编者按

介绍了半正定规划的一些应用实例，包括一个基于Julia/JuMP使用Mosek求解器的计算实例。通过本文，你将了解到SDP的理论和从0/1二次规划建模求解的思想。

作者:秦含章

编辑:秦含章

文章发表在微信微信官方账号【策略】:优化|图像理解与半正定编程(SDP)基本原理

一个SDP示例和一些参考资料

SDP有很多有趣的例子，除了线性规划是它的特例，比如李亚普诺夫稳定性，可以用来描述线性系统，近似0/1二次规划的解。可以用来逼近图上独立集)/图的shannon容量，带特征值的优化问题，复数域上的插值问题，欧氏空之间上点的嵌入问题，带矩阵补全/核范数的优化问题。

实际上，SDP作为一种特殊的凸优化问题，具有很强的建模能力。像现在的研究，其实更大的瓶颈是计算，比如如何找到大规模求解SDP的通用算法。虽然SDP在圆锥规划方面与LP相似，但实际上目前对其大致结构还不是很了解。不像实数域上有限维的多面体LP，我们知道它一定是由有限个极值点和极值射线生成的(这也是著名的Minkowski分解定理)，但是我们没有半定锥这样的广义结构定理。

所以不要扯太远，这里我就不一一回答了，因为如果你想知道如何使用SDP对上述问题进行建模并近似求解，看一些参考文献就能很快有更好的理解。下面先推荐几本参考书。

对SDP零基础，但是有一点凸优化基础的同学(没有优化基础的会从Boyd和Vandenberg He的凸优化书开始)可以从Robert Freund的这本讲义开始SDP入门，非常简洁，包含了丰富的例子。

《半定规划(SDP)简介》,作者Robert Freund

(https://OCW . MIT . edu/courses/electrical-engineering-and-computer-science/6-251j-introduction-to-***the***tical-programming-fall-2009/readings/MIT 6 _ 251 JF 09 _ SDP . pdf)

数学比较好的同学，尤其是代数比较好的同学，想投身于SDP的理论研究，可以学习巴勃罗·帕里洛等人的参考书。

半定优化与凸代数

几何学(http://***.mit.edu/~parrilo/sdocag/index.html)

在帕里洛教授的主页上还有一门课程6.256/18.456 –一些代数技巧和半定义程序设计的讲义和作业材料可以用来辅助学习。作为SDP应用的一个例子，矩阵补全问题在我之前的知乎回答中也有简要介绍:

矩阵补全的经典算法有哪些？目前流行的算法是什么？(
https://*** . zhi Hu . com/question/47716840/answer/110843844)

关于SDP如何逼近独立集，以及SDP与共正程序的关系，请参考我之前的知乎文章:

https://shimo.im/docs/J7JWAF7FSHQJM3NR/read张钦:协同编程简介

然后我们以SDP最重要的应用之一为例，讨论如何理解二元二次规划(BQP)中的SDP，以及如何利用SDP导出近似算法。其余的内容基本上来自Parrilo教授的讲义资料。

二元二次规划与半正定松弛

对于n维半定矩阵q，bq的一般形式是:

那么注意，这里的约束实际上可以写成n个二次方程x = 1，也就是说，原问题实际上可以看成一个连续优化问题，一个多项式优化问题。

关于对偶形式，当然最直接的推法是通过对原SDP (P) 使用拉格朗日对偶。那么这边我们其实可以稍微灵活一些，我们可以直接对原来的BQP问题进行所谓的拉格朗日松弛（Lagrangian relaxation），这样让大家可以更深刻的体会拉格朗日对偶可以用来一般化地对（非凸）连续最小化优化问题求出一个下界。关于对偶的形式，当然最直接的推导是对原SDP (P)使用拉格朗日对偶。那么我们实际上可以更灵活一点。我们可以直接对原BQP问题进行所谓的拉格朗日松弛，从而更深刻地理解拉格朗日对偶在一般情况下可以用来寻找(非凸)连续极小化优化问题的一个下界。

而这就是我们面前的对偶形式(D)！

在这一节的最后，我们给出了另一种概率解释。这个解释是针对SDP在原空中的表达，也就是说和前面的提升解释更相关。我们考虑到我们并没有确定地找到最优的X，只是说我们需要随机选择X，这样我们就可以期望我们的结果会更好。那么我们BQP的目标函数就变成了

基于三个SDP的BQP近似算法的界:戈曼斯-威廉姆森，内斯特罗夫，格罗滕迪克-克里万

然后我们意识到这里的Q其实有更好的结构。比如理论上它有一个很好的特性:对角占优，这使得我们的BQP的目标函数有一个可分的结构。

戈曼斯-威廉姆森舍入法是将SDP松弛得到的解(可能是分数)舍入到-1或1。这是SDP的早期阶段，包括迄今为止最成功、最漂亮的应用之一。因为你知道，在1995年他们的论文发表之前，人们的非SDP方法最好只能达到0.5的逼近，并且“卡”了很多年。他们基于SDP的方法一下子突破了原来的0.5到0.878左右。

即我们基于SDP的Goe***ns-Williamson rounding能给我们期望上约0.878的一个近似算法！也就是我们基于SDP的Goe***ns-Williamson舍入可以给我们一个大概0.878的近似算法！

注意这边的结果比之前是要糟糕的，因为左边是个等号。另外，不那么容易注意的一点是，前面两种rounding如果碰到SDP直接给出了一个全是 ±1 的解（最优解），rounding是不会干扰这个解的（虽然值可能会变，但仍然是最优的），而这边的话，即使已经有了一个最优解，一旦这个Grothen***ck-Krivine rounding一用上马上就会把解变差！ （具体原因留给大家思考）注意，这里的结果比之前更差，因为左边有一个等号。另外，不那么容易注意到，如果前两种舍入直接给出一个全为1的解(最优解)，舍入不会干扰这个解(虽然值可能变化，但仍然是最优的)。在这方面，即使已经有一个最优解，一旦使用格罗滕迪克-克里万舍入，它将立即恶化解决方案！(具体原因留给大家思考)

让我在这里跑题，格罗滕迪克(是的，你知道神一样的格罗滕迪克。当然，名字出现在这里的每个人都足够惊艳。)这里出现的相关著作当然不是针对BQP和SDP的(SDP的理论当时根本不存在)。他只是在年轻的时候一边做分析一边做出了这样的结果。它后来被Krivine采用，并用于这种二分结构的BQP问题。为了给出充分的格罗滕迪克信用，这里的相关常数称为格罗滕迪克常数。

对本节介绍的分析的完整细节感兴趣的同学可以参考Parrilo的相关讲义和书籍，或者实际上有一本非常难的凸优化讲义(我所知道的所有凸优化教材中最难的:现代曲线优化讲座，作者Aharon Ben-Tal和Arka di Nemirowski)以及其中引用的相关文献。

广义BQP问题的G-W舍入计算一例

注意我们进行10000次抽样，看看结果。我们取10000个样本，看看结果。

左边q .的密集实验结果:朴素算法；右:G-W舍入

那么我们确实看到G-W舍入得到的结果比naive的好得多。在我的实验中，G-W舍入的最优解的目标函数值是-5563.56，而naive的算法最好在一万次后得到一个-1500左右的函数值。而且在1万个样本的情况下，我们的样本均值和理论均值也非常接近。在我的实验中，naive算法的样本均值和理论均值分别是16.21和19.26，而G-W舍入的样本均值和理论均值分别是-4879.23和-4880.3(所以图上基本有一条线，肉眼看不出两者的差距)。

最后我们也看看G-W舍入对于稀疏Q和低秩Q的表现，从下图可以看出，G-W舍入给出的解都是挤在一起的！(当然一万次实验也不是完全一样的解，只是>:95%都一样，所以直方图用肉眼崩成了光杆…)

稀疏Q的实验(这里选择三对角对称矩阵)

具有低等级Q(这里等级1)的实验

其实这个结果应该是符合直觉的，这里的具体原因就留给你自己考虑了。提示:考虑这种情况下超平面真正需要的维数？