Semi-definite Programming

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

    Maximal entropy in the moment body

  • Didier Henrion
    • Categories Semi-definite Programming

    A moment body is a linear projection of the spectraplex, the convex set of trace-one positive semidefinite matrices. Determining whether a given point lies within a given moment body is a problem with numerous applications in quantum state estimation or polynomial optimization. This moment body membership oracle can be addressed with semidefinite programming, for which … Read more

    Efficient QUIC-Based Damped Inexact Iterative Reweighting for Sparse Inverse Covariance Estimation with Nonconvex Partly Smooth Regularization

  • Xiangyu Yang
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization, Semi-definite Programming Tags , , ,

    In this paper, we study sparse inverse covariance matrix estimation incorporating partly smooth nonconvex regularizers. To solve the resulting regularized log-determinant problem, we develop DIIR-QUIC—a novel Damped Inexact Iteratively Reweighted algorithm based on QUadratic approximate Inverse Covariance (QUIC) method. Our approach generalizes the classic iteratively reweighted \(\ell_1\) scheme through damped fixed-point updates. A key novelty … Read more