Semidefinite Programming Task: Difference between revisions
m (Text replacement - ". ----" to ". ----") |
m (Text replacement - "tems]]" to "tem]]s") |
||
Line 16: | Line 16: | ||
* (Wikipedia, 2016) ⇒ http://en.wikipedia.org/wiki/semidefinite_programming Retrieved:2016-1-11. | * (Wikipedia, 2016) ⇒ http://en.wikipedia.org/wiki/semidefinite_programming Retrieved:2016-1-11. | ||
** '''Semidefinite programming''' ('''SDP</B>) is a subfield of [[convex optimization]] concerned with the optimization of a [[linear | ** '''Semidefinite programming''' ('''SDP</B>) is a subfield of [[convex optimization]] concerned with the optimization of a [[linear | ||
objective function]] (an objective function is a user-specified function that the user wants to minimize or maximize) <P> over the intersection of the [[Cone (linear algebra)|cone]] of [[Positive-definite matrix#Negative-definite, semidefinite and indefinite matrices|positive semidefinite]] [[Matrix (mathematics)|matrices]] with an [[affine space]], i.e., a [[spectrahedron]]. <P> 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 inequality|linear matrix inequalities]]. SDPs are in fact a special case of [[conic optimization|cone programming]] and can be efficiently solved by [[interior point methods]]. <P> All [[linear programming|linear 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|optimization of complex | objective function]] (an objective function is a user-specified function that the user wants to minimize or maximize) <P> over the intersection of the [[Cone (linear algebra)|cone]] of [[Positive-definite matrix#Negative-definite, semidefinite and indefinite matrices|positive semidefinite]] [[Matrix (mathematics)|matrices]] with an [[affine space]], i.e., a [[spectrahedron]]. <P> 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 inequality|linear matrix inequalities]]. SDPs are in fact a special case of [[conic optimization|cone programming]] and can be efficiently solved by [[interior point methods]]. <P> All [[linear programming|linear 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|optimization of complex system]]s. In recent years, some quantum query complexity problems have been formulated in term of semidefinite programs. | ||
---- | ---- |
Latest revision as of 21:14, 9 May 2024
A Semidefinite Programming Task is a convex optimization task that accepts a linear objective function over the intersection of the cone of positive semidefinite matrices with an affine space.
- AKA: SDP.
- Context:
- It can be expressed as [math]\displaystyle{ \operatorname{min} C.X }[/math] such that [math]\displaystyle{ A_i X=b_i,i=1,\dots,m \\ X \geq 0 }[/math], where [math]\displaystyle{ C }[/math] is a symmetric matrix, [math]\displaystyle{ C.X }[/math] is a linear objective function, and there are [math]\displaystyle{ m }[/math] linear equations that [math]\displaystyle{ X }[/math] must satisfy, namely [math]\displaystyle{ A_i X = b_i,i =1,...,m. }[/math].
- It can be solved by a Semidefinite Programming Solving System (that implements a [[semidefinite programming solving algorithm, such as a primal-dual algorithm).
- Example(s):
- For [math]\displaystyle{ C=\begin{bmatrix}1 & 2 & 3 \\ 2 & 9 & 0 \\ 3 & 0 & 7\end{bmatrix},A_1=\begin{bmatrix} 1 & 0 & 1 \\ 0 & 3 & 7 \\ 1 & 7 & 5 \end{bmatrix}, A_2=\begin{bmatrix} 0 & 2 & 8 \\ 2 & 6 & 0 \\ 8 & 0 & 4 \end{bmatrix} }[/math] and [math]\displaystyle{ b_1=11, b_2=19 }[/math]. Then the variable [math]\displaystyle{ X }[/math] will be a symmetric matrix: [math]\displaystyle{ X=\begin{bmatrix}x_{11}&x_{12}&x_{13}\\x_{21}&x_{22}&x_{23}\\x_{31}&x_{32}&x_{33}\end{bmatrix},C.X=x_{11}+2x_{12}+3x_{13}+2x_{21}+9x_{22}+0x_{23}+3x_{31}+0x_{32}+7x_{33}=x_{11}+4x_{12}+6x_{13}+9x_{22}+0x_{23}+7x_{33} }[/math]
The SDP can be written as: Minimize [math]\displaystyle{ x_{11}+4x_{12}+6x_{13}+9x_{22}+0x_{23}+7x_{33}\\ s.t. x_{11}+0x_{12}+2x_{13}+3x_{22}+14x_{23}+5x_{33}=11 \\ 0x_{11}+4x_{12}+16x_{13}+6x_{22}+0x_{23}+4x_{33}=19 \\ X=\begin{bmatrix}x_{11}&x_{12}&x_{13}\\x_{21}&x_{22}&x_{23}\\x_{31}&x_{32}&x_{33}\end{bmatrix} \geq 0 }[/math]
- For [math]\displaystyle{ C=\begin{bmatrix}1 & 2 & 3 \\ 2 & 9 & 0 \\ 3 & 0 & 7\end{bmatrix},A_1=\begin{bmatrix} 1 & 0 & 1 \\ 0 & 3 & 7 \\ 1 & 7 & 5 \end{bmatrix}, A_2=\begin{bmatrix} 0 & 2 & 8 \\ 2 & 6 & 0 \\ 8 & 0 & 4 \end{bmatrix} }[/math] and [math]\displaystyle{ b_1=11, b_2=19 }[/math]. Then the variable [math]\displaystyle{ X }[/math] will be a symmetric matrix: [math]\displaystyle{ X=\begin{bmatrix}x_{11}&x_{12}&x_{13}\\x_{21}&x_{22}&x_{23}\\x_{31}&x_{32}&x_{33}\end{bmatrix},C.X=x_{11}+2x_{12}+3x_{13}+2x_{21}+9x_{22}+0x_{23}+3x_{31}+0x_{32}+7x_{33}=x_{11}+4x_{12}+6x_{13}+9x_{22}+0x_{23}+7x_{33} }[/math]
- See: Negative-Definite Matrix, Affine Space, Spectrahedron, Combinatorial Optimization, Linear Matrix Inequality, Conic Optimization.
References
2016
- (Wikipedia, 2016) ⇒ http://en.wikipedia.org/wiki/semidefinite_programming Retrieved:2016-1-11.
- Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a [[linear
objective function]] (an objective function is a user-specified function that the user wants to minimize or maximize)
over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron.
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 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. Semidefinite programming has been used in the optimization of complex systems. In recent years, some quantum query complexity problems have been formulated in term of semidefinite programs.