Semidefinite Programming

(Positive) Semidefinite Programming

Problem definition

SDP (Positive Semidefinite Programming) is a class of special non-linear convex optimization problems which has been widely applied to model controlling, truss design and relaxation of combinartorial problems. The optimization variables of SDP are matrices and the standard form is given by

$\begin{array}{c} \min_x & \sum_{j = 1}^p \langle C_j, X_j \rangle & \\ \text{subject to} ~~& \sum_{j = 1}^p \langle A_{i j}, X_j \rangle = b_i, & i = 1, \ldots, m\\ & X_j \in \mathbb{S}_+^{n_j}, & \end{array}$

where symmetric matrices and are problem data; is the right-hand-side vector of the equality constraints; the optimization variables are positive-semidefinite matrices. The matrix inner product in SDP is defined by .

Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize) over the intersection of the cone (opens new window) of positive semidefinite (opens new window) matrices (opens new window) with an affine space (opens new window), i.e., a spectrahedron (opens new window).

Semidefinite programming is a relatively new field of optimization which is of growing interest for several reasons. Many practical problems in operations research and combinatorial optimization can be modeled or approximated as semidefinite programming problems. In automatic control theory, SDPs are used in the context of linear matrix inequalities. SDPs are in fact a special case of cone programming (opens new window) and can be efficiently solved by interior point methods (opens new window). All linear programs and (convex) quadratic programs can be expressed as SDPs, and via hierarchies of SDPs the solutions of polynomial optimization problems can be approximated. Semidefinite programming has been used in the optimization of complex systems. In recent years, some quantum query complexity problems have been formulated in terms of semidefinite programs.

Algorithms

Currently most SDP optimization solvers implement the interior method and its variants, including

Primal-Dual Interior Point Method (PD-IPM)

Two popular variants of PD-IPM include Primal-Dual Infeasible Interior Point Method and Homogeneous Self-dual Embedding
Dual-scaling Interior Point Method

The interior point method implemented in DSDP