Content deleted Content added
Erel Segal (talk | contribs) Add book link |
Erel Segal (talk | contribs) No edit summary |
||
Line 1:
{{Short description|Subfield of convex optimization}}
'''Semidefinite programming''' ('''SDP''') is a subfield of [[convex optimization]] 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 |last=Gärtner |first=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}}</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 195:
<!-- this section is linked to from [[Randomized_rounding]], please update that link there if you change the section title here --nealeyoung May 31, 2010 -->
Semidefinite programs are important tools for developing approximation algorithms for NP-hard maximization problems. The first approximation algorithm based on an SDP is due to [[Michel Goemans]] and [[David P. Williamson]] (JACM, 1995).<ref name=":0" />{{Rp|___location=Chap.1}} They studied the [[Maximum cut|max cut problem]]: Given a [[Graph (discrete mathematics)|graph]] ''G'' = (''V'', ''E''), output a [[Partition of a set|partition]] of the vertices ''V'' so as to maximize the number of edges crossing from one side to the other. This problem can be expressed as an [[Quadratic programming|integer quadratic program]]:▼
▲Semidefinite programs are important tools for developing approximation algorithms for NP-hard maximization problems. The first approximation algorithm based on an SDP is due to [[Michel Goemans]] and [[David P. Williamson]] (JACM, 1995). They studied the [[Maximum cut|max cut problem]]: Given a [[Graph (discrete mathematics)|graph]] ''G'' = (''V'', ''E''), output a [[Partition of a set|partition]] of the vertices ''V'' so as to maximize the number of edges crossing from one side to the other. This problem can be expressed as an [[Quadratic programming|integer quadratic program]]:
:Maximize <math>\sum_{(i,j) \in E} \frac{1-v_{i} v_{j}}{2},</math> such that each <math>v_i\in\{1,-1\}</math>.
Line 210 ⟶ 209:
Since the original paper of Goemans and Williamson, SDPs have been applied to develop numerous approximation algorithms. Recently, 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 ===
== Algorithms ==▼
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
▲== Algorithms for solving SDPs ==
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>.
There are also facial reduction algorithms that can be used to preprocess SDPs problems by inspecting the constraints of the problem. These can be used to detect lack of strict feasibility, to delete redundant rows and columns, and also to reduce the size of the variable matrix.<ref>{{citation|last1=Zhu|first1=Yuzixuan|last2=Pataki|first2=Gábor|last3=Tran-Dinh|first3=Quoc|date=2019|title=Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs|url=http://link.springer.com/10.1007/s12532-019-00164-4|journal=Mathematical Programming Computation|language=en|volume=11|issue=3|pages=503–586|doi=10.1007/s12532-019-00164-4|issn=1867-2949|arxiv=1710.08954|s2cid=53645581}}</ref>▼
=== Interior point methods ===
Line 237:
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.
== Preprocessing algorithms ==
'''Facial reduction algorithms''' are algorithms used to preprocess SDPs problems by inspecting the constraints of the problem. These can be used to
▲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|date=2021|title=Solving an inverse elliptic coefficient problem by convex non-linear semidefinite programming|journal=Optimization Letters|volume=16 |issue=5 |pages=1599–1609 |language=en|doi=10.1007/s11590-021-01802-4|arxiv=2105.11440|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 |doi=10.1007/JHEP06(2015)174 |arxiv=1502.02033 |bibcode=2015JHEP...06..174S |s2cid=256009551 }}</ref>
* Detect lack of strict feasibility;
* Delete redundant rows and columns;
▲
== References ==
| |||