1. 首頁 > 生活 > >

半正定二次規劃 半正定規劃松弛

小知識



文章插圖
半正定二次規劃 半正定規劃松弛

文章插圖
編者按
本文介紹半正定規劃（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 個二次方程 X2=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%都是同一個，所以直方圖肉眼來看就塌縮成一條光桿了…）
稀疏Q（這里選取了一個三對角對稱陣）的實驗
低秩Q（這里的秩為1）的實驗
【半正定二次規劃 半正定規劃松弛】這個結果其實也應該是和直覺相符的，這里具體原因就留給大家作為思考了 。提示：考慮在這種 的情況下真正所需要的超平面的維數？