Content deleted Content added
Citation bot (talk | contribs) Alter: title, template type. Add: volume, chapter-url, chapter, authors 1-1. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Real algebraic geometry | #UCB_Category 11/43 |
m Open access bot: url-access updated in citation with #oabot. |
||
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 ==
| |||