Semi-definite Programming

Solving Stengle’s Example in Rational Arithmetic: Exact Values of the Moment-SOS Relaxations

  • Didier Henrion
    • Categories Semi-definite Programming Tags , , , ,

    We revisit Stengle’s classical univariate polynomial optimization example $\min 1-x^2$ s.t. $(1-x^2)^3\ge 0$ whose constraint description is degenerate at the minimizers. We prove that the moment-SOS hierarchy of relaxation order $r\ge 3$ has the exact value $-1/r(r-2)$. For this we construct in rational arithmetic a dual polynomial sum-of-squares (SOS) certificate and a primal moment sequence … Read more

    Global optimization of low-rank polynomials

  • Llorenç Balada Gaggioli
  • Didier Henrion
  • Milan Korda
    • Categories Global Optimization, Semi-definite Programming

    This work considers polynomial optimization problems where the objective admits a low-rank canonical polyadic tensor decomposition. We introduce LRPOP (low-rank polynomial optimization), a new hierarchy of semidefinite programming relaxations for which the size of the semidefinite blocks is determined by the canonical polyadic rank rather than the number of variables. As a result, LRPOP can … Read more

    Semidefinite hierarchies for diagonal unitary invariant bipartite quantum states

  • Jonas Britz
  • Monique Laurent
    • Categories Semi-definite Programming Tags , , , , , , , , ,

    We investigate questions about the cone \(\mathrm{SEP}_n\) of separable bipartite states, consisting of the Hermitian matrices acting on \(\mathbb{C}^n\otimes\mathbb{C}^n\) that can be written as conic combinations of rank one matrices of the form \(xx^*\otimes yy^*\) with \(x,y\in\mathbb{C}^n\). Bipartite states that are not separable are said to be entangled. Detecting quantum entanglement is a fundamental task … Read more

    Density, Determinacy, Duality and a Regularized Moment-SOS Hierarchy

  • Didier Henrion
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags ,

    The standard moment-sum-of-squares (SOS) hierarchy is a powerful method for solving global polynomial optimization problems. However, its convergence relies on Putinar’s Positivstellensatz, which requires the feasible set to satisfy the algebraic Archimedean property. In this paper, we introduce a regularized moment-SOS hierarchy capable of handling problems on unbounded sets or bounded sets violating the Archimedean … Read more

    A Dual Riemannian ADMM Algorithm for Low-Rank SDPs with Unit Diagonal

  • Jie Wang
    • Categories 0-1 Programming, Semi-definite Programming Tags , , , , , , ,

    This paper proposes a dual Riemannian alternating direction method of multipliers (ADMM) for solving low-rank semidefinite programs with unit diagonal constraints. We recast the ADMM subproblem as a Riemannian optimization problem over the oblique manifold by performing the Burer-Monteiro factorization. Global convergence of the algorithm is established assuming that the subproblem is solved to certain … Read more

    Semidefinite programming via Projective Cutting Planes for dense (easily-feasible) instances

  • Daniel Porumbel
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    The cone of positive semi-definite (SDP) matrices can be described by an infinite number of linear constraints. It is well-known that one can optimize over such a feasible area by standard Cutting Planes, but work on this idea remains a rare sight, likely due to its limited practical appeal compared to Interior Point Methods (IPMs). … Read more

    Sparse Multiple Kernel Learning: Alternating Best Response and Semidefinite Relaxations

  • Dimitris Bertsimas
  • Caio de Próspero Iglesias
  • Nicholas A. G. Johnson
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , , , ,

    We study Sparse Multiple Kernel Learning (SMKL), which is the problem of selecting a sparse convex combination of prespecified kernels for support vector binary classification. Unlike prevailing \(\ell_1\)‐regularized approaches that approximate a sparsifying penalty, we formulate the problem by imposing an explicit cardinality constraint on the kernel weights and add an \(\ell_2\) penalty for robustness. … Read more

    Moment-sos and spectral hierarchies for polynomial optimization on the sphere and quantum de Finetti theorems

  • Alexander Taveira Blomenhofer
  • Monique Laurent
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

    We revisit the convergence analysis of two approximation hierarchies for polynomial optimization on the unit sphere. The first one is based on the moment-sos approach and gives semidefinite bounds for which Fang and Fawzi (2021) showed an analysis in \(O(1/r^2)\) for the r-th level bound, using the polynomial kernel method. The second hierarchy was recently … Read more

    A user manual for cuHALLaR: A GPU accelerated low-rank semidefinite programming Solver

  • Jacob Aguirre
  • Diego Cifuentes
  • Vincent Guigues
  • Renato D.C. Monteiro
  • Victor Hugo Nascimento
  • Arnesh Sujanani
    • Categories Nonlinear Optimization, Optimization Software and Modeling Systems, Semi-definite Programming Tags , , , , , ,

    We present a Julia-based interface to the precompiled HALLaR and cuHALLaR binaries for large-scale semidefinite programs (SDPs). Both solvers are established as fast and numerically stable, and accept problem data in formats compatible with SDPA and a new enhanced data format taking advantage of Hybrid Sparse Low-Rank (HSLR) structure. The interface allows users to load … Read more

    A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation

  • Alberto Del Pia
  • Dekun Zhou
    • Categories (Mixed) Integer Linear Programming, Data Science Algorithms, Semi-definite Programming

    Sparse Principal Component Analysis (SPCA) is a fundamental technique for dimensionality reduction, and is NP-hard. In this paper, we introduce a randomized approximation algorithm for SPCA, which is based on the basic SDP relaxation. Our algorithm has an approximation ratio of at most the sparsity constant with high probability, if called enough times. Under a … Read more