Linear, Cone and Semidefinite Programming

Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone

  • Monique Laurent
  • Teresa Piovesan
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    We investigate the completely positive semidefinite cone $\mathcal{CS}_+^n$, a new matrix cone consisting of all $n\times n$ matrices that admit a Gram representation by positive semidefinite matrices (of any size). In particular we study relationships between this cone and the completely positive and doubly nonnegative cones, and between its dual cone and trace positive non-commutative … Read more

    An elementary proof of linear programming optimality conditions without using Farkas’ lemma

  • Anders Forsgren
  • Margaret H. Wright
    • Categories Linear Programming Tags , ,

    Although it is easy to prove the sufficient conditions for optimality of a linear program, the necessary conditions pose a pedagogical challenge. A widespread practice in deriving the necessary conditions is to invoke Farkas’ lemma, but proofs of Farkas’ lemma typically involve “nonlinear” topics such as separating hyperplanes between disjoint convex sets, or else more … Read more

    Linear conic optimization for nonlinear optimal control

  • Didier Henrion
  • Edouard Pauwels
    • Categories Control Applications, Infinite Dimensional Optimization, Semi-definite Programming

    Infinite-dimensional linear conic formulations are described for nonlinear optimal control problems. The primal linear problem consists of finding occupation measures supported on optimal relaxed controlled trajectories, whereas the dual linear problem consists of finding the largest lower bound on the value function of the optimal control problem. Various approximation results relating the original optimal control … Read more

    Sensitivity analysis of semidefinite programs without strong duality

  • Yuen-Lam Cheung
  • Henry Wolkowicz
    • Categories Semi-definite Programming Tags , , ,

    Suppose that we are given a feasible conic program with a finite optimal value and with strong duality failing. It is known that there are small perturbations of the problem data that lead to relatively big changes in the optimal value. We quantify the notion of big change in the case of a semidefinite program … Read more

    New lower bounds and asymptotics for the cp-rank

  • Immanuel M. Bomze
  • Werner Schachinger
  • Reinhard Ullrich
    • Categories Linear, Cone and Semidefinite Programming Tags , ,

    Let $p_n$ denote the largest possible cp-rank of an $n\times n$ completely positive matrix. This matrix parameter has its significance both in theory and applications, as it sheds light on the geometry and structure of the solution set of hard optimization problems in their completely positive formulation. Known bounds for $p_n$ are $s_n=\binom{n+1}2-4$, the current … Read more

    Disjunctive Cuts for Cross-Sections of the Second-Order Cone

  • Gérard Cornuéjols
  • Sercan Yildiz
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming Tags , , ,

    In this paper we provide a unified treatment of general two-term disjunctions on cross-sections of the second-order cone. We derive a closed-form expression for a convex inequality that is valid for such a disjunctive set and show that this inequality is sufficient to characterize the closed convex hull of all two-term disjunctions on ellipsoids and … Read more

    Exact duality in semidefinite programming based on elementary reformulations

  • Minghui Liu
  • Gabor Pataki
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Semi-definite Programming

    In semidefinite programming (SDP), unlike in linear programming, Farkas’ lemma may fail to prove infeasibility. Here we obtain an exact, short certificate of infeasibility in SDP by an elementary approach: we reformulate any equality constrained semidefinite system using only elementary row operations, and rotations. When the system is infeasible, the infeasibility of the reformulated system … Read more

    How to Convexify the Intersection of a Second Order Cone and a Nonconvex Quadratic

  • Samuel Burer
  • Fatma Kılınç-Karzan
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Second-Order Cone Programming Tags , , , , , , ,

    A recent series of papers has examined the extension of disjunctive-programming techniques to mixed-integer second-order-cone programming. For example, it has been shown—by several authors using different techniques—that the convex hull of the intersection of an ellipsoid, $\E$, and a split disjunction, $(l – x_j)(x_j – u) \le 0$ with $l < u$, equals the intersection ... Read more

    Strong duality in Lasserre’s hierarchy for polynomial optimization

  • Didier Henrion
  • Cedric Josz
    • Categories Global Optimization Theory, Semi-definite Programming

    A polynomial optimization problem (POP) consists of minimizing a multivariate real polynomial on a semi-algebraic set $K$ described by polynomial inequalities and equations. In its full generality it is a non-convex, multi-extremal, difficult global optimization problem. More than an decade ago, J.~B.~Lasserre proposed to solve POPs by a hierarchy of convex semidefinite programming (SDP) relaxations … Read more

    Calmness of linear programs under perturbations of all data: characterization and modulus

  • M.J. Cánovas
  • Abderrahim Hantoute
  • J. Parra
  • F.J. Toledo
    • Categories Complementarity and Variational Inequalities, Convex Optimization, Linear Programming Tags , , ,

    This paper provides operative point-based formulas (only involving the nominal data, and not data in a neighborhood) for computing or estimating the calmness modulus of the optimal set (argmin) mapping in linear optimization under uniqueness of nominal optimal solutions. Our analysis is developed in two different parametric settings. First, in the framework of canonical perturbations … Read more