The behaviour of the moment-sums-of-squares (moment-SOS) hierarchy for polynomial optimal control problems on compact sets has been explored to a large extent. Our contribution focuses on the case of non-compact control sets. We describe a new approach to optimal control problems with unbounded controls, using compactification by partial homogenization, leading to an equivalent infinite dimensional … Read more
We investigate the local linear convergence properties of the Alternating Direction Method of Multipliers (ADMM) when applied to Semidefinite Programming (SDP). A longstanding belief suggests that ADMM is only capable of solving SDPs to moderate accuracy, primarily due to its sublinear worst-case complexity and empirical observations of slow convergence. We challenge this notion by introducing … Read more
General quadratically constrained quadratic programs (QCQPs) are challenging to solve as they are known to be NP-hard. A popular approach to approximating QCQP solutions is to use semidefinite programming (SDP) relaxations. It is well-known that the optimal value η of the SDP relaxation problem bounds the optimal value ζ of the QCQP from below, i.e., … Read more
This paper presents the Lagrangian duality theory for mixed-integer semidefinite programming (MISDP). We derive the Lagrangian dual problem and prove that the resulting Lagrangian dual bound dominates the bound obtained from the continuous relaxation of the MISDP problem. We present a hierarchy of Lagrangian dual bounds by exploiting the theory of integer positive semidefinite matrices … Read more
We study the lift-and-project rank of the stable set polytope of graphs with respect to the Lovász–Schrijver SDP operator \( \text{LS}_+ \) applied to the fractional stable set polytope. In particular, we show that for every positive integer \( \ell \), the smallest possible graph with \( \text{LS}_+ \)-rank \( \ell \) contains \( 3\ell … Read more
Inspired by the impact of the Goemans-Williamson algorithm on combinatorial optimization, we construct an analogous relax-then-round strategy for low-rank optimization problems. First, for orthogonally constrained quadratic optimization problems, we derive a semidefinite relaxation and a randomized rounding scheme that obtains provably near-optimal solutions, building on the blueprint from Goemans and Williamson for the Max-Cut problem. … Read more
A convex cone K is said to be homogeneous if its group of automorphisms acts transitively on its relative interior. Important examples of homogeneous cones include symmetric cones and cones of positive semidefinite (PSD) matrices that follow a sparsity pattern given by a homogeneous chordal graph. Our goal in this paper is to elucidate the … Read more
A polynomial matrix inequality is a statement that a symmetric polynomial matrix is positive semidefinite over a given constraint set. Polynomial matrix optimization concerns minimizing the smallest eigenvalue of a symmetric polynomial matrix subject to a tuple of polynomial matrix inequalities. This work explores the use of sparsity methods in reducing the complexity of sum-of-squares … Read more
We extend recent computer-assisted design and analysis techniques for first-order optimization over structured functions–known as performance estimation–to apply to structured sets. We prove “interpolation theorems” for smooth and strongly convex sets with Slater points and bounded diameter, showing a wide range of extremal questions amount to structured mathematical programs. Prior function interpolation theorems are recovered … Read more
In the quadratic minimum spanning tree problem (QMSTP) one wants to find the minimizer of a quadratic function over all possible spanning trees of a graph. We present a formulation of the QMSTP as a mixed-integer semidefinite program exploiting the algebraic connectivity of a graph. Based on this formulation, we derive a doubly nonnegative relaxation … Read more