We develop tractable convex relaxations for rank-constrained quadratic optimization problems over $n \times m$ matrices, a setting for which tractable relaxations are typically only available when the objective or constraints admit spectral (permutation-invariant) structure. We derive lifted semidefinite relaxations that do not require such spectral terms. Although a direct lifting introduces a large semidefinite constraint … Read more
Quasinormality is a classical constraint qualification originally introduced by Hestenes in 1975 and subsequently extensively studied in nonlinear programming and in problems with abstract constraints. In this paper, we extend this concept to the setting of nonlinear semidefinite programming (NSDP). We show that the proposed condition is strictly weaker than Robinson’s constraint qualification, while still … Read more
Algorithms based on polyhedral outer approximations provide a powerful approach to solving mixed-integer nonlinear optimization problems. An initial relaxation of the feasible set is strengthened by iteratively adding linear inequalities and separating infeasible points. However, when the constraints are nonconvex, computing such separating hyperplanes becomes challenging. In this article, the moment-/sums-of-squares hierarchy is used in … Read more
We introduce a new class of semidefinite programming (SDP) relaxations for sparse box-constrained quadratic programs, obtained by a novel integration of the Reformulation Linearization Technique into standard SDP relaxations while explicitly exploiting the sparsity of the problem. The resulting relaxations are not implied by the existing LP and SDP relaxations for this class of optimization … Read more
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
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
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
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
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
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