Semidefinite programming: Difference between revisions

Revision as of 15:31, 15 January 2024

Revision as of 23:24, 19 June 2025

(7 intermediate revisions by 5 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 |lastlast1=Gärtner |firstfirst1=Bernd |title=Semidefinite Programming |date=2012 |url=https://doi.org/10.1007/978-3-642-22015-9_2 |work=Approximation Algorithms and Semidefinite Programming |pages=15–25 |editor-last=Gärtner |editor-first=Bernd |access-date=2023-12-31 |place=Berlin, Heidelberg |publisher=Springer |language=en |doi=10.1007/978-3-642-22015-9_2 |isbn=978-3-642-22015-9 |last2=Matoušek |first2=Jiří |editor2-last=Matousek |editor2-first=Jiri|url-access=subscription }}</ref>

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. RecentlySubsequently, Prasad Raghavendra has developed a general framework for constraint satisfaction problems based on the [[unique games conjecture]].<ref>{{Cite book|chapter-url=http://doi.acm.org/10.1145/1374376.1374414|doi=10.1145/1374376.1374414|chapter=Optimal algorithms and inapproximability results for every CSP?|title=Proceedings of the fortieth annual ACM symposium on Theory of computing|year=2008|last1=Raghavendra|first1=Prasad|pages=245–254|isbn=9781605580470|s2cid=15075197}}</ref>

=== Other 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 [[Linear matrix inequality|LMIs]], and in inverse elliptic coefficient problems as convex, non-linear, semidefiniteness constraints.<ref>{{citation |last1=Harrach |first1=Bastian |title=Solving an inverse elliptic coefficient problem by convex non-linear semidefinite programming |date=2021 |journal=Optimization Letters |volume=16 |issue=5 |pages=1599–1609 |language=en |arxiv=2105.11440 |doi=10.1007/s11590-021-01802-4 |s2cid=235166806}}</ref> It is also widely used in physics to constrain [[Conformal field theory|conformal field theories]] with the [[conformal bootstrap]].<ref>{{cite journal |last=Simmons-Duffin |first=David |date=2015-02-06 |title=A Semidefinite Program Solver for the Conformal Bootstrap |journal=Journal of High Energy Physics |volume=2015 |issue=6 |page=174 |arxiv=1502.02033 |bibcode=2015JHEP...06..174S |doi=10.1007/JHEP06(2015)174 |s2cid=256009551}}</ref>

== Run-tinetime complexity ==

The '''semidefinite feasibility problem''' (SDF) is the following [[decision problem]]: given an SDP, decide whether it has at least one feasible solution. The exact run-time complexity of this problem is unknown (as of 1997). However, Ramana proved the following:<ref name=":1" />

* In the [[Turing machine]] model, SDF is in NP iff it is in co-NP. Therefore, SDF is not NP-complete unless NP=coNP.

* In the [[Blum–Shub–Smale machine]] model, SDF is in the intersection of NP sndand co-NP.

== Algorithms for solving SDPs ==

== Approximation algorithms ==

There are several types of algorithms for approximately solving SDPs. These algorithms output the value of the SDP up to an additive error <math>\epsilon</math> in time that is polynomial in the program description size and <math>\log (1/\epsilon)</math>.

=== Ellipsoid method ===

Line 247:

Note that, in general, ''R'' may be doubly-exponential in ''n.'' In that case, the run-time guarantee of the ellipsoid method is exponential in ''n''. But in most applications, ''R'' is not so huge. In these cases, the ellipsoid method is the only known method that guarantees polynomial runtime in the Turing machine model.''<ref name=":0" />''{{Rp|___location=|page=23}} But in practice, its performance is not so good.

=== Hazan's algorithm ===

[[Elad Hazan]]<ref>{{Cite journal |last=Hazan |first=Elad |date=2008 |editor-last=Laber |editor-first=Eduardo Sany |editor2-last=Bornstein |editor2-first=Claudson |editor3-last=Nogueira |editor3-first=Loana Tito |editor4-last=Faria |editor4-first=Luerbio |title=Sparse Approximate Solutions to Semidefinite Programs |url=https://link.springer.com/chapter/10.1007/978-3-540-78773-0_27 |journal=LATIN 2008: Theoretical Informatics |series=Lecture Notes in Computer Science |language=en |___location=Berlin, Heidelberg |publisher=Springer |pages=306–316 |doi=10.1007/978-3-540-78773-0_27 |isbn=978-3-540-78773-0}}</ref> has developed a simple algorithm for solving SDPs with the additional constraint that the [[Trace (linear algebra)|trace]] of the variables matrix must be 1. Specifically, his algorithm solves problems of the form:

<math>

\begin{array}{rl}

{\displaystyle\max_{X \in \mathbb{S}^n}} & \langle C, X \rangle \\

\text{subject to} & \langle A_k, X \rangle \leq b_k, \quad k = 1,\ldots,m \\

& \operatorname{trace}(X) = 1,

\\

& X \succeq 0.

\end{array}

</math>

This can be seen as a maximizing a linear objective over the [[spectraplex]].

Let OPT be the optimal value of this problem, and ''ε>''0 a constant. Hazan's algorithm returns one of the following:''<ref name=":0" />''{{Rp|___location=Thm.5.1.1|page=}}

* A matrix in the spectraplex such that <math>

OPT - \langle C,X\rangle \leq 2\epsilon \cdot \|C\| \text{ and } \langle A_i , X\rangle - bi \leq \epsilon\cdot \|A_i\|

</math> (that is, the solution is approximately optimal and satisfies the linear inequalities approximately);

* A certificate that there is no feasible solution.

The run-time in the [[Real RAM]] model is, [[with high probability]], in <math>

O\left (\frac{N \cdot \log{n}\cdot \log{m} \cdot log(1/\epsilon)}{\epsilon^3}\right)

</math>, where ''N'' is input size (number of nonzero entries in the matrices), ''n'' is the number of variables, and ''m'' is the number of inequality constraints. Note that the runtime is polynomial in 1/''ε'' rather than log(1/''ε''). However, in practice it runs quite fast.

Hazan's algorithm uses a sub-routine for solving the '''feasibility problem''' - deciding whether a given SDP is feasible:<blockquote><math>

\begin{array}{rl}

{\displaystyle \text{find } {X \in \mathbb{S}^n}} & \\

\text{subject to} & \langle A_k, X \rangle \leq b_k, \quad k = 1,\ldots,m \\

& \operatorname{trace}(X) = 1,

\\

& X \succeq 0.

\end{array}

</math></blockquote>There is an algorithm that, for any given ''ε>''0, returns one of the following:''<ref name=":0" />''{{Rp|___location=Thm.5.3.2|page=}}

* An ''ε''-approximately-feasible solution: a solution ''X'' in the spectraplex, for which <math>

\langle A_i , X\rangle - bi \leq \epsilon

</math> for all ''i'' in 1,...,''m''.

* A certificate that no feasible solution exists.

The run-time in the [[Real RAM]] model is, [[with high probability]], in <math>

O\left (\frac{N \cdot \log{n}\cdot \log{m} \cdot }{\epsilon^3}\right)

</math>. The algorithm is applied in a [[binary search]] style to find an approximately-optimal solution.

=== Interior point methods ===

Line 313 ⟶ 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 book |last=Hazan |first=Elad |date=2008 |editor-last=Laber |editor-first=Eduardo Sany |editor2-last=Bornstein |editor2-first=Claudson |editor3-last=Nogueira |editor3-first=Loana Tito |editor4-last=Faria |editor4-first=Luerbio |chapter=Sparse Approximate Solutions to Semidefinite Programs |chapter-url=https://link.springer.com/chapter/10.1007/978-3-540-78773-0_27 |title=LATIN 2008: Theoretical Informatics |series=Lecture Notes in Computer Science |volume=4957 |language=en |___location=Berlin, Heidelberg |publisher=Springer |pages=306–316 |doi=10.1007/978-3-540-78773-0_27 |isbn=978-3-540-78773-0}}</ref> has developed an approximate algorithm for solving SDPs with the additional constraint that the [[Trace (linear algebra)|trace]] of the variables matrix must be 1.

== Preprocessing algorithms ==