Semidefinite programming: Difference between revisions

Revision as of 21:21, 16 May 2022

Revision as of 11:10, 10 June 2022

Line 90:

=== Strong duality ===

Under a condition known as [[Slater's condition]],When the value of the primal and dual SDPs are equal., the ThisSDP is knownsaid asto satisfy the [[strong duality]] property. Unlike for [[Linear programming|linear programs]], howeverwhere every dual linear program has optimal objective equal to the primal objective, not every SDP satisfies strong duality; in general, the value of the dual SDP may lie strictly below the value of the primal., and the P-SDP and D-SPD satisfy the following properties:

Under a condition known as [[Slater's condition]], the value of the primal and dual SDPs are equal. This is known as [[strong duality]]. Unlike for [[Linear programming|linear programs]], however, not every SDP satisfies strong duality; in general, the value of the dual SDP may lie strictly below the value of the primal.

(i) Suppose the primal problem (P-SDP) is bounded below and strictly

Line 106 ⟶ 105:

Then there is an optimal solution <math>X^*</math> to (P-SDP) and

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>{{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 |issn=0025-5610}}</ref>

== Examples ==