Content deleted Content added
Erel Segal (talk | contribs) No edit summary |
Erel Segal (talk | contribs) |
||
Line 51:
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).
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.
When the matrix ''C'' is diagonal, the inner products <''C'',''X''> is equivalent to a vector product of the diagonal of ''C'' and the diagonal of ''X''. Analogously, when the matrices ''A<sub>k</sub>'' are diagonal, the corresponding inner products are equivalent to vector products. In these vector products, only the diagonal elements of ''X'' are used, so we can add constraints equating the non-diagonal elements of ''X'' to 0. The condition <math>X \succeq 0</math> is then equivalent to the condition that all diagonal elements of ''X'' are non-negative. Then, the resulting SDP becomes a [[linear program]] in which the variables are the diagonal elements of ''X''.
== Duality theory ==
| |||