本文由 发布，转载请注明出处，如有问题请联系我们！ 发布时间: 2021-08-01半正定规划问题-半正定和正定的区别

编写评价/表明

文中详细介绍了半正定整体规划(SDP)的一些运用案例，并包含一个应用根据Julia/JuMP的Mosek求得器的测算案例。根据本文，你将从0/1二次规划逐渐，掌握SDP的基础理论以及模型求得。

创作者:秦含章。

编写:秦含章。

文章内容发表在微信官方网账户:提升|图象表达与半正定整体规划(SDP)基本概念。

SDP有很多有意思的事例，除开线性规划问题这类充分必要条件，例如能够用于描绘现代控制理论的李亚普诺夫可靠性，及其能够类似的0/1二次规划的解。它可用以类似求得单独集/图的香侬容积，带矩阵的特征值的优化问题，复域上的插值法难题，欧氏空中间上面的置入难题及其带引流矩阵补齐/核形的优化问题。

事实上，SDP做为一种独特的凸优化难题，具备较强的模型工作能力。就现阶段的分析看来，实际上更高的短板取决于测算，例如怎样寻找一个规模性求得SDP的通用性优化算法。尽管SDP在锥体整体规划层面与LP类似，但事实上其一般构造现阶段尚未有效的了解。与LP不一样的是，我们知道实数域上的比较有限维多面体务必由比较有限个极值点和极大值放射线转化成(这也是广为人知的Minkowski辨别定律)，但针对半定锥，大家沒有那样的理论构造定律。

如果不偏题得话，我在这也不一一回应了，由于假如你想要知道怎样用SDP对以上难题进行模型并类似求得，能够根据阅读文章一些论文参考文献迅速获得更快的了解。这儿大家先强烈推荐几本书教材。

对SDP零基础但有一点凸优化基本的学员(沒有提升基本的学员应当从Boyd和Vandenberghe的凸优化书逐渐)能够从Robert Freund的这篇教材开始学习SDP。內容十分简约，包括丰富多彩的事例。

约翰逊·弗伦德半定整体规划概论

(https://OCW . MIT . edu/courses/electric-engineering-and-computer-science/6-251j-数学课编程学习-2009年秋天/readings/MIT6_251JF09_SDP.pdf)

数学课比较好的同学们，尤其是解析几何比较好的同学们，要想专注于SDP理论基础研究，能够学习培训一下Pablo Parrilo等的教材。

半定提升与凸解析几何

代数学(http://www.mit.edu/~parrilo/sdocag/index.html)

在帕罗专家教授的首页上也有一些课程内容6.256/18.456-解析几何方法和半可预测性程序编写的教材和工作原材料，能够用于适用学习培训。引流矩阵补齐难题做为SDP运用的一个事例，我以前在知乎问答的回应中也干了简易详细介绍:

引流矩阵补齐的经典算法有什么？现阶段盛行的算法是什么？(https://www.zhihu.com/question/47716840/answer/110843844)

有关怎样用SDP来靠近单独集及其SDP相融正程序流程的关联，参照我以前在知乎问答的文章内容:

秦含章:公司程序编写概论。

随后，以SDP最重要的运用为例子，探讨了怎样看待二进制二次规划(BQP)中的SDP，及其怎样运用SDP推论近似算法。以后的內容基本上是来自帕里罗专家教授的教材。

二元二次整体规划与半正定松驰

BQP的一般方式是，针对n维半正定矩阵q:

有关对偶方式，自然最立即的揉法是根据对原SDP (P) 应用拉格朗日对偶。那麼这里大家实际上能够略微灵便一些，我们可以立即对以前的BQP难题开展说白了的拉格朗日松驰（Lagrangian relaxation），那样让我们能够更难忘的感受拉格朗日对偶能够用于一般化地对（非凸）持续降到最低优化问题求出一个末地。对于对偶方式，自然最立即的推论便是对原SDP (P)应用拉格朗日对偶。因此小编在这儿事实上能够更轻松一点，我们可以立即对原BQP难题开展说白了的拉格朗日松驰，那样人们就可以更难忘的了解拉格朗日对偶能够用于找寻一般(非凸)持续降到最低优化问题的末地。

戈曼斯-威廉姆森舍入就是指根据释放压力SDP获得的解(可能是成绩)被舍入为-1或1。这也是SDP初期最取得成功最漂亮的运用之一，包含到现在。关键的是要了解，在1995年她们的发表论文以前，大家的各种各样非SDP方式最好是只做到0.5的自然数，而且被“卡”了好多年，她们根据SDP的方式忽然摆脱了原本的0.5到0.878上下。

即大家根据SDP的Goemans-Williamson rounding能给大家期待上大约0.878的一个近似算法！也就是大家根据SDP的Goemans-Williamson舍入能够给大家一个近似算法，期待约为0.878！

留意这里的后果比以前是要槽糕的，由于左侧是个等于号。此外，不那麼非常容易准备的一点是，前边二种rounding假如遇到SDP立即得出了一个都是 ±1 的解（最优解），rounding是不容易影响这一解的（尽管值很有可能会变，但仍旧是最佳的），而这里得话，即便早已得到一个最优解，一旦这一Grothendieck-Krivine rounding一用上立刻便会把解下降！ （实际缘故交给大伙儿思索）一定要注意，这儿的后果比之前更糟糕，由于左侧有一个等于号。此外，不那麼非常容易注意到的是，假如前二种舍入在碰到SDP时立即得出一个全为1的解(最优解)，舍入不容易影响这一解(尽管值很有可能会变，但仍旧是最佳的)，可是在这儿，即便有最优解，一旦应用这一格罗滕迪克-克里文舍入，解会马上下降！(实际缘故交给大伙儿思索)

大家跑题了，格罗滕迪克(是的，那便是你所晓得的神一样的格罗滕迪克。自然，这儿全部有名称的人都充足震撼。)自然，这儿的有关业务并并不是用于做BQP和SDP的(那时候SDP的基础理论压根不会有)，反而是他年轻的时候顺带做剖析得到那样的結果。它是克里文明确提出的，用以二部构造的BQP难题。为了更好地夸奖格罗滕迪克，这儿的有关参量称为格罗滕迪克参量。

对这节剖析的详细关键点有兴趣的同学们还可以参照Parrilo的有关教材和书本，或是事实上有一本十分难的凸优化教材(我所晓得的全部凸优化教材中较难的:当代凸优化专题讲座，作者是Aharon Ben-tal和Arka di Nemirovski)及其在其中收录的有关参考文献。

具备四w舍入的理论BQP难题的测算案例。

留意大家开展10000次取样，看一下結果。一定要注意，大家早已收集了10000个样版来查询結果。

随后大家的确见到G-W舍入测算的后果比孩子气的結果好很多。在我的试验中，G-W舍入最优解的总体目标函数为-5563.56，质朴优化算法最好是在1000次能获得一个-1500上下的函数。并且，在10000个样版的情形下，大家的样本均值和基础理论平均值十分贴近。在我的试验中，质朴优化算法的样本均值和基础理论平均值分別为16.21和19.26，而G-W舍入的样本均值和基础理论平均值分別为-4879.23和-4880.3(因此图大部分是一条线，人眼没有了他们相互之间的差别)。

最终大家也一起来看看G-W求整针对稀少Q和低秩Q的主要表现，从图片能够看得出G-W求整得出的解全是挤在一起的！(自然，一万个试验不全是同一个解，可是> 95%全是一样的，因此人眼看条形图塌成主杆……)。

实际上这一結果也应当和判断力一致，这儿的详细缘故会带给大伙儿去思索。提醒:考虑到这些情形下真真正正必须的超平面层面？