編者按

本文介紹半正定規劃（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 個二次方程 X²=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%都是同一個，所以直方圖肉眼來看就塌縮成一條光桿了…）