5.4.1. Modeling for Semi-Definite Programming

Note

This page might be displayed slowly due to the large amount of formulas. Please wait for the equations to be displayed properly before reading it.

Please refer to our website to learn more about Semi-Definite Programming (SDP) and its applications and optimization methods.

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 transfered 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.4.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.4.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.4.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.