5.7.1. Modeling for Semi-Definite Programming

To better understand its mathematical formulation, let’s start with the linear programming (LP) and gradually extend to SDP.

In LP, the objective is to minimize (or sometimes maximize) a linear objective function under linear equality and inequality constraints. A linear program in the standard form can be expressed as:

\[\begin{split}\min \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]^T \in\mathbb{R}^n\) is the decision variable,

• \(\mathbf{c}=[c_1,c_2,\cdots,c_n]^T \in\mathbb{R}^n\) is the linear coefficient in the objective function,

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

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

• The equation \(\mathbf{x}\ge 0\) means \(x_k\ge 0, \forall k\in[n]\), i.e., \(\mathbf{x}\in\mathbb{R}^{n}_+\) is in the non-negative orthant.

Note that each LP in the general form as Modeling for Linear Programming can be transferred into a standard-form LP.

SDP is an extension of LP, with a very similar form:

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

where,

• \(\mathbf{X}\in\mathbb{S}^n\) is the decision variable and \(\mathbb{S}^n\) means \(n\times n\) real symmetric matrix.

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

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

  \[\begin{split}\mathcal{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\) is a given coefficient matrix and \(\langle\mathbf{A}_k, \mathbf{X}\rangle=\mathrm{trace}(\mathbf{A}_k^T \mathbf{X})\). Therefore, the constraint \(\mathcal{A}(\mathbf{X})=\mathbf{b}\) is actually \(\langle \mathbf{A}_k,\mathbf{X}\rangle=b_k\), \(\forall k\in[m]\).

• The expression \(\mathbf{X}\succeq 0\) means \(\mathbf{X}\) is a positive semidefinite (PSD) matrix, i.e., \(\mathbf{X}\in\mathbb{S}^n_+\), where \(\mathbb{S}^n_+\) means a collection of \(n\times n\) positive semidefinite matrix. Specifically, \(\mathbf{X}\in\mathbb{S}^n,\) if any condition listed below is satisfied \(\mathbf{X}\in\mathbb{S}^n_+\):

  1. all eigenvalues are non-negative;

  2. the real number \(\mathbf{a}^T \mathbf{Xa}\) is non-negative for all \(\mathbf{a}\in\mathbb{R}^n;\)

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

To summarize, LP is about finding the optimal solution \(\mathbf{x}^\ast\) with the minimum value of \(\langle \mathbf{c},\mathbf{x}^\ast\rangle=\mathbf{c}^T \mathbf{x^\ast}\) from the intersection of all non-negative vectors \(\mathbf{x}\in\mathbb{R}^{n}_+\) and the solutions to the linear equations \(\{\mathbf{x}:\mathbf{Ax}=\mathbf{b}\}\). While SDP aims to find the optimal solution with the minimum value from the intersection of the PSD cone \(\mathbb{S}^n_+\) and the set of solutions to linear equations \(\{\mathbf{X}:\mathcal{A}(\mathbf{X})=\mathbf{b}\}\).

5.7.1.1. Examples of semidefinite programming

We will consider two examples of SDP, one with a single block and another with multiple blocks of variables. We will demonstrate how to model and optimize these two problems using MindOpt.

5.7.1.1.1. SDP Example I

\[\begin{split}\begin{align*} \max\quad & \langle \mathbf{C},\mathbf{X} \rangle \\ \text { s.t. }\quad & \langle \mathbf{A},\mathbf{X} \rangle = 1 \\ & \mathbf{X} \succeq 0\\ \end{align*}\end{split}\]

where,

\[\begin{split}\mathbf{C} = \begin{bmatrix} -3 & 0 & 1 \\ 0 & -2 & 0 \\ 1 & 0 & -3 \end{bmatrix},\end{split}\]

and

\[\begin{split}\mathbf{A} = \begin{bmatrix} 3 &0 & 1 \\ 0 & 4 & 0 \\ 1 & 0 &5 \end{bmatrix}.\end{split}\]

5.7.1.1.2. SDP Example II

\[\begin{split}\max\quad & \langle \mathbf{C}_0,\mathbf{X}_0 \rangle +\langle \mathbf{C}_1,\mathbf{X}_1 \rangle \\ \text { s.t. }\quad & \langle \mathbf{A}_{00},\mathbf{X}_0 \rangle + x_0 = 1 \\ & \langle \mathbf{A}_{11},\mathbf{X}_1 \rangle + x_1 = 2 \\ & \mathbf{X}_0, \mathbf{X}_1\succeq 0\\ & x_0, x_1 \geq 0\end{split}\]

where,

• \[\begin{split}\begin{align*} \mathbf{C}_0 = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix} \end{align*},\end{split}\]
• \[\begin{split}\begin{align*} \mathbf{C}_1 = \begin{bmatrix} 3 & 0 & 1 \\ 0 & 2 & 0 \\ 1 & 0 & 3 \end{bmatrix} \end{align*},\end{split}\]
• \[\begin{split}\begin{align*} \mathbf{A}_{00} = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix} \end{align*},\end{split}\]
• \[\begin{split}\begin{align*} \mathbf{A}_{11} = \begin{bmatrix} 3 &0 & 1 \\ 0 & 4 & 0 \\ 1 & 0 &5 \end{bmatrix} \end{align*}.\end{split}\]

In the above SDP instance, variables \(\mathbf{X}_0, \mathbf{X}_1\) are refered to as matrix variables or PSD variables since they represent matrices that must be PSD, while variables \(x_0, x_1\) are termed linear variables as they are subject to certain linear constraints. Meanwhile, the expression \(\langle \mathbf{A}_{00},\mathbf{X}_0 \rangle\) is named as a matrix term in the first linear constraint, while \(x_0\) is named as a linear term. Any constraint containing at least one PSD variable are termed a PSD constraint.

We will provide example codes of how MindOpt models and solves the above SDP problems in different programming languages.