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

编者按
本文介绍半正定规划（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）的经典算法有哪些？目前比较流行的算法是什么？（
http://www.jinnalai.com/uploads/article/2021/09/29/86268 program的关系，可见我之前的一篇知乎文章：
覃含章：Copositive Programming简介（
https://shimo.im/docs/j7jWAf7fshQJm3NR/read）
之后我们就以SDP目前一个最为重要的应用为例，在binary二次规划（BQP）中来探讨如何理解SDP，并且如何利用SDP导出近似算法。之后的内容基本都源于Prof. Parrilo的讲义资料。
二Binary二次规划和半正定松弛BQP的一般形式为，对一个n维的半正定矩阵 Q：