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_+\):

    1. 所有的特征值皆为非负;

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

    3. \(\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\)

Note

MindOpt 也支持求解不等式约束的半正定规划问题。

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 建模和求解上述优化问题。