Content deleted Content added
Erel Segal (talk | contribs) No edit summary |
Erel Segal (talk | contribs) No edit summary |
||
Line 103:
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}}</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}}</ref>
== Examples ==
Line 208:
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>
==
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" />
There are several types of algorithms for 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>.▼
* 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 snd co-NP.
== 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 ===
| |||