Content deleted Content added
m Fix linking to Hazan |
m Open access bot: url-access updated in citation with #oabot. |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 1:
{{Short description|Subfield of convex optimization}}
'''Semidefinite programming''' ('''SDP''') is a subfield of [[mathematical programming]] 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 (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]].<ref name=":0">{{Citation |
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]].
Line 108:
the equality from (i) holds.
A sufficient condition for strong duality to hold for a SDP problem (and in general, for any convex optimization problem) is the [[Slater's condition]]. It is also possible to attain strong duality for SDPs without additional regularity conditions by using an extended dual problem proposed by Ramana.<ref name=":1">{{Cite journal |last=Ramana |first=Motakuri V. |date=1997 |title=An exact duality theory for semidefinite programming and its complexity implications |url=http://link.springer.com/10.1007/BF02614433 |journal=Mathematical Programming |language=en |volume=77 |issue=1 |pages=129–162 |doi=10.1007/BF02614433 |s2cid=12886462 |issn=0025-5610|url-access=subscription }}</ref><ref>{{Cite journal |last1=Vandenberghe |first1=Lieven |last2=Boyd |first2=Stephen |date=1996 |title=Semidefinite Programming |url=http://epubs.siam.org/doi/10.1137/1038003 |journal=SIAM Review |language=en |volume=38 |issue=1 |pages=49–95 |doi=10.1137/1038003 |issn=0036-1445|url-access=subscription }}</ref>
== Examples ==
Line 208:
This is an SDP because the objective function and constraints are all linear functions of vector inner products. Solving the SDP gives a set of unit vectors in <math>\mathbf{R^n}</math>; since the vectors are not required to be collinear, the value of this relaxed program can only be higher than the value of the original quadratic integer program. Finally, a rounding procedure is needed to obtain a partition. Goemans and Williamson simply choose a uniformly random hyperplane through the origin and divide the vertices according to which side of the hyperplane the corresponding vectors lie. Straightforward analysis shows that this procedure achieves an expected ''approximation ratio'' (performance guarantee) of 0.87856 - ε. (The expected value of the cut is the sum over edges of the probability that the edge is cut, which is proportional to the angle <math>\cos^{-1}\langle v_{i}, v_{j}\rangle</math> between the vectors at the endpoints of the edge over <math>\pi</math>. Comparing this probability to <math>(1-\langle v_{i}, v_{j}\rangle)/{2}</math>, in expectation the ratio is always at least 0.87856.) Assuming the [[unique games conjecture]], it can be shown that this approximation ratio is essentially optimal.
Since the original paper of Goemans and Williamson, SDPs have been applied to develop numerous approximation algorithms.
=== Other applications ===
Line 268:
=== Approximate methods ===
Algorithms that solve SDPs approximately have been proposed as well. The main goal of such methods is to achieve lower complexity in applications where approximate solutions are sufficient and complexity must be minimal. A prominent method that has been used for data detection in multiple-input multiple-output (MIMO) wireless systems is Triangular Approximate SEmidefinite Relaxation (TASER),<ref>{{Cite journal|last1=Castañeda|first1=O.|last2=Goldstein|first2=T.|last3=Studer|first3=C.|date=December 2016|title=Data Detection in Large Multi-Antenna Wireless Systems via Approximate Semidefinite Relaxation|journal=IEEE Transactions on Circuits and Systems I: Regular Papers|volume=63|issue=12|pages=2334–2346|doi=10.1109/TCSI.2016.2607198|arxiv=1609.01797|hdl=20.500.11850/448631|issn=1558-0806|doi-access=free}}</ref> which operates on the Cholesky decomposition factors of the semidefinite matrix instead of the semidefinite matrix. This method calculates approximate solutions for a max-cut-like problem that are often comparable to solutions from exact solvers but in only 10-20 algorithm iterations. [[Elad Hazan|Hazan]]<ref>{{Cite
== Preprocessing algorithms ==
| |||