编者按
本文介绍半正定规划（SDP）的一些应用实例，也包含了一个基于Julia/JuMP使用Mosek求解器的计算实例。通过这篇文章，你将从0/1二次规划出发，了解SDP的理论和建模求解思路。
文章作者：覃含章
责任编辑：覃含章
文章发表于微信公众号【运筹OR帷幄】：优化 | 半正定规划(SDP)的形象理解和基本原理
那么注意到这边的约束其实也可以写成 n 个二次方程 X²=1，也就是说原问题其实也可以看成是一个连续优化问题，一个polynomial optimization问题。
关于对偶形式，当然最直接的推法是通过对原SDP (P) 使用拉格朗日对偶。那么这边我们其实可以稍微灵活一些，我们可以直接对原来的BQP问题进行所谓的拉格朗日松弛（Lagrangian relaxation），这样让大家可以更深刻的体会拉格朗日对偶可以用来一般化地对（非凸）连续最小化优化问题求出一个下界。
本节最后我们再给出一个概率解释。这个解释是针对SDP在原空间上的表达式的，也就是说跟前面lifting的解释更加相关。我们考虑现在不是确定性地找出最优的 x，而只是说需要随机地选取 x，使得期望上我们的结果比较好就可以了。那么我们BQP的目标函数就变成
那么我们就意识到这里的 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（这里选取了一个三对角对称阵）的实验
低秩Q（这里的秩为1）的实验
这个结果其实也应该是和直觉相符的，这里具体原因就留给大家作为思考了。提示：考虑在这种 的情况下真正所需要的超平面的维数？
