Semidefinite programming

From Wikipedia, the free encyclopedia

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.

1 Definition
- 1.1 Standard form
- 1.2 Inequality form
2 Duality
3 Examples
- 3.1 Example 1
- 3.2 Example 2
4 Algorithms
- 4.1 Interior point methods
- 4.2 Bundle method
5 Software
6 Applications
7 Open problems
8 See also
9 References
10 External links

[edit] Definition

[edit] Standard form

The standard form of a semidefinite programming problem consists of the following three parts:

A linear function $\mathrm{tr}\ (CX)$ to be minimized over the matrix variable $X$
Equality constraints of the form $\mathrm{tr}\ (A_i X) = b_i,\quad i=1,\dots,p$ , where each $A i$ is a matrix and $b_i \$ is a scalar.
Semi-definiteness of the matrix variable, i.e. $X \geq0$

A semidefinite program is thus written as

minimize $\mathrm{tr}\ (CX)\$ subject to

$\mathrm{tr}\ (A_i X) = b_i,\quad i=1,\dots,p$

$X \geq0$

where $C , \ A_1 ,\dots,A_p \in\mathbb{S}^n$ are the problem parameters.

[edit] Inequality form

SDPs can also be written in inequality form, in which case the optimization variable $x$ is in $\mathbb{R}^n$ . The problem has the form

minimize $c^T x \$ subject to

$x_1 F_1 + \cdots + x_n F_n + G \leq 0$

$Ax = b \$

where $G, \ F_1,\dots,F_n \in \mathbb{S}^k$ and $A\in\mathbb{R}^{p\times n}$ . here the inequality is a linear matrix inequality.

[edit] Duality

The dual of a semidefinite program in inequality form,

minimize $c^T x \$ subject to

$x_1 F_1 + \cdots + x_n F_n + G \leq 0$

$Ax = b \$

is given by

maximize $\mathrm{tr}\ (GZ)\$ subject to

$\mathrm{tr}\ (F_i Z) +c_i =0,\quad i=1,\dots,n$

$Z \geq0$

[edit] Examples

[edit] Example 1

Consider three random variables $A \$ , $B \$ , and $C \$ . By definition, their correlation coefficients $\rho_{AB}, \ \rho_{AC}, \rho_{BC}$ are valid if and only if

$\begin{pmatrix} 1 & \rho_{AB} & \rho_{AC} \\ \rho_{AB} & 1 & \rho_{BC} \\ \rho_{AC} & \rho_{BC} & 1 \end{pmatrix} \succeq 0$

Suppose that we know from some prior knowledge (empirical results of an experiment, for example) that $-0.2 \leq \rho_{AB} \leq -0.1$ and $0.4 \leq \rho_{BC} \leq 0.5$ . The problem of determining the smallest and largest values that $\rho_{AC} \$ can take is given by:

minimize/maximize $x_{23} \$

subject to

$-0.2 \leq x_{12} \leq -0.1$

$0.4 \leq x_{23} \leq 0.5$

$x_{11} = x_{22} = x_{33} = 1 \$

$\begin{pmatrix} 1 & x_{12} & x_{13} \\ x_{12} & 1 & x_{23} \\ x_{13} & x_{23} & 1 \end{pmatrix} \succeq 0$

we set $\rho_{AB} = x_{12}, \ \rho_{AC} = x_{13}, \ \rho_{BC} = x_{23}$ 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

$\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$

Solving this SDP gives the minimum and maximum values of $\rho_{AC} = x_{13} \$ as $- 0.978$ and $0.872$ respectively.

[edit] Example 2

Consider the problem

minimize $\frac{(c^T x)^2}{d^Tx}$

subject to $Ax +b\geq 0$

where we assume that $d T x > 0$ whenever $Ax+b\geq 0$ .

Introducing an auxiliary variable $t$ the problem can be reformulated:

minimize

t

subject to $Ax+b\geq 0, \, \frac{(c^T x)^2}{d^Tx}\leq t$

In this formulation, the objective is a linear function of the variables $x, t$ .

The first restriction can be written as

$\textbf{diag}(Ax+b)\geq 0$

where the matrix $\textbf{diag}(Ax+b)$ is the square matrix with values in the diagonal equal to the elements of the vector $A x + b$ .

The second restriction can be written as

$td^Tx-(c^Tx)^2\geq 0$

or equivalently

det $\underbrace{\left[\begin{array}{cc}t&c^Tx\\c^Tx&d^Tx\end{array}\right]}_{D}\geq 0$

Thus $D\geq 0$ .

The semidefinite program associated with this problem is

minimize

t

subject to $\left[\begin{array}{ccc}\textbf{diag}(Ax+b)&0&0\\0&t&c^Tx\\0&c^Tx&d^Tx\end{array}\right]\geq 0$

[edit] Algorithms

[edit] Interior point methods

There are two types of algorithms for solving SDPs. One is the interior point methods, the other one is spacialzed general convex optimization algorithms.

[edit] Bundle method

[edit] Software

The following codes are available for SDP:

SDPA, CSDP, SDPT3, SeDuMi, DSDP, PENSDP, SDPLR, SBmeth

[edit] 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.

[edit] Open problems

[edit] See also

Sum of squares

[edit] References

Lieven Vandenberghe, Stephen Boyd, "Semidefinite Programming", SIAM REVIEW, March 1996.

Monique Laurent, Franz Rendl, "Semidefinite Programming and Integer Programming".

[edit] External links

Christoph Helmberg's page giving links to introductions and events in the field

Software

Retrieved from "http://en.wikipedia.org../../../s/e/m/Semidefinite_programming.html"

Categories: Optimization | Operations research