Semidefinite Programming Quick notes
Conic Programming
Conic optimization is a subfield of convex optimization that studies problems consisting of minimizing a convex function over the intersection of an affine subspace and a convex cone.
convex cone: In linear algebra, a cone—sometimes called a linear cone to distinguish it from other sorts of cones—is a subset of a real vector space that is closed under positive scalar multiplication That is \(C\) is a cone if \(x\in C\) implies \(s x \in C\) for every \(s>0\).
- A convex cone is a cone that is also closed under addition, or, equivalently, a subset of a vector space that is closed under linear combinations with positive coefficients. It follows that convex cones are convex sets.
- The conical hull of a set \(C\) is defined as the smallest convex cone that contains \(C \cup \{0\}\). Therefore, it need not be the smallest cone that contains \(C \cup \{0\}\).
The class of conic optimization problems includes some of the most well known classes of convex optimization problems, namely linear and semidefinite programming.
Definition
Given a real vector space X, a convex, real-valued function:
\(f \colon C \mapsto \mathbb{R}\) defined on a convex cone \(C \subset X\), and an affine subspace \(\cal{H}\) defined by a set of affine constraints \(h_i (x) =0\), a conic optimization problem is to find the point \(x \in C \cap \cal{H}\) for which the number \(f(x)\) is minimized.
- Example of \(C\) include the positive orthant \(\mathbb{R}_+^n \colon =\{x \in \mathbb{R}^n \colon x \geq 0\}\), positive semidefinite matrices \(\mathbb{S}_+^n\).
- Often \(f\) is a linear function, in which case the conic optimization problem reduces to a linear program, a semidefinite program, respectively.
Semidefinite Programming
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 of positive semidefinite matrices with an affine space, i.e., a spectrahedron.
- A spectrahedron is a shape that can be represented as a linear matrix inequality.
Initial motivation
In semidefinite programming, we use real-valued vectors and are allowed to take the dot product of vectors with semi-definiteness constraints on matrix variables.
\[\min_{x^1, ... , x^n \in \mathbb{R}^n} \sum_{i,j \in [n]} c_{i,j} (x^i \cdot x^j)\] \[\text{subject to } \sum_{i,j \in [n]} a_{i,j,k} (x^i \cdot x^j) \leq b_k \quad \forall k.\]Equivalent formulations
Use the gram matrix of some vectors \(X \colon = [x^i \cdot x^j]\). We can rewrite the mathematical program given in the previous section equivalently as:
\[\min_{X\in \mathbb{S}^n} \langle C, X\rangle\] \[\text{subject to } X \succeq \mathbf{0}, \langle A_k, X\rangle \leq b_k \quad \forall k.\]Duality Theory
Analogously to linear programming, given a general SDP of the form
\[\min_{X\in \mathbb{S}^n} \langle C, X\rangle\] \[\text{subject to } X \succeq \mathbf{0}, \langle A_k, X\rangle \leq b_k \quad \forall k.\](The primal problem of P-SDP), we define the dual semidefinite program (D-SDP) as
\[\max_{y \in \mathbb{R}^n} b^\top y\] \[\text{subject to } \sum_{i = 1}^m y_i A_i \preceq C.\]- Weak duality always holds, which means any feasible solution to the dual SDP lower-bounds the primal SDP value, and conversely, any feasible solution to the primal SDP upper-bounds the dual SDP value.
- Strong Duality doens’t hold always, which differs from the LP(linear programming). A sufficient condition for strong duality is the Slater’s condition.