Semi-definite Programming

Sequential constant rank constraint qualifications for nonlinear semidefinite programming with applications

  • Roberto Andreani
  • Gabriel Haeser
  • Héctor Ramírez
  • Leonardo M. Mito
    • Categories Constrained Nonlinear Optimization, Second-Order Cone Programming, Semi-definite Programming Tags , , ,

    We present new constraint qualification conditions for nonlinear semidefinite programming that extend some of the constant rank-type conditions from nonlinear programming. As an application of these conditions, we provide a unified global convergence proof of a class of algorithms to stationary points without assuming neither uniqueness of the Lagrange multiplier nor boundedness of the Lagrange … Read more

    Evaluating approximations of the semidefinite cone with trace normalized distance

  • Yuzhu Wang
  • Akiko Yoshise
    • Categories Semi-definite Programming Tags , ,

    We evaluate the dual cone of the set of diagonally dominant matrices (resp., scaled diagonally dominant matrices), namely ${\cal DD}_n^*$ (resp., ${\cal SDD}_n^*$), as an approximation of the semidefinite cone. We prove that the norm normalized distance, proposed by Blekherman et al. (2022), between a set ${\cal S}$ and the semidefinite cone has the same … Read more

    A new perspective on low-rank optimization

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Semi-definite Programming Tags , , ,

    A key question in many low-rank problems throughout optimization, machine learning, and statistics is to characterize the convex hulls of simple low-rank sets and judiciously apply these convex hulls to obtain strong yet computationally tractable convex relaxations. We invoke the matrix perspective function — the matrix analog of the perspective function — and characterize explicitly … Read more

    SOS-SDP: an Exact Solver for Minimum Sum-of-Squares Clustering

  • Veronica Piccialli
  • Antonio M. Sudoso
  • Angelika Wiegele
    • Categories 0-1 Programming, Quadratic Programming, Semi-definite Programming

    The minimum sum-of-squares clustering problem (MSSC) consists in partitioning n observations into k clusters in order to minimize the sum of squared distances from the points to the centroid of their cluster. In this paper, we propose an exact algorithm for the MSSC problem based on the branch-and-bound technique. The lower bound is computed by … Read more

    A Strengthened Barvinok-Pataki Bound on SDP Rank

  • Haesol Im
  • Henry Wolkowicz
    • Categories Semi-definite Programming Tags , , , ,

    The Barvinok-Pataki bound provides an upper bound on the rank of extreme points of a spectrahedron. This bound depends solely on the number of affine constraints of the problem, i.e., on the algebra of the problem. Specifically, the triangular number of the rank r is upper bounded by the number of affine constraints. We revisit … Read more

    Time-Varying Semidefinite Programming: Geometry of the Trajectory of Solutions

  • Antonio Bellon
  • Didier Henrion
  • Vyacheslav Kungurtsev
  • Jakub Marecek
    • Categories Semi-definite Programming

    In many applications, solutions of convex optimization problems must be updated on-line, as functions of time. In this paper, we consider time-varying semidefinite programs (TV-SDP), which are linear optimization problems in the semidefinite cone whose coefficients (input data) depend on time. We are interested in the geometry of the solution (output data) trajectory, defined as … Read more

    How do exponential size solutions arise in semidefinite programming?

  • Gabor Pataki
  • Aleksandr Touzov
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Semi-definite Programming

    Semidefinite programs (SDPs) are some of the most popular and broadly applicable optimization problems to emerge in the last thirty years. A curious pathology of SDPs, illustrated by a classical example of Khachiyan, is that their solutions may need exponential space to even write down. Exponential size solutions are the main obstacle to solve a … Read more

    Moment-SOS hierarchy and exit time of stochastic processes

  • Didier Henrion
  • Mauricio Junca
  • Mauricio Velasco
    • Categories Semi-definite Programming

    The moment sum of squares (moment-SOS) hierarchy produces sequences of upper and lower bounds on functionals of the exit time solution of a polynomial stochastic differential equation with polynomial constraints, at the price of solving semidefinite optimization problems of increasing size. In this note we use standard results from elliptic partial differential equation analysis to … Read more

    Weak notions of nondegeneracy in nonlinear semidefinite programming

  • Roberto Andreani
  • Gabriel Haeser
  • Leonardo M. Mito
  • Héctor Ramírez
    • Categories Constrained Nonlinear Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    The constraint nondegeneracy condition is one of the most relevant and useful constraint qualifications in nonlinear semidefinite programming. It can be characterized in terms of any fixed orthonormal basis of the, let us say, $\ell$-dimensional kernel of the constraint matrix, by the linear independence of a set of $\ell(\ell+1)/2$ derivative vectors. We show that this … Read more

    A Geometric View of SDP Exactness in QCQPs and its Applications

  • Fatma Kılınç-Karzan
  • Alex L. Wang
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , ,

    Let S denote a subset of Rn defined by quadratic equality and inequality constraints and let S denote its projected semidefinite program (SDP) relaxation. For example, take S and S to be the epigraph of a quadratically constrained quadratic program (QCQP) and the projected epigraph of its SDP relaxation respectively. In this paper, we suggest … Read more