Month: May 2017

Vector Transport-Free SVRG with General Retraction for Riemannian Optimization: Complexity Analysis and Practical Implementation

  • Bo Jiang
  • Shiqian Ma
  • Anthony Man-Cho So
  • Shuzhong Zhang
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , , , ,

    In this paper, we propose a vector transport-free stochastic variance reduced gradient (SVRG) method with general retraction for empirical risk minimization over Riemannian manifold. Existing SVRG methods on manifold usually consider a specific retraction operation, and involve additional computational costs such as parallel transport or vector transport. The vector transport-free SVRG with general retraction we … Read more

    A simplicial decomposition framework for large scale convex quadratic programming

  • Enrico Bettiol
  • Lucas Létocart
  • Francesco Rinaldi
  • Emiliano Traversi
    • Categories Convex Optimization, Quadratic Programming Tags , , ,

    In this paper, we analyze in depth a simplicial decomposition like algorithmic framework for large scale convex quadratic programming. In particular, we first propose two tailored strategies for handling the master problem. Then, we describe a few techniques for speeding up the solution of the pricing problem. We report extensive numerical experiments on both real … Read more

    A New Use of Douglas-Rachford Splitting and ADMM for Identifying Infeasible, Unbounded, and Pathological Conic Programs

  • Yanli Liu
  • Ernest K. Ryu
  • Wotao Yin
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , ,

    In this paper, we present a method for identifying infeasible, unbounded, and pathological conic programs based on Douglas-Rachford splitting, or equivalently ADMM. When an optimization program is infeasible, unbounded, or pathological, the iterates of Douglas-Rachford splitting diverge.Somewhat surprisingly, such divergent iterates still provide useful information, which our method uses for identification. In addition, for strongly … Read more

    Multicut decomposition methods with cut selection for multistage stochastic programs

  • Michelle Bandarra
  • Vincent Guigues
    • Categories Stochastic Programming

    We introduce a variant of Multicut Decomposition Algorithms (MuDA), called CuSMuDA (Cut Selection for Multicut Decomposition Algorithms), for solving multistage stochastic linear programs that incorporates strategies to select the most relevant cuts of the approximate recourse functions. We prove the convergence of the method in a finite number of iterations and use it to solve … Read more

    Dual Dynamic Programming with cut selection: convergence proof and numerical experiments

  • Vincent Guigues
    • Categories Convex and Nonsmooth Optimization, Dynamic Programming

    We consider convex optimization problems formulated using dynamic programming equations. Such problems can be solved using the Dual Dynamic Programming algorithm combined with the Level 1 cut selection strategy or the Territory algorithm to select the most relevant Benders cuts. We propose a limited memory variant of Level 1 and show the convergence of DDP … Read more

    Solving Mixed-Integer Nonlinear Programs using Adaptively Refined Mixed-Integer Linear Programs

  • Robert Burlacu
  • Björn Geißler
  • Lars Schewe
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , ,

    We propose a method for solving mixed-integer nonlinear programs (MINLPs) to global optimality by discretization of occuring nonlinearities. The main idea is based on using piecewise linear functions to construct mixed-integer linear program (MIP) relaxations of the underlying MINLP. In order to find a global optimum of the given MINLP we develope an iterative algorithm … Read more

    Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization

  • Daniel Kuhn
  • Napat Rujeerapaiboon
  • Kilian Schindler
  • Wolfram Wiesemann
    • Categories Approximation Algorithms, Data-Mining, Linear, Cone and Semidefinite Programming Tags , , ,

    Plain vanilla K-means clustering is prone to produce unbalanced clusters and suffers from outlier sensitivity. To mitigate both shortcomings, we formulate a joint outlier-detection and clustering problem, which assigns a prescribed number of datapoints to an auxiliary outlier cluster and performs cardinality-constrained K-means clustering on the residual dataset. We cast this problem as a mixed-integer … Read more

    An Inexact Newton-like conditional gradient method for constrained nonlinear systems

  • Max L. N. Gonçalves
  • F.R. Oliveira
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization

    In this paper, we propose an inexact Newton-like conditional gradient method for solving constrained systems of nonlinear equations. The local convergence of the new method as well as results on its rate are established by using a general majorant condition. Two applications of such condition are provided: one is for functions whose the derivative satisfies … Read more

    Distributionally Robust Markovian Traffic Equilibrium

  • Selin Damla Ahipasaoglu
  • Karthik Natarajan
  • Ugur Arikan
    • Categories Robust Optimization, Transportation Tags , ,

    Stochastic user equilibrium models are fundamental to the analysis of transportation systems. Such models are typically developed under the assumption of route based choice models for the users. A class of link based models under a Markovian assumption on the route choice behavior of the users has been proposed to deal with the drawbacks of … Read more

    Oracle Complexity of Second-Order Methods for Smooth Convex Optimization

  • Ohad Shamir
  • Ron Shiff
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    Second-order methods, which utilize gradients as well as Hessians to optimize a given function, are of major importance in mathematical optimization. In this work, we study the oracle complexity of such methods, or equivalently, the number of iterations required to optimize a function to a given accuracy. Focusing on smooth and convex functions, we derive … Read more