5.4.1. Semidefinite Programming Modeling

Note

There are many formulas in this page, which is slow to open. Please wait for the formulas to display normally before reading.

For the semi-definite programming (SDP) problem, please refer to the blog blog for a more detailed introduction, application scenarios, and solution methods.

To make the mathematical expression of SDP easier to understand, we start with the basic linear programming (LP), and gradually extend it to SDP.

For LP, it is a constrained optimization problem of minimizing (or sometimes maximizing) a linear objective function under linear equality and inequality constraints, for example, Modeling for linear programming. The standard form of LP formula is shown as follows:

\[\begin{split}\operatorname*{min}_{\mathbf{x}} \quad& \langle\mathbf{c}, \mathbf{x} \rangle \\ \text {s.t.} \quad & \mathbf{Ax}=\mathbf{b}, \\ & \mathbf{x} \geq {0},\end{split}\]

where

  • \(\mathbf{x}=[x_1,x_2,\cdots,x_n]^\top\in\mathbb{R}^n\) is a decision variable,

  • \(\mathbf{c}=[c_1,c_2,\cdots,c_n]^\top\in\mathbb{R}^n\) is a coefficient vector in the target function,

  • \(\mathbf{A}\in\mathbb{R}^{m\times n}\) is a constraint matrix,

  • \(\mathbf{b}\in\mathbb{R}^m\) is a constant vector in the constraint,

  • the inequality \(\mathbf{x}\ge 0\) means \(x_k\ge 0, \forall k\in[n]\) . That is, \(\mathbf{x}\in\mathbb{R}^{n}_+\), which is the non-negative quadrant of \(\mathbb{R}^n\).

Briefly, this goal of the linear programming problem is to find the minimum \(\langle \mathbf{c},\mathbf{x}^\ast\rangle=\mathbf{c}^\top\mathbf{x^\ast}\) and the corresponding optimal solution of \(\mathbf{x}^\ast\) from the intersection of all non-negative vectors and solutions of linear equations.

SDP is a generalization of LP and has a very similar mathematical form:

\[\begin{split}\operatorname*{min}_{\mathbf{X}} \quad& \langle\mathbf{C}, \mathbf{X} \rangle \\ \text {s.t.} \quad & \mathscr{A}(\mathbf{X})=\mathbf{b} \\ & \mathbf{X} \succeq {0}\end{split}\]

where

  • \(\mathbf{X}\in\mathbb{S}^n\) is a decision variable， and \(\mathbb{S}^n\) denotes the set of symetric n times n matrices,

  • \(\mathbf{b}\in\mathbb{R}^m\) is a constant term in equality constraint.

  • \(\mathscr{A}:\mathbb{S}^n \to \mathbb{R}^m\) is an operator in linear equality constraint, which is defined as:

    \[\begin{split}\mathscr{A}(\mathbf{X}) =\begin{bmatrix} \langle \mathbf{A}_1, \mathbf{X} \rangle \\ \vdots \\ \langle \mathbf{A}_m, \mathbf{X} \rangle \end{bmatrix}\end{split}\]

    where \(\mathbf{A}_k\in\mathbb{S}^n, k\in[m]\) is a given coefficient matrix.

    Therefore, the k-th row of the linear equality constraint \(\mathscr{A}(\mathbf{X})=\mathbf{b}\) is \(\langle \mathbf{A}_k,\mathbf{X}\rangle=b_k\), \(\forall k\in[m]\).

  • The generalized inequality \(\mathbf{X}\succeq 0\) means \(\mathbf{X}\) is a positive semidefinite (PSD) symmetric matrix, that is \(\mathbf{X}\in\mathbb{S}^n_+\), where \(\mathbb{S}^n_+\) denotes the set of positive semidefinite (PSD) symmetric \(n\times n\) matrices. Specifically, for any symmetric matrix \(\mathbf{X},\) it is PSD if any of the following conditions \(\mathbf{X}\in\mathbb{S}^n_+\) is satisfied:

    1. all its eigenvalues are real and non-negative;

    2. all its quadratic form are non-negative: \(\mathbf{a}^\top\mathbf{Xa}\ge0,\forall\mathbf{a}\in\mathbb{R}^n;\)

    3. \(\mathbf{X}=\mathbf{UU}^\top,\exists \mathbf{U}\in\mathbb{R}^{n\times n}\)。

Similarly, the SDP problem is to find optimal solutions \(\mathbf{X}^\ast\) from the intersection of all PSD matrices and solutions of linear equations.