半正定和正定的区别半正定规划问题( 二 ) _云知道

关于对偶形式，当然最直接的推法是通过对原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）和其中所引用的相关文献。