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
Deploying mathematical optimization in autonomous production systems requires precise contracts for objects returned by an optimization solver. Unfortunately, conventions on dual solution and infeasibility certificates (rays) vary widely across solvers and classes of problems. This paper presents the theoretical framework used by MathOpt (a domain-specific language developed and used at Google) to unify these notions. … Read more
In modern Formula~1, strict regulations and highly optimized cars limit performance gains through hardware, increasing the importance of strategic decision-making. This work tackles the problem of computing a race strategy that minimizes total race time by jointly optimizing tire stints, compound selection, fuel load, and Energy Recovery System (ERS) deployment. We present a high-performance simulation … Read more
ArticleDownload View PDF
We consider a quadratic minmax problem with coupled inner constraints and propose a method to compute a class of stationary points. To motivate the need to compute such stationary points, we first show that they are meaningful, in the sense that they can be locally optimal for our problem under suitable linear independence and second-order … 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