半正定规划

半正定规划（Semidefinite programming，SDP）是凸优化问题的一个分支，它具有线性目标函数（由用户指定的最大化或最小化函数），且其定义在半正定矩阵构成的凸锥与仿射空间的交集上，即光谱面。

在最佳化理论中，半正定规划是一个相对较年轻的领域，并且基于各种原因，学界不断的增加对它的兴趣：许多作业研究和组合最佳化的问题都能建模成半正定规划问题，或以半正定规划的方式得到近似解；在自动控制理论中，半正定规划用于处理线性矩阵不等式。此外，半正定规划是锥规划的特例，因此实际上可以内点法快速解掉。所有线性规划问题都可以表示成半正定规划，此外，多项式最佳化问题的解也可以透由半正定规划逼近。

半正定规划经常用于处理复杂系统的最佳化，而近年来，量子查询复杂性理论的问题也经常被建模成半正定规划。

动机与定义

初始动机

一个线性规划问题是要求在一个多面体上最大或最小化一个实数值线性函数；在半正定规划问题中，则是将线性规划的实变数改成向量内积。以数学的语言来说，一般的半正定规划问题可以被表示成以下型式：

${\begin{array}{rl}{\displaystyle \min _{x^{1},\ldots ,x^{n}\in \mathbb {R} ^{n}}}&{\displaystyle \sum _{i,j=1}^{n}c_{i,j}(x^{i}\cdot x^{j})}\\{\text{subject to}}&{\displaystyle \sum _{i,j=1}^{n}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}},\quad k=1,\ldots ,m\\\end{array}}$

其中 $c_{i,j}$、$a_{i,j,k}$ 和 $b_{k}$ 是实数，$x^{i}\cdot x^{j}$ 是 $x^{i}$ 和 $x^{j}$ 的内积，subject to 后面是需满足的限制式。

等价描述

从上节中看不出半正定这个名称从何而来，事实上，从下面的等价描述会发现，半正定这个词来自于将线性规划中的实变数的非负限制式改为矩阵变数的半正定限制式。

定义一个 $n\times n$ 矩阵 $M$ 是半正定的，若其为一些向量的格拉姆矩阵，换言之，存在向量 $x^{1},\ldots ,x^{n}$ 使得对所有 $i$、$j$ 都有 $m_{i,j}=x^{i}\cdot x^{j}$。若上述发生，则记做 $M\succeq 0$。此外，半正定矩阵还有许多常见的等价定义，例如，一个半正定矩阵是对称的，并且所有特征值都是非负的。

将 $\mathbb {S} ^{n}$ 设为收集所有对称矩阵所形成的空间，并且在空间上赋予内积

$\langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\sum _{i,j=1}^{n}A_{ij}B_{ij}$

其中 ${\rm {tr}}$ 代表矩阵的迹。

因此上节的半正定规划可以改写成

${\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\&X\succeq 0\end{array}}$

注意到原本的性质不保证 $C$ 和 $A_{k}$ 是对称的，因此必需它们对称化：将 $C$ 的第 $i,j$ 项修正成 ${\frac {c_{i,j}+c_{j,i}}{2}}$，将 $A_{k}$ 的第 $i,j$ 项修正成 ${\frac {a_{i,j,k}+a_{j,i,k}}{2}}$。如此一来，上述的内积就会是良好定义的。

如果适度的添加松弛变量，半正定规划可以被写成

${\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{k},X\rangle _{\mathbb {S} ^{n}}=b_{k},\quad k=1,\ldots ,m\\&X\succeq 0\end{array}}$

此外如果得出上述形式的最佳解 $X^{*}$，将其还原成原本名命题的最佳解 ${x^{1}}^{*},\ldots ,{x^{n}}^{*}$ 只需耗费至多 $O(n^{3})$ 的时间。有众多算法可以办到以上过程，例如科列斯基分解是其中一个较为常见的。

其他变形

有时为了方便，会不妨稍微修改半正定规划的形式。举例来说，如果想要在 $\langle C,X\rangle _{\mathbb {S} ^{n}}$ 后面加 $l$ 几项非负变数，只要将 $X$ 扩充成 $(n+l)\times (n+l)$ 矩阵，并且添加额外条件 $X_{ij}=0$ 对所有 $j\neq i>n$。

对偶理论

主条目：对偶性 (最佳化)

定义

与线性规划相似的，一个形式如

${\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{i},X\rangle _{\mathbb {S} ^{n}}=b_{i},\quad i=1,\ldots ,m\\&X\succeq 0\end{array}}$

的半正定规划问题被称为原问题；不过对偶问题的形式就与原问题不大相同，写作

${\begin{array}{rl}{\displaystyle \max _{y\in \mathbb {R} ^{m}}}&\langle b,y\rangle _{\mathbb {R} ^{m}}\\{\text{subject to}}&{\displaystyle \sum _{i=1}^{m}}y_{i}A_{i}\preceq C\end{array}}$

其中两个矩阵 $P$、$Q$ 被写成 $P\succeq Q$ 的意思是 $P-Q\succeq 0$。

弱对偶性

半正定规划的弱对偶定理是说，对偶问题的最大值必然小于等于原问题的最小值，因此，任何对偶问题的可行解都是原问题的一个下界，反之，任何原问题的可行解也都是对偶问题的一个上界。具体的原因是如果 $X$ 和 $y$ 分别是原问题和对偶问题的其中一个可行解，则有

${\begin{aligned}\langle C,X\rangle -\langle b,y\rangle &=\langle C,X\rangle -\sum _{i=1}^{m}y_{i}b_{i}\\&=\langle C,X\rangle -\sum _{i=1}^{m}y_{i}\langle A_{i},X\rangle =\langle C-\sum _{i=1}^{m}y_{i}A_{i},X\rangle \geq 0\end{aligned}}$

其中最后一个不等式成立的原因是两个半正定矩阵的内积是非负的。

原问题和对偶问题的值的差距常被称为对偶间隙。

强对偶性

与线性规划不同的是，不是所有的半正定规划问题都有强对偶性，有时候对偶问题的值会严格小于原问题的值。不过，强对偶定理叙述说，如果半正定规划满足斯莱特条件，则原问题和对偶问题的值会相同，换言之，没有对偶间隙。更确切的说明如下

(一) 若原问题有下界，并且有严格可行解，也就是存在正定的对称矩阵 $X_{0}$ 使得 $\langle A_{i},X_{0}\rangle _{\mathbb {S} ^{n}}=b_{i}$ 对所有 $i=1,\ldots ,m$，则原问题存在最佳解 $X^{*}$、对偶问题存在最佳解 $y^{*}$，且

$\langle C,X^{*}\rangle _{\mathbb {S} ^{n}}=\langle b,y^{*}\rangle _{\mathbb {R} ^{m}}$

(二) 若对偶问题有上界，并且有严格可行解，也就是存在 $y^{0}\in \mathbb {R} ^{m}$ 使得 $\sum _{i=1}^{m}y_{i}^{0}A_{i}\prec C$，则原问题存在最佳解 $X^{*}$、对偶问题存在最佳解 $y^{*}$，且

$\langle C,X^{*}\rangle _{\mathbb {S} ^{n}}=\langle b,y^{*}\rangle _{\mathbb {R} ^{m}}$

例子

例一

考虑三个随机变数 $A$, $B$ 和 $C$，那么根据定义，它们两两之间的相关系数 $\rho _{AB},\ \rho _{AC},\rho _{BC}$ 的所有可能性恰好就是所有满足

${\begin{pmatrix}1&\rho _{AB}&\rho _{AC}\\\rho _{AB}&1&\rho _{BC}\\\rho _{AC}&\rho _{BC}&1\end{pmatrix}}\succeq 0,$

的 $\rho _{AB}$，$\rho _{BC}$、$\rho _{AC}$，而式子的左手边称作相关矩阵。

假设根据实验或其他经验法则得知 $-0.2\leq \rho _{AB}\leq -0.1$ 及 $0.4\leq \rho _{BC}\leq 0.5$，想得知 $\rho _{AC}\$ 的可能极大极小值则只需将 $\rho _{AB}$，$\rho _{BC}$、$\rho _{AC}$ 分别设为变数 $x_{12}$、$x_{23}$、$x_{13}$，并解下面的半正定规划原问题

${\begin{array}{rl}{\displaystyle \min /\max }&x_{13}\\{\text{subject to}}&-0.2\leq x_{12}\leq -0.1\\&0.4\leq x_{23}\leq 0.5\\&{\displaystyle {\begin{pmatrix}1&x_{12}&x_{13}\\x_{12}&1&x_{23}\\x_{13}&x_{23}&1\end{pmatrix}}\succeq 0}\end{array}}$

通过求解半正定规划问题可以得出 $\rho _{AC}=x_{13}\$ 的最大最小值分别约等于 0.872 与 -0.978。

例二

假设当 $Ax+b\geq 0$ 时，恒有 $d^{\top }x>0$。考虑下述问题

${\begin{array}{rl}{\displaystyle \min }&{\displaystyle {\frac {(c^{\top }x)^{2}}{d^{\top }x}}}\\{\text{subject to}}&{\displaystyle Ax+b\geq 0}\\\end{array}}$

引入一个任意实变数 $t$，并将问题化成

${\begin{array}{rl}{\displaystyle \min }&{\displaystyle t}\\{\text{subject to}}&\displaystyle Ax+b\geq 0,\\&\displaystyle {\frac {(c^{\top }x)^{2}}{d^{\top }x}}\leq t\\\end{array}}$

在这个形式中，目标函数已是 $x$ 和 $t$ 的线性函数，因此仅剩下限制式待处理。

第一条限制式等价于

${\textbf {diag}}(Ax+b)\succeq 0$

其中 ${\textbf {diag}}(Ax+b)$ 代表对角线是 $Ax+b$ 的对角矩阵。

而第二条限制式则等价于

$td^{\top }x-(c^{\top }x)^{2}\geq 0$

若将 $D$ 定义为

$D=\left[{\begin{array}{cc}t&c^{T}x\\c^{T}x&d^{T}x\end{array}}\right]$

那么第二条限制式又等价于

$D\succeq 0$

总的来说，原先的问题可以被化约成

${\begin{array}{rl}{\displaystyle \min }&{\displaystyle t}\\{\text{subject to}}&\displaystyle {\displaystyle \left[{\begin{array}{ccc}{\textbf {diag}}(Ax+b)&0&0\\0&t&c^{\top }x\\0&c^{\top }x&d^{\top }x\end{array}}\right]\succeq 0}\\\end{array}}$

经过仔细观察可以发现，上述形式已是一个半正定规划的对偶问题了。

例三 (格曼–威廉森最大割逼近算法)

半正定规划是解 NP困难的最佳化问题重要的工具，而格曼–威廉森最大割逼近算法是第一个基于半正定规划的逼近算法 (JACM, 1995)。迈克尔·格曼和戴维·保罗·威廉森的研究聚焦在最大割问题：给定一个图 $G=(V,E)$，目标是将顶点集 $V$ 分割成两个互斥部分，使得横跨两部分的边的个数达到最大值。

该问题可以被表示成以下的整数二次规划问题：

${\begin{array}{rl}\displaystyle \max &\displaystyle \sum _{(i,j)\in E}{\frac {1-v_{i}v_{j}}{2}}\\{\text{such that }}&v_{i}\in \{1,-1\}{\text{ for all }}i\end{array}}$

由于二次规划问题是NP困难的，除非证明 P = NP，否则上述整数二次规划的最佳值是不可能在多项式时间内被解出的。然而格曼和威廉森经由尝试得出处理这类问题的三步骤方针：

1. 将整数二次规划问题先放松成半正定规划问题。
2. 解半正定规划问题 (可能会与正解有些许误差项 $\epsilon$)。
3. 用半正定规划问题的最佳解回推出一个原先整数二次规划问题的近似解。

对于最大割问题，最自然的办法是放松成以下形式

${\begin{array}{rl}\displaystyle \max &\displaystyle \sum _{(i,j)\in E}{\frac {1-\langle v_{i},v_{j}\rangle }{2}}\\{\text{subject to }}&\lVert v_{i}\rVert ^{2}=1{\text{ for all }}i\end{array}}$

注意到此时的变数 $v_{i}$ 已从整数变成向量了。

因为目标函数及所有线制式都已是向量变数的内积的线性组合，因此此时问题已变成一个半正定规划，而最佳解是一组 $\mathbb {R} ^{n}$ 中的向量。由于这些向量不见得共线性，放松后的半正定规划问题的佳最值必定大于等于原本的整数二次规划问题。格曼和威廉森于此需要采取一个方法将这些向量分成两类：随机生成一个通过原点的超平面，超平面的两侧自然的就将向量分成两类，其中一类在原问题中代表 1，而另一类则代表 -1。可以证明，通过此方式所得到的近似值的其望值至少是真实数值的 0.87856 倍；换言之，当随机取用超平面足够多次，就可以得到至少是真实数值的 0.87856 - ε 倍的近似值。

0.87856 这个数字来自于，两向量 $v_{i}$、$v_{j}$ 会被切在不同的半平面的几率是 ${\frac {\cos ^{-1}\langle v_{i},v_{j}\rangle }{\pi }}$，而此几率与 ${\frac {1-\langle v_{i},v_{j}\rangle }{2}}$ 的比值的最大值就是 0.87856。此外，如果独立游戏猜想是正确的，则也不会有比 0.87856 更佳的方案了。

算法

目前已有许多针对半正规划的算法，而这些算法都是可以规划问题的最佳值带一个误差项 ε，计算都花费问题资讯尺寸与 $\log(1/\epsilon )$ 的多项式时间。

此外有许多对于半正定规划问题的表面预处理算法，这些算法往往都是检查限制式之间的关系，例如消去多余的行或列，或是移除代入最佳解存在时等号不会成立的松弛限制式。如此一来可能可以大大降低问题的资料量。

内点法

内点法是解线性半正定规划对偶问题的一个相对稳健的方法，许多程式码都是根据内点法设计的，如 CSDP、MOSEK、SeDuMi、SDPT3、DSDP 及 SDPA。然而，内点法的缺点是会用到二阶法，而且经常会需要储存和分解矩阵，而且该矩阵往往是稠密而非稀疏的。

一阶法

与内点法不同的，运用锥最佳化的一阶法可以避免储存及分解巨大的黑塞矩阵，然而付出的代价是，要求相同的精确度之下，需要面对更大的尺寸的问题资料。一阶法于分裂锥解算器(SCS) 及交替方向乘子法(ADMM) 中有所应用，其中后者在施行时会将每一步伐走到的新资料投影回半正定矩阵锥。

谱丛分析法

程式锥丛 (ConicBundle) 将半正定规划问题转换成非光滑最佳化问题，并且使用谱丛分析法处理此非光滑问题。这个方法处理特殊种类的半正定规划问题格外的有效率。

其他处理方法

算法 PENSDP 建立在增广拉格朗日惩罚函数法的基础之上，而其表现大致上与内点法相去不远，但是对于某些极大值尺度的问题上处理得非常快速。其他算法诸如 SDPLR 则运用半正定规划的低秩资讯及将该规划重构成一个非线性规划问题。

近似解法

有时只需要一定程度的解的精确度，但是希望可以有计算的复杂度最低值，因此许许多多的近似解法就此应运而生。其中一个重要的方法是应用在多输入多输出系统 (MIMO) 的半正定放松三角近似(TASER)，其特色在于对半正定矩阵的科列斯基分解矩阵而非半正定矩阵本身，处理类似最大割的问题往往只需 10 至 20 次迭代就可得到几乎等于精确解的解答。

应用

除了最大割问题之外，半正定规划在几何上被用来判断一个图是否为张拉整体图，在控制理论中则应用在线性矩阵不等式的相关题材之中。

参考资料

• Lieven Vandenberghe, Stephen Boyd, "Semidefinite Programming", SIAM Review 38, March 1996, pp. 49–95. pdf （页面存档备份，存于互联网档案馆）
• Monique Laurent, Franz Rendl, "Semidefinite Programming and Integer Programming", Report PNA-R0210, CWI, Amsterdam, April 2002. optimization-online （页面存档备份，存于互联网档案馆）
• E. de Klerk, "Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications", Kluwer Academic Publishers, March 2002, ISBN 1-4020-0547-4.
• Robert M. Freund, "Introduction to Semidefinite Programming (SDP), SDP-Introduction （页面存档备份，存于互联网档案馆）

外部链接

• Links to introductions and events in the field（页面存档备份，存于互联网档案馆）
• Lecture notes from László Lovász（页面存档备份，存于互联网档案馆） on Semidefinite Programming