Semidefinite programming: Difference between revisions

Revision as of 06:12, 27 January 2025

Latest revision as of 09:31, 27 August 2025

(One intermediate revision by one other user 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 |last1=Gärtner |first1=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 211:

=== 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 |pagearticle-number=174 |arxiv=1502.02033 |bibcode=2015JHEP...06..174S |doi=10.1007/JHEP06(2015)174 |s2cid=256009551}}</ref>

== Run-time complexity ==

Line 249:

=== Interior point methods ===

Most codes are based on [[interior point methods]] (CSDP, [[MOSEK]], SeDuMi, [https://www.math.cmu.edu/~reha/sdpt3.html SDPT3], DSDP, SDPA). These are robust and efficient for general linear SDP problems, but restricted by the fact that the algorithms are second-order methods and need to store and factorize a large (and often dense) matrix. Theoretically, the state-of-the-art high-accuracy SDP algorithms<ref>{{Cite book |last1=Jiang |first1=Haotian |last2=Kathuria |first2=Tarun |last3=Lee |first3=Yin Tat |last4=Padmanabhan |first4=Swati |last5=Song |first5=Zhao |title=2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) |chapter=A Faster Interior Point Method for Semidefinite Programming |date=November 2020 |chapter-url=https://ieeexplore.ieee.org/document/9317892 |___location=Durham, NC, USA |publisher=IEEE |pages=910–918 |doi=10.1109/FOCS46700.2020.00089 |arxiv=2009.10217 |isbn=978-1-7281-9621-3|s2cid=221836388 }}</ref><ref>{{Cite arXiv |last1=Huang |first1=Baihe |last2=Jiang |first2=Shunhua |last3=Song |first3=Zhao |last4=Tao |first4=Runzhou |last5=Zhang |first5=Ruizhe |date=2021-11-18 |title=Solving SDP Faster: A Robust IPM Framework and Efficient Implementation |class=math.OC |eprint=2101.08208}}</ref> are based on this approach.

=== First-order methods ===

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|bibcode=2016ITCSR..63.2334C |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 ==