5.4.1. 半定规划建模¶
Note
本页公式多，打开慢，请等待公式显示正常后阅读。
关于半定规划（Semi-Definite Programming，SDP）问题，可参看 博文 了解更详细介绍和应用场景与求解方法。
其数学表达形式，为了方便理解，我们从最基础的线性规划讲起，慢慢推广到半定规划。
对于线性规划，它是一个在线性等式和不等式约束下的最小化 (有时或最大化) 线性目标函数的优化问题，同 线性规划建模 ，将该线性规划公式转为标准形式，则数学公式如下：
其中
\(\mathbf{x}=[x_1,x_2,\cdots,x_n]^\top\in\mathbb{R}^n\) 是优化变量，
\(\mathbf{c}=[c_1,c_2,\cdots,c_n]^\top\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}^\top\mathbf{x^\ast}\) 的最优解 \(\mathbf{x}^\ast\)。
半定规划是线性规划的推广，具有非常相似的数学标准形式：
其中
\(\mathbf{X}\in\mathbb{S}^n\) 为优化变量，这里 \(\mathbb{S}^n\) 表示所有的 \(n\times n\) 对称矩阵的集合。
\(\mathbf{b}\in\mathbb{R}^m\) 是线性等式约束的常数项。
\(\mathscr{A}:\mathbb{S}^n \to \mathbb{R}^m\) 是线性等式约束中的算子，其定义为：
\[\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}\]这里 \(\mathbf{A}_k\in\mathbb{S}^n, k\in[m]\) 是给定的系数矩阵。
因此线性等式约束 \(\mathscr{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}^\top\mathbf{Xa}\ge0,\forall\mathbf{a}\in\mathbb{R}^n;\)
\(\mathbf{X}=\mathbf{UU}^\top,\exists \mathbf{U}\in\mathbb{R}^{n\times n}\)。
同理，半定规划是从 \(\mathbb{S}^n_+\) 与线性等式解的交集中找到具有最小值 \(\langle\mathbf{C},\mathbf{X}^\ast\rangle=\mathrm{trace}(\mathbf{C}^\top\mathbf{X^\ast})\) 的最优解 \(\mathbf{X}^\ast\)。