Semidefinite programming
2019-06-29 — 2023-07-23
Wherein the Generalised Theory of Convex Programming Is Presented, and Optimization Problems Constrained by Positive Semidefinite Matrix Inequalities Are Shown to Be Expressible and Solvable via Specialized Numerical Solvers.
Optimization of a linear objective over symmetric matrices constrained to be positive semidefinite,
\[\min_X \ \langle C, X \rangle \quad \text{subject to} \quad \langle A_i, X \rangle = b_i, \quad X \succeq 0.\]
This is a convex program, since the positive semidefinite matrices form a convex cone and all the other stuff is linear. Replace \(X \succeq 0\) by membership \(x \in K\) of some other closed convex cone \(K\), keeping the linear objective and the linear equality constraints, and the result is called a cone program. Taking \(K\) to be the non-negative orthant \(\{x : x_j \ge 0\}\) gives linear programming, and taking it to be the second-order cone \(\{(u, t) : \|u\|_2 \le t\}\) gives second-order cone programming, which contains convex quadratic programming. These classes are nested: a linear program is a semidefinite program with diagonal \(X\), and a second-order cone constraint is a matrix inequality,
\[\|u\|_2 \le t \iff \begin{pmatrix} t I & u \\ u^\top & t \end{pmatrix} \succeq 0.\]
There exist more general cone programs beyond semidefinite programming but I have never needed to use them. Which convex problems are semidefinite programs? Any problem can be put in epigraph form, minimizing a new scalar \(t\) subject to \(f(x) \le t\) in place of minimizing \(f(x)\), which makes the objective one more constraint. The problem can then be solved as a semidefinite program if each constraint set, such as the epigraph \(\{(x, t) : f(x) \le t\}\), can be expressed as a linear matrix inequality \(A_0 + \sum_i x_i A_i + t B + \sum_j u_j C_j \succeq 0\) for fixed symmetric matrices, with auxiliary variables \(u\) allowed. If not, it is still a convex program, but not a semidefinite program.
Semidefinite programs, with the linear and second-order cone programs inside them, were for a long time the largest class of cone programs with reliable general-purpose interior-point solvers; current ones such as MOSEK and Clarabel also accept exponential and power cones too. A practical limit on the semidefinite part is size, since an interior-point method gets memory constrained and runs out of memory once a matrix variable \(X\) is a few thousand on a side.
Placeholder.
1 Intros
(Freund 2004; Vandenberghe and Boyd 1996)
Convex Optimization and Euclidean Distance Geometry 2ε by Jon Dattorro.
2 Problems that are secretly semidefinite programs
A problem that looks non-convex in its own variables can be convex in a lifted matrix variable. The lifting trick is that a quadratic form \(x^\top Q x\) equals \(\langle Q, X \rangle\) for \(X = xx^\top\), which is linear in \(X\). The set of such \(X\) is the positive semidefinite matrices of rank one; drop the rank condition and what remains is a semidefinite program, a convex relaxation of the original. (Shades of the kernel trick.)
From this we extract:
- Stability and controller synthesis for linear systems, as linear matrix inequalities. A Lyapunov function \(x^\top P x\) guarantees stability when \(P \succ 0\) and \(A^\top P + P A \prec 0\), which is a feasibility problem in \(P\). (Boyd 1994) is free and is mostly a catalogue of control problems analyzed through this lens.
- Approximate Max-Cut (Goemans and Williamson 1995)
- Optimal power flow, (Lavaei and Low 2012)
- Low-rank matrix recovery, since the nuclear norm, the convex surrogate for rank, has a semidefinite representation: matrix completion (Candes and Recht 2008), and phase retrieval (Candes, Strohmer, and Voroninski 2011)
3 Tools
Handy tool for some problems:
GENO (Soeren Laue, Mitterreiter, and Giesen 2019; Sören Laue, Blacher, and Giesen 2022)
GENO provides optimization solvers for everyone. You can enter your optimization problem in an easy-to-read modeling language in the code editor below. Python code is then generated automatically that can solve this class of optimization problems on the CPU or on the GPU. The automatically generated solvers are often as fast as handwritten, specialised solvers…
The GENO solver combines an Augmented Lagrangian approach with a limited memory quasi-Newton method (L-BFGS-B) that can handle also bound constraints on the variables. Quasi-Newton methods are very efficient for problems involving thousands of optimization variables. The GENO solver is then instantiated by the automatically generated methods for computing function values and gradients that are provided by this website to solve the specified class of optimization problems. This approach is very well suited for optimization problems originating from classical machine learning problems.