半正定二次规划半正定规划松弛 _半正定规划松弛

文章插图

文章插图
编者按
本文介绍半正定规划（SDP）的一些应用实例，也包含了一个基于Julia/JuMP使用Mosek求解器的计算实例。通过这篇文章，你将从0/1二次规划出发，了解SDP的理论和建模求解思路。

文章作者：覃含章
责任编辑：覃含章
文章发表于微信公众号【运筹OR帷幄】：优化 | 半正定规划(SDP)的形象理解和基本原理

一SDP实例和一些参考资料
SDP有很多有意思的实例，除了作为其特例的线性规划（linear programming），比如可以用来刻画线性系统（linear system）的李雅普诺夫稳定性(Lyapunov stability)，可以用来近似0/1二次规划（binary quadratic programming）的解，可以用来近似求解图上的独立集（independent set）/图的shannon capacity，带有特征值的优化问题（eigenvalue optimization），复数域上的插值（interpolation）问题，欧式空间上点的embedding问题，近似求解矩阵补全/带有nucelar norm的优化问题。
实际上，SDP作为一类特殊的凸优化问题，有很强的modeling能力。作为目前的研究来说其实更大的瓶颈是在计算，如如何找到泛用的大规模求解SDP的算法。因为虽然SDP从conic programming的角度来说和LP很像，但是实际上目前对它的一般结构并没有很好的了解。不像LP，一个实数域上finite dimensional的polyhedron我们是知道一定由有限个extreme points和extreme rays生成的（这也是著名的Minkowski Resolution Theorem），但对semidefinite cone我们就没有这样一般化的结构性定理。
那么不扯远了，我这边就不再一个个例子回答，因为如果想要了解如何用SDP去model上述的那些问题并近似求解，看一些参考文献就很快能比较好的了解了。这里先推荐一些参考读物。
对SDP零基础，但有一点点凸优化基础的同学（毫无优化基础的同学就先从Boyd, Vandenberghe的凸优化书入手）都可以从这份Robert Freund的讲义入门SDP，内容非常简明精悍，同时包含丰富的实例。
Introduction to Semidefinite Programming (SDP), by Robert Freund
（https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-251j-introduction-to-mathematical-programming-fall-2009/readings/MIT6_251JF09_SDP.pdf）
数学更好一些的同学，尤其是代数学的比较好的同学，想致力于SDP理论研究的，可以学习Pablo Parrilo等人的参考书。
Semidefinite Optimization and Convex Algebraic
Geometry（http://www.mit.edu/~parrilo/sdocag/index.html）
Prof. Parrilo主页上也有课程6.256/18.456 – Algebraic techniques and semidefinite programming的一些讲义、作业资料，可以配套学习。矩阵补全问题作为SDP可应用的一个实例，我在以前的知乎回答也有简单介绍：
矩阵补全（matrix completion）的经典算法有哪些？目前比较流行的算法是什么？（https://www.zhihu.com/question/47716840/answer/110843844）
关于如何利用SDP近似计算独立集，以及SDP和copositive program的关系，可见我之前的一篇知乎文章：
覃含章：Copositive Programming简介（https://shimo.im/docs/j7jWAf7fshQJm3NR/read）
之后我们就以SDP目前一个最为重要的应用为例，在binary二次规划（BQP）中来探讨如何理解SDP，并且如何利用SDP导出近似算法。之后的内容基本都源于Prof. Parrilo的讲义资料。
二Binary二次规划和半正定松弛
BQP的一般形式为，对一个n维的半正定矩阵 Q：

那么注意到这边的约束其实也可以写成 n 个二次方程 X2=1，也就是说原问题其实也可以看成是一个连续优化问题，一个polynomial optimization问题。

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

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

本节最后我们再给出一个概率解释。这个解释是针对SDP在原空间上的表达式的，也就是说跟前面lifting的解释更加相关。我们考虑现在不是确定性地找出最优的 x，而只是说需要随机地选取 x，使得期望上我们的结果比较好就可以了。那么我们BQP的目标函数就变成

三基于SDP的BQP近似算法的bounds：Goemans-Williamson, Nesterov, Grothendieck-Krivine

那么我们就意识到这里的 Q 其实是有比较好的结构的，比如理论上来说它有一个很好的特性：对角占优（diagonally dominant），这样使得我们的BQP的目标函数具有可分离的结构。
所谓的Goemans-Williamson rounding就是说对SDP松弛得到的解（可能是分数）再化整（round)成-1或1 。这是SDP早期，包括到如今为止最成功和漂亮的应用之一。因为要知道的是，再1995年他们的paper发表之前，人们的各种非SDP方法最好就是只能达到0.5近似而且“卡壳”了许多年，他们基于SDP的方法一下子就将原来的0.5突破到了约0.878 。

即我们基于SDP的Goemans-Williamson rounding能给我们期望上约0.878的一个近似算法！

注意这边的结果比之前是要糟糕的，因为左边是个等号。另外，不那么容易注意的一点是，前面两种rounding如果碰到SDP直接给出了一个全是 ±1 的解（最优解），rounding是不会干扰这个解的（虽然值可能会变，但仍然是最优的），而这边的话，即使已经有了一个最优解，一旦这个Grothendieck-Krivine rounding一用上马上就会把解变差！（具体原因留给大家思考）
这边说点题外话，Grothendieck（是的，就是你知道的那位神一般的Grothendieck 。当然，这里出现名字的所有人都已经够神的了）这里出现的相关的工作当然不是用来做BQP,SDP的（那会儿SDP的理论根本都还没有呢），他只是年轻的时候在做分析的时候顺便做了这么个结果。后来是被Krivine捡出来并用在这个bipartite结构的BQP问题里面了。为了给足Grothendieck credit，把这边相关的常数就叫做Grothendieck constant了。
对本节出现的分析的完整细节感兴趣的同学可参阅Parrilo相关讲义和书籍，或者其实还有个非常艰深的凸优化讲义（我所知道的所有凸优化教材里最为艰深的：Lectures on Modern Convex Optimization，by Aharon Ben-Tal and Arkadi Nemirovski）和其中所引用的相关文献。
四G-W rounding对一般化BQP问题的计算实例

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

稠密Q的实验结果。左边：naive算法；右边：G-W rounding
那么我们确实看到G-W rounding计算得到的结果比naive的要好得多，在我这次实验中G-W rounding最优解的目标函数值是-5563.56而naive算法10000次下来最好也才得到了一个-1500左右的函数值。而且10000次取样的情况下我们的样本均值和理论均值也非常接近了，在我这次实验中，naive算法的样本均值和理论均值为16.21，19.26，而G-W rounding的样本均值和理论均值为-4879.23和-4880.3（所以图上基本都是一条线，肉眼看不出之间的gap）。
最后我们也对稀疏的 Q 和低秩（low rank）的 Q 看看G-W rounding的表现。我们从下图看到G-W rounding给出的解全部挤在一块了！（当然，10000次实验并不完全是同一个解，只是>95%都是同一个，所以直方图肉眼来看就塌缩成一条光杆了…）

稀疏Q（这里选取了一个三对角对称阵）的实验

低秩Q（这里的秩为1）的实验
【半正定二次规划半正定规划松弛】这个结果其实也应该是和直觉相符的，这里具体原因就留给大家作为思考了。提示：考虑在这种的情况下真正所需要的超平面的维数？

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

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