Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function over the intersection of the cone of positive semidefinite matrices with an affine space. 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, SDP's are used in the context of linear matrix inequalities. SDPs are in fact a special case of cone programming and can be efficiently solved by interior point methods. All linear programs can be expressed as SDPs, and via hierarchies of SDPs the solutions of polynomial optimization problems can be approximated. Finally, semidefinite programming can aid in the design of quantum computing circuits, which makes it interesting as a future subject.
Contents |
Definition
Standard form
The standard form of a semidefinite programming problem consists of the following three parts (where tr denotes the trace) :
- A linear function <math>\mathrm{tr}\ (CX)</math> to be minimized over the matrix variable <math>X</math>
- Equality constraints of the form <math>\mathrm{tr}\ (A_i X) = b_i,\quad i=1,\dots,p</math>, where each <math>A_i</math> is a matrix and <math>b_i \ </math> is a scalar.
- Semi-definiteness of the matrix variable, i.e. <math>X \geq0</math>
A semidefinite program is thus written as minimize <math>\mathrm{tr}\ (CX)\ </math> subject to
- <math>\mathrm{tr}\ (A_i X) = b_i,\quad i=1,\dots,p</math>
- <math>X \geq0</math>
where <math>C , \ A_1 ,\dots,A_p \in\mathbb{S}^n </math> are the problem parameters.
Inequality form
SDPs can also be written in inequality form, in which case the optimization variable <math>x</math> is in <math>\mathbb{R}^n</math>. The problem has the form minimize <math>c^T x</math> subject to
- <math>x_1 F_1 + \cdots + x_n F_n + G \leq 0</math>
- <math> Ax = b \ </math>
where <math>G, \ F_1,\dots,F_n \in \mathbb{S}^k </math> and <math>A\in\mathbb{R}^{p\times n} </math>. Here the inequality is a linear matrix inequality.
Duality
The dual of a semidefinite program in inequality form, minimize <math>c^T x</math> subject to
- <math>x_1 F_1 + \cdots + x_n F_n + G \leq 0</math>
- <math> Ax = b \ </math>
is given by maximize <math>\mathrm{tr}\ (GZ)\ </math> subject to
- <math>\mathrm{tr}\ (F_i Z) +c_i =0,\quad i=1,\dots,n</math>
- <math>Z \geq0</math>
Examples
Example 1
Consider three random variables <math>A</math>, <math>B</math>, and <math>C</math>. By definition, their correlation coefficients <math>\rho_{AB}, \ \rho_{AC}, \rho_{BC} </math> are valid if and only if
- <math>\begin{pmatrix}
1 & \rho_{AB} & \rho_{AC} \\
\rho_{AB} & 1 & \rho_{BC} \\
\rho_{AC} & \rho_{BC} & 1
\end{pmatrix} \succeq 0</math> Suppose that we know from some prior knowledge (empirical results of an experiment, for example) that <math>-0.2 \leq \rho_{AB} \leq -0.1</math> and <math>0.4 \leq \rho_{BC} \leq 0.5</math>. The problem of determining the smallest and largest values that <math>\rho_{AC} \ </math> can take is given by:
- minimize/maximize <math>x_{13}</math>
- subject to
- <math>-0.2 \leq x_{12} \leq -0.1</math>
- <math>0.4 \leq x_{23} \leq 0.5</math>
- <math>x_{11} = x_{22} = x_{33} = 1 \ </math>
- <math>\begin{pmatrix}
1 & x_{12} & x_{13} \\
x_{12} & 1 & x_{23} \\
x_{13} & x_{23} & 1
\end{pmatrix} \succeq 0</math> we set <math>\rho_{AB} = x_{12}, \ \rho_{AC} = x_{13}, \ \rho_{BC} = x_{23} </math> to obtain the answer. This can be formulated by an SDP. We handle the inequality constraints by augmenting the variable matrix and introducing slack variables, for example <math>\mathrm{tr}\left(\left(\begin{array}{cccccc} 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\end{array}\right)\cdot\left(\begin{array}{cccccc} 1 & x_{12} & x_{13} & 0 & 0 & 0\\ x_{12} & 1 & x_{23} & 0 & 0 & 0\\ x_{13} & x_{23} & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & s_{1} & 0 & 0\\ 0 & 0 & 0 & 0 & s_{2} & 0\\ 0 & 0 & 0 & 0 & 0 & s_{3}\end{array}\right)\right)=x_{12} + s_{1}=-0.1</math> Solving this SDP gives the minimum and maximum values of <math>\rho_{AC} = x_{13} \ </math> as <math>-0.978</math> and <math> 0.872 </math> respectively.
Example 2
Consider the problem
- minimize <math>\frac{(c^T x)^2}{d^Tx} </math>
- subject to <math>Ax +b\geq 0</math>
where we assume that <math>d^Tx>0</math> whenever <math>Ax+b\geq 0</math>. Introducing an auxiliary variable <math>t</math> the problem can be reformulated:
- minimize <math>t</math>
- subject to <math>Ax+b\geq 0, \, \frac{(c^T x)^2}{d^Tx}\leq t</math>
In this formulation, the objective is a linear function of the variables <math>x,t</math>. The first restriction can be written as
- <math>\textbf{diag}(Ax+b)\geq 0</math>
where the matrix <math>\textbf{diag}(Ax+b)</math> is the square matrix with values in the diagonal equal to the elements of the vector <math>Ax+b</math>. The second restriction can be written as
- <math>td^Tx-(c^Tx)^2\geq 0</math>
or equivalently
- det<math>\underbrace{\left[\begin{array}{cc}t&c^Tx\\c^Tx&d^Tx\end{array}\right]}_{D}\geq 0</math>
Thus <math>D\geq 0</math>. The semidefinite program associated with this problem is
- minimize <math>t</math>
- subject to <math>\left[\begin{array}{ccc}\textbf{diag}(Ax+b)&0&0\\0&t&c^Tx\\0&c^Tx&d^Tx\end{array}\right]\geq 0</math>
Algorithms
Interior point methods
There are two types of algorithms for solving SDPs. One is the interior point methods, the other one is spacialized general convex optimization algorithms.
Bundle method
Software
The following codes are available for SDP: SDPA, CSDP, SDPT3, SeDuMi, DSDP, PENSDP, SDPLR, SBmeth SeDuMi runs on MATLAB and uses the Self-Dual method for solving general convex optimization problems.
Applications
Semidefinite programming has been applied to find approximate solutions to combinatorial optimization problems, such as the solution of the max cut problem with an approximation ratio of 0.87856. SDPs are also used in geometry to determine tensegrity graphs, and arise in control theory as LMIs.
Open problems
See also
References
- Lieven Vandenberghe, Stephen Boyd, "Semidefinite Programming", SIAM REVIEW, March 1996.
- Monique Laurent, Franz Rendl, "Semidefinite Programming and Integer Programming".
External links
- Software
