Content deleted Content added
Erel Segal (talk | contribs) No edit summary |
Erel Segal (talk | contribs) No edit summary |
||
Line 50:
For convenience, an SDP may be specified in a slightly different, but equivalent form. For example, linear expressions involving nonnegative [[scalar (mathematics)|scalar]] variables may be added to the program specification. This remains an SDP because each variable can be incorporated into the matrix <math>X</math> as a diagonal entry (<math>X_{ii}</math> for some <math>i</math>). To ensure that <math>X_{ii} \geq 0</math>, constraints <math>X_{ij} = 0</math> can be added for all <math>j \neq i</math>. As another example, note that for any positive semidefinite matrix <math>X</math>, there exists a set of vectors <math>\{ v_i \}</math> such that the <math>i</math>, <math>j</math> entry of <math>X</math> is <math>X_{ij} = (v_i, v_j)</math> the [[dot product|scalar product]] of <math>v_i</math> and <math>v_j</math>. Therefore, SDPs are often formulated in terms of linear expressions on scalar products of vectors. Given the solution to the SDP in the standard form, the vectors <math>\{ v_i \}</math> can be recovered in <math>O(n^3)</math> time (e.g., by using an incomplete [[Cholesky decomposition]] of X).
=== Relation to cone programming ===
The space of semidefinite matrices is a [[convex cone]]. Therefore, SDP is a special case of [[conic optimization]], which is a special case of convex optimization.
== Duality theory ==
| |||