Semidefinite programming

In semidefinite programming ( SDP , also semidefinite optimization ), optimization problems are examined whose variables are not vectors but symmetric matrices . As a secondary condition, it is required that these matrices are positive (or negative) semidefinite , from which the name of the problem results.

There are applications in the field of approximation theory , control theory , combinatorial optimization , optimal design of experiments and in technology.

Problem formulation

Given is the real vector space of the real, symmetric matrices provided with the Frobenius scalar product ${\displaystyle n\times n}$ ${\displaystyle S^{n}}$

${\displaystyle \langle A,B\rangle _{F}=\sum _{i=1}^{n}\sum _{j=1}^{n}a_{ij}b_{ij}=\operatorname {tr} (A^{T}B)=\operatorname {tr} (AB^{T})}$.

Here the trace is a matrix. ${\displaystyle \operatorname {tr} }$

Furthermore, let the cone of the symmetrical, positive semidefinite matrices and the generalized inequality defined by this cone , the so-called Loewner partial order, be . ${\displaystyle S_{+}^{n}}$ ${\displaystyle \preccurlyeq _{S_{+}^{n}}}$

Normal form

The optimization problem

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{F}&\\{\text{unter den Nebenbedingungen }}&X\succcurlyeq _{S_{+}^{n}}0&\,{\text{(positiv semidefinitheit)}}\\&\langle {A_{i}},{X}\rangle _{F}=b_{i}&\,{\text{ für }}i=1,\dots ,m\end{aligned}}}$

with a linear semidefinite program or simply semidefinite program (SDP for short) in normal form. We are looking for a real, symmetrical matrix that is positive semidefinite, the scalar product of which assumes a certain value with the given matrices and which is maximal with respect to the Frobenius scalar product. Sometimes the equation constraints are also summarized by a linear function , which is given by ${\displaystyle C,X,A_{i}\in S^{n}}$ ${\displaystyle X}$ ${\displaystyle m}$ ${\displaystyle L(X):S^{n}\mapsto \mathbb {R} ^{m}}$

${\displaystyle L(X):={\begin{pmatrix}\langle {A_{1}},{X}\rangle _{F}\\\vdots \\\langle {A_{m}},{X}\rangle _{F}\end{pmatrix}}}$

is defined. Then the inequality constraints are as . ${\displaystyle L(X)=b}$ ${\displaystyle b\in \mathbb {R} ^{m}}$

Inequality form

Analogous to linear optimization problems, there is also the inequality form of an SDP:

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(x)=c^{T}x\\{\text{unter den Nebenbedingungen }}&x_{1}A_{1}+\dots +x_{m}A_{m}\preccurlyeq _{S_{+}^{n}}B\end{aligned}}}$

where and are. Occasionally the inequality form is also written as ${\displaystyle x,c\in \mathbb {R} ^{m}}$ ${\displaystyle A_{i},B\in S^{n}}$

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(x)=c^{T}x\\{\text{unter den Nebenbedingungen }}&x_{1}A_{1}+\dots +x_{m}A_{m}+S=B\\&S\succcurlyeq _{S_{+}^{n}}0\end{aligned}}}$

This corresponds to the introduction of a slip variable . This form is often chosen in order to make analogies to the linear programs clear. Here, too, a linear function is occasionally defined by ${\displaystyle S}$ ${\displaystyle L^{*}(x):\mathbb {R} ^{m}\mapsto S^{n}}$

${\displaystyle L^{*}(x)=x_{1}A_{1}+\dots +x_{m}A_{m}}$,

to simplify the notation and to make later duality statements clearer.

Without generalized inequalities

If SDP is formulated without generalized inequalities, then the conditions (normal form) and (inequality form with slip variable) are usually written out as " (or- ) is positive semidefinite". ${\displaystyle X\succcurlyeq _{S_{+}^{n}}0}$ ${\displaystyle S\succcurlyeq _{S_{+}^{n}}0}$ ${\displaystyle X}$ ${\displaystyle S}$

Nonlinear semidefinite programs

Occasionally, non-linear semidefinite programs are also considered; these then either no longer have a linear objective function or have non-linear restrictions.

Classification and special cases

As convex optimization problems

Semidefinite programs are always convex optimization problems . This follows from the fact that all equation restrictions are always affine-linear and all inequality restrictions (using generalized inequalities) are always affine-linear and are therefore always K-convex functions . So the restriction set is convex. In addition, since the objective function is always linear, it is always an (abstract or generalized) convex problem, regardless of whether it is formulated as a minimization problem or a maximization problem.

As a conical program

Semidefinite programs are conical programs on the vector space of the symmetric real matrices provided with the Frobenius scalar product and using the cone of the positive semidefinite matrices. The linear subspace of the is described in the normal form by the core of the figure , i.e. by the solution set of the equation . In the inequality form with a slip variable, the subspace is described by the image of the figure . ${\displaystyle S^{n}}$ ${\displaystyle L:S^{n}\mapsto \mathbb {R} ^{m}}$ ${\displaystyle L(X)=0}$ ${\displaystyle L^{*}:\mathbb {R} ^{m}\mapsto S^{n}}$

Special case of linear programs

A special case of a semidefinite program is a linear program . To do this, all occurring matrices are replaced by diagonal matrices. This reduces the requirement that positive semidefinite should be , the Frobenius scalar product goes over to the standard scalar product and thus the equation restrictions become a linear system of equations. ${\displaystyle X}$ ${\displaystyle x_{i}\geq 0}$

example

If one wants to find a symmetric matrix for which the sum of the k largest eigenvalues ​​is as small as possible, one can formulate this as a problem of semidefinite programming. In doing so, one minimizes the variable t as the objective function, of which one demands in a secondary condition that it is greater than or equal to the sum of the k largest eigenvalues ​​of X. This constraint is very difficult to handle because there is no easy-to-calculate function that gives the eigenvalues ​​of a matrix, especially not in a sorted form. However, the constraint can be expressed equivalently by the following three conditions:

1. ${\displaystyle t-ks-\mathrm {tr} (Z)\geq 0}$
2. ${\displaystyle Z\succeq 0}$
3. ${\displaystyle Z-X+sE\succeq 0}$.

E is the identity matrix , t and s are real variables, X and Z are matrix variables. These conditions are mathematically easier to deal with, although at first glance they look more difficult. All of them are easy to calculate because they are linear in the variables. Calculating the track is also easy. There are special procedures for checking for positive semi-definiteness for the second and third conditions, which are then used to solve the problem.

duality

Lagrange duality

Is a SDP in normal form given by

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{F}&\\{\text{unter den Nebenbedingungen }}&X\succcurlyeq _{S_{+}^{n}}0&\,{\text{(positive Semidefinitheit)}}\\&\langle {A_{i}},{X}\rangle _{F}=b_{i}&\,{\text{für }}i=1,\dots ,m\end{aligned}}}$,

so the dual problem regarding the Lagrange duality can be formulated as follows. The equation constraints are formulated in order to . This gives us a Lagrange function ${\displaystyle -\langle {A_{i}},{X}\rangle _{F}+b_{i}=0}$

${\displaystyle L(X,\Lambda ,\mu )=\langle {C},{X}\rangle _{F}+\langle {-X},{\Lambda }\rangle _{F}+\sum _{i=1}^{m}\mu _{i}(-\langle {A_{i}},{X}\rangle _{F}+b_{i})}$.

and the dual problem using the self-duality of the semidefinite cone

${\displaystyle {\begin{aligned}{\text{Maximiere }}&\mu ^{T}b\\{\text{unter den Nebenbedingungen }}&\mu _{1}A_{1}+\dots +\mu _{m}A_{m}-\Lambda =-C\\&\Lambda \succcurlyeq _{S_{+}^{n}}0\end{aligned}}}$.

${\displaystyle \Lambda }$acts here as a slip variable. This is an SDP in inequality form. For the exact procedure see Lagrange duality of conical programs .

Analogous to the conical programs, one also obtains the dual problem of an SDP in inequality form

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(x)=c^{T}x\\{\text{unter den Nebenbedingungen }}&x_{1}A_{1}+\dots +x_{m}A_{m}\preccurlyeq _{S_{+}^{n}}B\end{aligned}}}$

the SDP in normal form

${\displaystyle {\begin{aligned}{\text{Maximiere }}&s(\Lambda )=-\langle {\Lambda },{B}\rangle _{F}&\\{\text{unter den Nebenbedingungen }}&\Lambda \succcurlyeq _{S_{+}^{n}}&\\&\langle {\Lambda },{A_{i}}\rangle _{F}=-c_{i}&i=1,\dots ,m\end{aligned}}}$,

Thus the SDPs are closed with regard to the Lagrange duality and the dual problem of the dual problem is always the primal problem again. In addition, the weak duality always applies , i.e. the objective function value of the dual problem is always smaller than the objective function value of the primal problem. If the Slater condition is also fulfilled (see below), then the strong duality applies , the optimal values ​​of the primal and the dual problem therefore agree.

Duality of conical programs

If SDPs are understood as abstract conical programs, then the linear subspace can be described by the linear function described above . It is then exactly the solution set of the equation . Thus, the primal conical problem can be written as SDP in normal form. ${\displaystyle {\mathcal {L}}}$ ${\displaystyle L:S^{n}\mapsto \mathbb {R} ^{m}}$ ${\displaystyle L(X)=0}$

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{F}\\{\text{unter den Nebenbedingungen }}&X\succcurlyeq _{S_{+}^{n}}0\\&L(X)-b=0\end{aligned}}}$

Here is . The orthogonal space required for the dual problem is then described by the operator to be adjoint , which is defined by . Thus the conical dual problem is: ${\displaystyle L(B)=b}$ ${\displaystyle L}$ ${\displaystyle L^{*}:\mathbb {R} ^{m}\mapsto S^{n}}$ ${\displaystyle L^{*}(x)=x_{1}A_{1}+\dots +x_{m}A_{m}}$

${\displaystyle {\begin{aligned}{\text{Minimiere }}&s(Y)=\langle {B},{Y}\rangle _{F}\\{\text{unter den Nebenbedingungen }}&Y\succcurlyeq _{S_{+}^{n}}0\\&Y=L^{*}(y)+C,\,y\in \mathbb {R} ^{m}\end{aligned}}}$.

The dual problem is then an SDP in the form of an inequality with a slip variable. It then always applies to all permissible ones ${\displaystyle X,Y}$

${\displaystyle \langle {C},{X}\rangle _{F}+\langle {B},{Y}\rangle _{F}\geq \langle {B},{C}\rangle _{F}}$

If the Slater condition is fulfilled (see below) and the primal problem has a finite optimal value , then the dual problem has an optimal solution and it holds ${\displaystyle p^{*}}$ ${\displaystyle Y^{*}}$

${\displaystyle p^{*}+\langle {B},{Y^{*}}\rangle _{F}=\langle {B},{C}\rangle _{F}}$.

Slater condition

The Slater condition is a requirement of the primal problem that guarantees that strong duality holds. It requires that the problem has a point which satisfies the equation constraints and strictly satisfies all inequality constraints, that is, or for at least one point in all inequality constraints of the problem simultaneously. But since if is, which in turn is equivalent to being a positively definite matrix, the Slater condition for SDPs is already fulfilled if there is a positively definite matrix that fulfills the secondary equation conditions. ${\displaystyle f(x)\prec _{K}0}$ ${\displaystyle f(x)\succ _{K}0}$ ${\displaystyle x}$ ${\displaystyle X\succ _{S_{+}^{n}}0}$ ${\displaystyle X\in \operatorname {Int} (S_{+}^{n})}$ ${\displaystyle X}$

literature

• Florian Jarre, Josef Stoer: Optimization. Springer, Berlin 2004, ISBN 3-540-43575-1 .
• Johannes Jahn: Introduction to the Theory of Nonlinear Optimization. 3. Edition. Springer, Berlin 2007, ISBN 978-3-540-49378-5 .

Individual evidence

1. ↑ Florian Jarre, Josef Stoer: Optimization. Springer, Berlin 2004, p. 419.

Web links

• Christoph Helmberg: Page with many additional links ( English ) Retrieved on July 19, 2008.