5.4.1. 半定规划建模¶

Note

本页公式多，打开慢，请等待公式显示正常后阅读。

关于半定规划（Semi-Definite Programming，SDP）问题，可参看官网了解更详细介绍和应用场景与求解方法。

其数学表达形式，为了方便理解，我们从最基础的线性规划讲起，慢慢推广到半定规划。

对于线性规划，它是一个在线性等式和不等式约束下的最小化 (有时或最大化) 线性目标函数的优化问题，同线性规划建模，将该线性规划公式转为标准形式，则数学公式如下：

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

其中

\(\mathbf{x}=[x_1,x_2,\cdots,x_n]^T \in\mathbb{R}^n\) 是优化变量，

\(\mathbf{c}=[c_1,c_2,\cdots,c_n]^T \in\mathbb{R}^n\) 是目标函数向量，

\(\mathbf{A}\in\mathbb{R}^{m\times n}\) 是线性等式约束矩阵，

\(\mathbf{b}\in\mathbb{R}^m\) 是线性等式约束的常数项，

最后，不等式 \(\mathbf{x}\ge 0\) 表示 \(x_k\ge 0, \forall k\in[n]\)。即，\(\mathbf{x}\in\mathbb{R}^{n}_+\) 处于坐标的非负象限。

简单地说，这个线性规划问题是：我们要从所有非负向量与线性等式解的交集中找到具有最小值 \(\langle \mathbf{c},\mathbf{x}^\ast\rangle=\mathbf{c}^T \mathbf{x^\ast}\) 的最优解 \(\mathbf{x}^\ast\)。

半定规划是线性规划的推广，具有非常相似的数学标准形式：

\[\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}\]

其中

\(\mathbf{X}\in\mathbb{S}^n\) 为优化变量，这里 \(\mathbb{S}^n\) 表示所有的 \(n\times n\) 对称矩阵的集合。

\(\mathbf{b}\in\mathbb{R}^m\) 是线性等式约束的常数项。

\(\mathcal{A}:\mathbb{S}^n \to \mathbb{R}^m\) 是线性等式约束中的算子，其定义为：

\[\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}\]

这里 \(\mathbf{A}_k\in\mathbb{S}^n, k\in[m]\) 是给定的系数矩阵。

因此线性等式约束 \(\mathcal{A}(\mathbf{X})=\mathbf{b}\) 即为 \(\langle \mathbf{A}_k,\mathbf{X}\rangle=b_k\), \(\forall k\in[m]\)。

最后，不等式 \(\mathbf{X}\succeq 0\) 表示 \(\mathbf{X}\) 是半正定 (Positive semidefinite, PSD) 对称矩阵，

即 \(\mathbf{X}\in\mathbb{S}^n_+\) 这里 \(\mathbb{S}^n_+\) 表示所有 \(n\times n\) 半正定对称矩阵的集合。

具体来说给定 \(\mathbf{X}\in\mathbb{S}^n,\) 若满足下面任意条件则 \(\mathbf{X}\in\mathbb{S}^n_+\):

所有的特征值皆为非负;

所有的二次式皆为非负: \(\mathbf{a}^T \mathbf{Xa}\ge0,\forall\mathbf{a}\in\mathbb{R}^n;\)

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

同理，半定规划是从 \(\mathbb{S}^n_+\) 与线性等式解的交集中找到具有最小值 \(\langle\mathbf{C},\mathbf{X}^\ast\rangle=\mathrm{trace}(\mathbf{C}^T \mathbf{X^\ast})\) 的最优解 \(\mathbf{X}^\ast\)。

5.4.1.1. 半定规划问题示例¶

我们将考虑两个SDP问题例子，分别为只有一块和多块变量的半定规划问题。我们将展示如何使用 MindOpt 来建模和优化这两个问题。

5.4.1.1.1. SDP示例1¶

\[\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}\]

其中，

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

以及

\[\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示例2¶

\[\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}\]

其中，

\[\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}\]

我们将分别给出不同编程语言下的示例，来展示如何使用 MindOpt 建模和求解上述优化问题。