Linear, Cone and Semidefinite Programming

Improved Decision Rule Approximations for Multi-Stage Robust Optimization via Copositive Programming

  • Grani A. Hanasusanto
  • Guanglin Xu
    • Categories Dynamic Programming, Linear, Cone and Semidefinite Programming, Robust Optimization

    We study decision rule approximations for generic multi-stage robust linear optimization problems. We consider linear decision rules for the case when the objective coefficients, the recourse matrices, and the right-hand sides are uncertain, and consider quadratic decision rules for the case when only the right-hand sides are uncertain. The resulting optimization problems are NP-hard but … Read more

    Outer Approximation With Conic Certificates For Mixed-Integer Convex Problems

  • Chris Coey
  • Miles Lubin
  • Juan Pablo Vielma
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming, Optimization Software Benchmark Tags , ,

    A mixed-integer convex (MI-convex) optimization problem is one that becomes convex when all integrality constraints are relaxed. We present a branch-and-bound LP outer approximation algorithm for an MI-convex problem transformed to MI-conic form. The polyhedral relaxations are refined with K* cuts} derived from conic certificates for continuous primal-dual conic subproblems. Under the assumption that all … Read more

    Time-Varying Semidefinite Programs

  • Amir Ali Ahmadi
  • Bachir El Khadir
    • Categories Basic Sciences Applications, Infinite Dimensional Optimization, Semi-definite Programming Tags , , , , ,

    We study time-varying semidefinite programs (TV-SDPs), which are semidefinite programs whose data (and solutions) are functions of time. Our focus is on the setting where the data varies polynomially with time. We show that under a strict feasibility assumption, restricting the solutions to also be polynomial functions of time does not change the optimal value … Read more

    Positive semidefinite matrix approximation with a trace constraint

  • Kouhei Harada
    • Categories Convex Optimization, Semi-definite Programming Tags , , , ,

    We propose an efficient algorithm to solve positive a semidefinite matrix approximation problem with a trace constraint. Without constraints, it is well known that positive semidefinite matrix approximation problem can be easily solved by one-time eigendecomposition of a symmetric matrix. In this paper, we confirmed that one-time eigendecomposition is also sufficient even if a trace … Read more

    Cutting Planes by Projecting Interior Points onto Polytope Facets

  • Daniel Porumbel
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Linear Programming Tags , ,

    Given a point x inside a polytope P and a direction d, the projection of x along d asks to find the maximum step length t such that x+td is feasible; we say x+td is a pierce point because it belongs to the boundary of P. We address this projection sub-problem with arbitrary interior points … Read more

    An improved projection and rescaling algorithm for conic feasibility problems

  • Yanqin Bai
  • Cornelis Roos
  • Wei Zhang
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    Motivated by Chubanov’s projection-based method for linear feasibility problems [Chubanov2015], a projection and rescaling algorithm for the conic feasibility problem \[ find \; x\in L\bigcap \Omega \] is proposed in [Pena2016], where $L$ and $\Omega$ are respectively a linear subspace and the interior of a symmetric cone in a finitely dimensional vector space $V$. When … Read more

    Best case exponential running time of a branch-and-bound algorithm using an optimal semidefinite relaxation

  • Florian Jarre
    • Categories Branch and Cut Algorithms, Linear, Cone and Semidefinite Programming Tags , ,

    Chvatal (1980) has given a simple example of a knapsack problem for which a branch-and-bound algorithm using domination and linear relaxations to eliminate subproblems will use an exponential number of steps in the best case. In this short note it is shown that Chvatals result remains true when the LP relaxation is replaced with a … Read more

    Convex computation of extremal invariant measures of nonlinear dynamical systems and Markov processes

  • Didier Henrion
  • Milan Korda
  • Igor Mezic
    • Categories Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , ,

    We propose a convex-optimization-based framework for computation of invariant measures of polynomial dynamical systems and Markov processes, in discrete and con- tinuous time. The set of all invariant measures is characterized as the feasible set of an infinite-dimensional linear program (LP). The objective functional of this LP is then used to single-out a specific measure … Read more

    Finding Minimum Volume Circumscribing Ellipsoids Using Generalized Copositive Programming

  • Grani A. Hanasusanto
  • Areesh Mittal
    • Categories Linear, Cone and Semidefinite Programming

    We study the problem of finding the Lowner-John ellipsoid, i.e., an ellipsoid with minimum volume that contains a given convex set. We reformulate the problem as a generalized copositive program, and use that reformulation to derive tractable semidefinite programming approximations for instances where the set is defined by affine and quadratic inequalities. We prove that, … Read more

    Semidenite Approximations of Invariant Measures for Polynomial Systems

  • Marcelo Forets
  • Didier Henrion
  • Victor Magron
    • Categories Semi-definite Programming, Systems governed by Differential Equations Optimization Tags , , , ,

    We consider the problem of approximating numerically the moments and the supports of measures which are invariant with respect to the dynamics of continuousand discrete-time polynomial systems, under semialgebraic set constraints. First, we address the problem of approximating the density and hence the support of an invariant measure which is absolutely continuous with respect to … Read more