Linear, Cone and Semidefinite Programming

An exact duality theory for semidefinite programming based on sums of squares

  • Igor Klep
  • Markus Schweighofer
    • Categories Semi-definite Programming Tags , , , , , , , ,

    Farkas’ lemma is a fundamental result from linear programming providing linear certificates for infeasibility of systems of linear inequalities. In semidefinite programming, such linear certificates only exist for strongly infeasible linear matrix inequalities. We provide nonlinear algebraic certificates for all infeasible linear matrix inequalities in the spirit of real algebraic geometry: A linear matrix inequality … Read more

    A Proof by the Simplex Method for the Diameter of a (0,1)-Polytope

  • Tomonari Kitahara
  • Shinji Mizuno
    • Categories Graphs and Matroids, Linear Programming Tags , , , ,

    Naddef shows that the Hirsch conjecture is true for (0,1)-polytopes by proving that the diameter of any $(0,1)$-polytope in $d$-dimensional Euclidean space is at most $d$. In this short paper, we give a simple proof for the diameter. The proof is based on the number of solutions generated by the simplex method for a linear … Read more

    Sampling with respect to a class of measures arising in second-order cone optimization with rank constraints

  • Leonid Faybusovich
    • Categories Second-Order Cone Programming Tags , ,

    We describe a classof measures on second-order cones as a push-forward of the Cartesian product of a probabilistic measure on positive semi-line corresponding to Gamma distribution and the uniform measure on the sphere Citationreport, Department of Mathematics, University of Notre Dame, July, 2011ArticleDownload View PDF

    An efficient semidefinite programming relaxation for the graph partition problem

  • Renata Sotirov
    • Categories Semi-definite Programming Tags , , , ,

    We derive a new semidefinite programming relaxation for the general graph partition problem (GPP). Our relaxation is based on matrix lifting with matrix variable having order equal to the number of vertices of the graph. We show that this relaxation is equivalent to the Frieze-Jerrum relaxation [A. Frieze and M. Jerrum. Improved approximation algorithms for … Read more

    A Complementarity Partition Theorem for Multifold Conic Systems

  • Javier F. Peña
  • Vera Roshchina
    • Categories Convex Optimization, Second-Order Cone Programming Tags ,

    Consider a homogeneous multifold convex conic system $$ Ax = 0, \; x\in K_1\times \cdots \times K_r $$ and its alternative system $$ A\transp y \in K_1^*\times \cdots \times K_r^*, $$ where $K_1,\dots, K_r$ are regular closed convex cones. We show that there is canonical partition of the index set $\{1,\dots,r\}$ determined by certain complementarity … Read more

    Lower bounds for the maximum number of solutions generated by the simplex method

  • Tomonari Kitahara
  • Shinji Mizuno
    • Categories Linear Programming Tags , ,

    Kitahara and Mizuno get upper bounds for the maximum number of different basic feasible solutions generated by Dantzig�s simplex method. In this paper, we obtain lower bounds of the maximum number. Part of the results in this paper are shown in a paper by the authors as a quick report without proof. They present a … Read more

    Solving Basis Pursuit: Heuristic Optimality Check and Solver Comparison

  • Dirk A. Lorenz
  • Marc E. Pfetsch
  • Andreas M. Tillmann
    • Categories Linear Programming, Nonsmooth Optimization, Optimization Software Benchmark Tags , , , ,

    The problem of finding a minimum l^1-norm solution to an underdetermined linear system is an important problem in compressed sensing, where it is also known as basis pursuit. We propose a heuristic optimality check as a general tool for l^1-minimization, which often allows for early termination by “guessing” a primal-dual optimal pair based on an … Read more

    Representing quadratically constrained quadratic programs as generalized copositive programs

  • Samuel Burer
  • Hongbo Dong
    • Categories Global Optimization Theory, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , ,

    We show that any nonconvex quadratically constrained quadratic program(QCQP) can be represented as a generalized copositive program. In fact,we provide two representations. The first is based on the concept of completely positive (CP) matrices over second order cones, while the second is based on CP matrices over the positive semidefinte cone. Our analysis assumes that … Read more

    Approximation of rank function and its application to the nearest low-rank correlation matrix

  • Shujun Bi
  • Shaohua Pan
    • Categories Applications - Science and Engineering, Nonsmooth Optimization, Semi-definite Programming

    The rank function $\rank(\cdot)$ is neither continuous nor convex which brings much difficulty to the solution of rank minimization problems. In this paper, we provide a unified framework to construct the approximation functions of $\rank(\cdot)$, and study their favorable properties. Particularly, with two families of approximation functions, we propose a convex relaxation method for the … Read more

    How to generate weakly infeasible semidefinite programs via Lasserre’s relaxations for polynomial optimization

  • Hayato Waki
    • Categories Convex Optimization, Semi-definite Programming Tags , ,

    Examples of weakly infeasible semidefinite programs are useful to test whether semidefinite solvers can detect infeasibility. However, finding non trivial such examples is notoriously difficult. This note shows how to use Lasserre’s semidefinite programming relaxations for polynomial optimization in order to generate examples of weakly infeasible semidefinite programs. Such examples could be used to test … Read more