整理2021年11月8日的筆記時(shí)翻到一頁紙標(biāo)題只寫了半行字半定規(guī)劃SDP。那天我在調(diào)一個(gè)圖劃分問題的松弛折騰到很晚隨手記下來的SDP要點(diǎn)如今回頭看竟然成了之后好幾個(gè)項(xiàng)目的解題地基。半定規(guī)劃這個(gè)名字聽起來很數(shù)學(xué)但本質(zhì)其實(shí)不難它就是把線性規(guī)劃里的“非負(fù)向量”約束換成“半正定矩陣”約束。它之所以值得花時(shí)間去啃是因?yàn)樗茏龊芏嗑€性規(guī)劃做不了的事——給組合優(yōu)化提供強(qiáng)松弛、把非凸的秩問題轉(zhuǎn)換成凸問題、把控制理論里的穩(wěn)定性條件寫成可求解的矩陣不等式。這篇文章適合正在跟整數(shù)規(guī)劃、非線性約束、低秩恢復(fù)打交道或者被某個(gè)看似簡(jiǎn)單卻死活解不動(dòng)的小模型卡住的人讀。我會(huì)把核心原理、應(yīng)用范式、求解器選型以及實(shí)際踩坑的過程都捋一遍盡量說人話。1. 線性松弛為什么擋不住這種問題從最大割說起1.1 一個(gè)讓線性松弛當(dāng)場(chǎng)翻車的例子最大割問題是SDP最經(jīng)典的出場(chǎng)場(chǎng)景。問題本身很直白給你一張無向圖每條邊帶權(quán)重把頂點(diǎn)分成兩組讓“兩端不在同一組”的邊權(quán)重總和盡量大。這是個(gè)NP-hard問題聚類、電路劃分、網(wǎng)絡(luò)設(shè)計(jì)里都藏著它的變體。第一次接觸這類問題時(shí)大多數(shù)人會(huì)嘗試整數(shù)規(guī)劃建模。對(duì)每條邊(i,j)引入變量表示兩端是否同組最直接的做法是用x_i±1編碼組別然后最大化∑ w_ij · (1 - x_i x_j) / 2這里x_i x_j1表示同組該邊不貢獻(xiàn)x_i x_j-1表示異組貢獻(xiàn)w_ij。理想情況是讓x_i只取±1但那是整數(shù)規(guī)劃不好解。所以經(jīng)典的松弛思路是允許x_i落在[-1,1]區(qū)間把問題變成線性規(guī)劃。這個(gè)松弛在理論上是成立的——可行域變大了最優(yōu)值只會(huì)更好。但問題是它好得過頭了。我在一個(gè)模擬項(xiàng)目X里測(cè)過一張單位權(quán)隨機(jī)圖整數(shù)最優(yōu)割大約能拿到總邊權(quán)的84%線性松弛給出來的上界卻在92%以上。這個(gè)上界虛高到?jīng)]法用來做分支定界的剪枝幾乎等于沒給信息。原因在于[-1,1]這個(gè)盒子太松松弛解可以讓每條邊都“半貢獻(xiàn)”把這個(gè)割的邊數(shù)同時(shí)掙滿這在真正的離散解里根本做不到。換成SDP之后情況完全不一樣。做法是把標(biāo)量x_i升級(jí)成向量v_i約束張成Gram矩陣X其中X_ii1X_ijv_i^T v_j。允許X_ij在[-1,1]之間連續(xù)變化但要求整個(gè)Gram矩陣半正定。同樣是那張隨機(jī)圖SDP給出來的上界只比整數(shù)最優(yōu)高兩三個(gè)百分點(diǎn)。這就是SDP在組合優(yōu)化里最核心的價(jià)值松弛質(zhì)量緊邊界有用。1.2 為什么SDP松弛更緊一個(gè)幾何直覺很多人第一次看到“把標(biāo)量升級(jí)成向量”會(huì)覺得莫名其妙這不是把簡(jiǎn)單問題搞復(fù)雜了嗎但如果從幾何角度理解就順了。線性松弛相當(dāng)于把{-1,1}^n的頂點(diǎn)集合放進(jìn)一個(gè)n維立方體。立方體是凸的好優(yōu)化但它的體積遠(yuǎn)大于離散點(diǎn)真正的凸包尤其在組合結(jié)構(gòu)復(fù)雜時(shí)立方體的很多角落在組合意義上根本不可達(dá)。SDP則不同它把每個(gè)頂點(diǎn)映射為單位球上的一個(gè)向量可行域變成所有Gram矩陣的集合——你可以讓某些邊的內(nèi)積給到部分的貢獻(xiàn)但這些內(nèi)積必須來自一組真實(shí)存在的歐氏空間向量不能每個(gè)方向都撒謊。舉個(gè)例子三條邊的三角形如果想讓三條邊同時(shí)貢獻(xiàn)接近滿分線性松弛可以說“每條邊都切一半”三個(gè)x_i_i的對(duì)都取接近0目標(biāo)值虛高。但SDP里三個(gè)向量?jī)蓛蓨A角不能同時(shí)接近180°Gram矩陣半正定這個(gè)約束會(huì)把這種不可能直接判死。所謂“半正定約束沒有時(shí)間先后它管的是全局一致性”這就是SDP比LP緊的幾何本質(zhì)。2. 半定錐、LMI與對(duì)偶SDP的數(shù)學(xué)骨架2.1 標(biāo)準(zhǔn)形式從頭到尾只有三個(gè)要素SDP的標(biāo)準(zhǔn)形式寫出來非常簡(jiǎn)短min tr(C X) s.t. tr(A_i X) b_i, i 1,...,m X ? 0且X為對(duì)稱矩陣這里tr(AX)是矩陣內(nèi)積等于把兩個(gè)矩陣對(duì)應(yīng)元素相乘再求和。X ? 0表示X是半正定矩陣所有特征值非負(fù)。三個(gè)要素分別是線性目標(biāo)、線性等式約束、半定矩陣錐約束。跟線性規(guī)劃相比唯一的變化就是約束從“x ≥ 0”變成了“X ? 0”。但這一變表達(dá)力就完全不同了。標(biāo)量版本里x_i≥0是一些獨(dú)立的半射線矩陣版本里X ? 0是整個(gè)半定錐它對(duì)矩陣整體結(jié)構(gòu)施加約束能把“這些向量之間滿足某種內(nèi)積關(guān)系”這種全局性質(zhì)直接表達(dá)出來。很多看起來完全非線性的問題放進(jìn)這個(gè)框架里反而變成凸問題。2.2 LMI與Schur補(bǔ)把二次約束翻譯進(jìn)半定世界線性矩陣不等式LMI是SDP最常見的表述形式。它一般寫成F(x) A_0 ∑ x_i A_i ? 0其中A_i是常數(shù)對(duì)稱矩陣x是決策向量。只要目標(biāo)函數(shù)是線性的這整個(gè)問題就是一個(gè)SDP。之所以強(qiáng)調(diào)LMI是因?yàn)榇罅抗こ碳s束都不是天然寫成SDP的標(biāo)準(zhǔn)形式而是能通過LMI等價(jià)轉(zhuǎn)化。最常用的翻譯工具是Schur補(bǔ)。比如我要表達(dá)“t ≥ x^T x”這個(gè)二次約束它本身是凸的但沒法寫進(jìn)線性規(guī)劃。通過Schur補(bǔ)可以寫成[ I, x ] [ x^T, t ] ? 0這個(gè)分塊矩陣半正定等價(jià)于t ≥ x^T x?？雌饋碇皇菗Q了個(gè)寫法但在求解上是從“非線性約束”變成了“矩陣錐約束”直接落入SDP的射程。我做傳感器定位項(xiàng)目時(shí)這個(gè)技巧幾乎天天用——把距離約束的平方項(xiàng)塞進(jìn)矩陣的角落問題就從“不知道從哪下手”變成了“標(biāo)準(zhǔn)的凸優(yōu)化”。2.3 對(duì)偶與Slater條件求解器真正在解什么SDP的拉格朗日對(duì)偶寫出來跟原始問題長(zhǎng)得非常對(duì)稱max b^T y s.t. C - ∑ y_i A_i ? 0弱對(duì)偶始終成立任意原始可行點(diǎn)的目標(biāo)值都不小于任意對(duì)偶可行點(diǎn)。但真正讓求解器能高效工作的是強(qiáng)對(duì)偶也就是原始最優(yōu)值等于對(duì)偶最優(yōu)值而這需要在原始問題里存在一個(gè)嚴(yán)格可行點(diǎn)某個(gè)X滿足等式約束并且X嚴(yán)格正定所有特征值都大于0。這個(gè)條件叫Slater條件。大多數(shù)SDP求解器同時(shí)維護(hù)原始路徑和對(duì)偶路徑靠?jī)烧咧g的對(duì)偶間隙來判斷收斂。如果問題里沒有嚴(yán)格可行點(diǎn)對(duì)偶路徑會(huì)一直不穩(wěn)求解器要么慢得要命要么直接報(bào)不可行。我在實(shí)際項(xiàng)目里吃過這方面的虧——模型的理論形式看著沒問題等式約束也都對(duì)得上但變量被約束在低秩流形上整個(gè)可行集里找不到一個(gè)嚴(yán)格正定的點(diǎn)求解器就是不給面子。解決辦法通常是在目標(biāo)里加一個(gè)很小的正則項(xiàng)比如εtr(X)或者把某些等式約束放寬到帶ε的區(qū)間把問題推向內(nèi)點(diǎn)存在的情形。2.4 多項(xiàng)式時(shí)間可解為什么SDP能上工程SDP是凸優(yōu)化最經(jīng)典的算法是內(nèi)點(diǎn)法。它的思路是在目標(biāo)函數(shù)上疊加一個(gè)對(duì)數(shù)障礙項(xiàng)比如min tr(CX) - μ log det(X)然后沿著μ遞減的路徑做牛頓迭代。每步牛頓法要分解一個(gè)大型矩陣代價(jià)大約O(n^3)但迭代次數(shù)只需要約O(√n log(1/ε))——這里的n是矩陣維度ε是目標(biāo)精度。這意味著求解時(shí)間隨問題規(guī)模是多項(xiàng)式增長(zhǎng)而不是指數(shù)爆炸這是SDP能用于實(shí)際工程的根本保證。不要被“矩陣”這個(gè)外殼嚇住從計(jì)算復(fù)雜度框架看SDP和LP非常接近只是每一步要多拆一個(gè)更大的矩陣。實(shí)際表現(xiàn)上幾千維以內(nèi)的SDP在主流求解器上都能在幾秒到幾分鐘內(nèi)收斂到1e-6左右的精度完全夠用。3. 四個(gè)能直接抄的SDP應(yīng)用范式松弛、核范數(shù)、李雅普諾夫與定位3.1 最大割的經(jīng)典套路SDP求解隨機(jī)舍入最大割的完整流程值得認(rèn)真走一遍它是理解SDP后處理的標(biāo)準(zhǔn)模板。第一步建模目標(biāo)。設(shè)X是Gram矩陣約束X_ii1最大化∑ w_ij (1 - X_ij)/2。求解SDP得到最優(yōu)的X*。第二步特征分解。把X*寫成VΛV^T取特征向量矩陣V每一行就是原問題頂點(diǎn)對(duì)應(yīng)的高維向量v_i。第三步隨機(jī)舍入。生成一個(gè)標(biāo)準(zhǔn)高斯隨機(jī)向量r對(duì)所有頂點(diǎn)計(jì)算s_isign(r^T v_i)s_i為1的頂點(diǎn)歸入A組-1歸入B組。第四步重復(fù)多次。采樣幾百上千個(gè)隨機(jī)方向取切割權(quán)重最大的一次作為最終解。這個(gè)流程里最關(guān)鍵的理解點(diǎn)是SDP解出來的不是一組離散標(biāo)簽而是一組連續(xù)向量。標(biāo)簽是在后處理階段“舍入”出來的舍入質(zhì)量直接決定最終結(jié)果。理論上有保證期望切割權(quán)重不低于SDP最優(yōu)值的0.878倍這是經(jīng)典結(jié)果。實(shí)際跑下來通常更好尤其在冗余采樣幾百組隨機(jī)向量后經(jīng)常能拿到0.9以上的近似比。3.2 核范數(shù)最小化把非凸秩問題變成凸問題推薦系統(tǒng)里的矩陣補(bǔ)全圖像修復(fù)里的低秩重構(gòu)本質(zhì)都在做同一件事有一個(gè)大矩陣只知道部分元素想恢復(fù)整個(gè)矩陣而且相信真實(shí)矩陣是低秩的。直接最小化rank(X)是非凸的幾乎沒法解。但rank函數(shù)有一個(gè)凸包絡(luò)核范數(shù)也就是所有奇異值之和。把目標(biāo)換成min ||X||_*問題變成凸的。更有意思的是核范數(shù)可以寫成SDPmin (1/2)(tr(U) tr(V)) s.t. [ U, X; X^T, V ] ? 0這個(gè)等價(jià)關(guān)系在工程上意味著什么意味著低秩恢復(fù)可以被一套標(biāo)準(zhǔn)的凸優(yōu)化工具鏈處理不需要給每個(gè)問題手寫專用算法。這在以前是不可想象的。我在一個(gè)圖像去噪的demo里試過噪聲污染了大約60%的像素點(diǎn)核范數(shù)SDP恢復(fù)出來的矩陣在視覺上幾乎看不出缺失痕跡。3.3 李雅普諾夫穩(wěn)定性控制里的SDPSDP不只是離散優(yōu)化和機(jī)器學(xué)習(xí)的工具控制理論里它幾乎是標(biāo)配。一個(gè)線性系統(tǒng)dx/dt Ax怎么判斷它是否穩(wěn)定可以找一個(gè)李雅普諾夫函數(shù)V(x)x^T P x如果P正定并且V沿系統(tǒng)軌跡單調(diào)下降系統(tǒng)就穩(wěn)定。這個(gè)條件寫成矩陣不等式就是P ? 0, A^T P P A ? 0兩個(gè)都是矩陣不等式變量是P這正是標(biāo)準(zhǔn)SDP。求解之后不僅能判斷穩(wěn)定性還能拿P去構(gòu)造控制器或者在滿足LMI約束的前提下進(jìn)一步優(yōu)化某個(gè)性能指標(biāo)比如最小化某個(gè)衰減率這些追加約束都還是SDP。這個(gè)應(yīng)用提醒我SDP的覆蓋面遠(yuǎn)比單純“組合優(yōu)化松弛”要寬它本身就是處理矩陣層面約束的通用語言。3.4 傳感器定位提升半定松弛丟棄秩約束傳感器定位問題是一個(gè)特別好的范式平面上布了N個(gè)節(jié)點(diǎn)只知道部分兩兩距離測(cè)量值想估計(jì)每個(gè)節(jié)點(diǎn)的真實(shí)坐標(biāo)。約束長(zhǎng)這樣(p_i - p_j)^T (p_i - p_j) d_ij^2這是非凸的二次等式直接解非常困難。SDP的做法是把這個(gè)非線性問題“提升”到矩陣空間。定義P為坐標(biāo)矩陣d×n構(gòu)造分塊矩陣Y [I, P; P^T, Q]其中Q是對(duì)稱矩陣。注意如果Q恰好等于P^T P那么Y自動(dòng)半正定而且秩等于d。所以原始問題等價(jià)于Y ? 0、Y的某些固定塊已知、外加rank(Y)d。丟掉秩約束保留半正定和固定塊約束就是一個(gè)SDP。這個(gè)“提升到矩陣 半定松弛 丟秩”的配方可以遷移到很多幾何問題上包括相機(jī)位姿估計(jì)、分子構(gòu)象恢復(fù)等。我自己的體會(huì)是看到“二次等式約束”先別慌先想能不能把它塞進(jìn)一個(gè)分塊矩陣的Schur補(bǔ)里往往答案就出來了。4. 求解器實(shí)戰(zhàn)場(chǎng)內(nèi)點(diǎn)法、一階法與建模接口怎么選4.1 兩類主流求解器精度還是規(guī)模半定規(guī)劃的求解器大體可以分兩類選錯(cuò)了會(huì)非常難受。類型每步代價(jià)迭代次數(shù)適用規(guī)模典型表現(xiàn)內(nèi)點(diǎn)法型O(n^3)約O(√n log(1/ε))幾千維以內(nèi)穩(wěn)健gap能到1e-8一階法型O(nnz)依賴稀疏度幾百到幾萬受精度影響大超大規(guī)模稀疏矩陣快但高精度收斂慢內(nèi)點(diǎn)法型的看家本領(lǐng)是精度和穩(wěn)健性適合驗(yàn)證模型、產(chǎn)出基準(zhǔn)解、處理中小規(guī)模問題。一階法型更適合超大規(guī)模、稀疏結(jié)構(gòu)明顯、只需要近似解做快速探索的場(chǎng)景。我現(xiàn)在的習(xí)慣是首次接觸一個(gè)問題永遠(yuǎn)先用內(nèi)點(diǎn)法在小規(guī)模數(shù)據(jù)上跑出目標(biāo)值的基準(zhǔn)再切到一階法去逼近。否則你會(huì)分不清誤差是來自松弛模型本身還是來自算法沒收斂。4.2 建模接口三行代碼聲明一個(gè)半定變量SDP建模接口已經(jīng)做得很成熟核心抽象就三個(gè)元素半定矩陣變量、等式約束、線性目標(biāo)。以某通用凸優(yōu)化建模接口為例最大割的SDP松弛寫起來大約是這樣的概念代碼# 概念代碼最大割SDP松弛 X Semidefinite(n) # 聲明n×n半定矩陣變量 constraints [X[i][i] 1 for i in range(n)] objective sum(w[i][j] * (1 - X[i][j]) / 2 for i j) prob Minimize(-objective) # 等價(jià)于最大化 prob.solve()這段代碼幾乎和數(shù)學(xué)公式一一對(duì)應(yīng)不用手動(dòng)推導(dǎo)對(duì)偶形式不用管內(nèi)點(diǎn)法的具體步進(jìn)策略。聲明變量、寫約束、設(shè)目標(biāo)、調(diào)求解器四步走完。這也是我推薦每個(gè)人都應(yīng)該學(xué)一點(diǎn)SDP建模的原因數(shù)學(xué)底子要求不高收益卻非常實(shí)在。4.3 求解參數(shù)與終止判據(jù)調(diào)什么、什么時(shí)候調(diào)拿回一個(gè)SDP模型求解參數(shù)通常不需要大動(dòng)但有幾個(gè)點(diǎn)值得了解。第一是初始點(diǎn)給X傳一個(gè)合理的正定矩陣比如單位陣的倍數(shù)往往能顯著減少收斂時(shí)間。第二是終止間隙gap建模階段如果只是探索解的行為gap設(shè)在1e-3到1e-4足夠如果要拿去做后續(xù)精確驗(yàn)證壓到1e-7更穩(wěn)。第三是迭代上限大規(guī)模一階法給一個(gè)較大的上限然后盯著gap下降曲線看而不是干等它結(jié)束。如果返回狀態(tài)是原始不可行或無界不要急著改約束先跑一個(gè)小規(guī)模代理問題把目標(biāo)系數(shù)縮小十倍看問題形態(tài)有沒有變化。無界問題通常表現(xiàn)為目標(biāo)函數(shù)在某個(gè)可行方向上能無限下降不可行問題則要檢查是否有冗余等式約束或者你手動(dòng)構(gòu)造一個(gè)明顯可行的X代入約束驗(yàn)證一下。這兩件事做下來大部分建模初期的問題都能定位。5. 我踩過的三個(gè)SDP數(shù)值坑從報(bào)錯(cuò)到修復(fù)的完整鏈路5.1 坑一約束系數(shù)尺度懸殊gap卡死不動(dòng)現(xiàn)象很典型求解器迭代了上千次gap停在1e-3附近死活不下來目標(biāo)值卻在微小的范圍內(nèi)抖動(dòng)。我的排查鏈路是先打印約束矩陣A_i的元素絕對(duì)值和分布。結(jié)果發(fā)現(xiàn)有些約束的系數(shù)集中在1e7量級(jí)另一些只有1e-7。這樣量級(jí)懸殊的系數(shù)放在同一個(gè)SDP里等價(jià)于把一個(gè)橢球拉伸得極扁牛頓步在數(shù)值上非常不穩(wěn)定。SDP的內(nèi)點(diǎn)法對(duì)尺度是敏感的盡管數(shù)學(xué)上同比例縮放不影響最優(yōu)解但在浮點(diǎn)數(shù)世界里等價(jià)不等于可計(jì)算。修復(fù)方式很簡(jiǎn)單把所有約束矩陣和目標(biāo)矩陣統(tǒng)一除以最大系數(shù)的絕對(duì)值也就是整體縮放到0.1到10的區(qū)間內(nèi)。做完之后同一求解器gap很快降到1e-7。驗(yàn)證方式也簡(jiǎn)單兩次求解的目標(biāo)值一致但收斂路徑和精度完全不同。這個(gè)坑是隱藏的因?yàn)槟繕?biāo)值看著沒變?nèi)绻呀饽萌プ鎏卣鞣纸馓卣飨蛄繒?huì)被數(shù)值噪聲污染得一塌糊涂后續(xù)舍入和恢復(fù)步驟全崩。5.2 坑二模型看似可行其實(shí)沒有Slater點(diǎn)有一次在模擬項(xiàng)目X里做傳感器定位求解器報(bào)原始不可行。我很確定約束方程組有解因?yàn)樗袦y(cè)量值都是真實(shí)的不存在矛盾。仔細(xì)排查后發(fā)現(xiàn)問題出在“幾何退化”。所有傳感器的真實(shí)坐標(biāo)落在一個(gè)低維子空間里比如全部共線這導(dǎo)致任何滿足等式約束的Y矩陣在對(duì)應(yīng)方向上的特征值自動(dòng)變成0整個(gè)可行集里找不到一個(gè)嚴(yán)格正定的內(nèi)點(diǎn)。也就是說雖然可行集非空但Slater條件不滿足對(duì)偶問題失效求解器只能判定原始不可行。修復(fù)的方法是加正則項(xiàng)給目標(biāo)函數(shù)加上δ·tr(X)δ取1e-6左右相當(dāng)于把可行集朝內(nèi)點(diǎn)方向“推”了一下。這會(huì)對(duì)最優(yōu)值引入δ量級(jí)的擾動(dòng)但對(duì)大多數(shù)工程應(yīng)用來說可以接受。這個(gè)坑的教訓(xùn)是SDP數(shù)學(xué)上寫著“半正定”求解器數(shù)值上要的是“正定”這兩個(gè)狀態(tài)之間的差距往往就是一次求解成功和失敗的分界線。5.3 坑三隨機(jī)舍入前忘了清洗特征向量最大割流程走到最后一步SDP解出來了gap已經(jīng)到1e-6隨機(jī)超平面舍入的結(jié)果卻慘不忍睹近似比只有0.6左右遠(yuǎn)低于0.878的理論保障。一開始我以為是隨機(jī)種子問題多跑幾組還是沒有改善。后來查了解矩陣本身發(fā)現(xiàn)問題出在求解器默認(rèn)容差下X*帶著微小的負(fù)特征值。特征分解之后負(fù)特征值對(duì)應(yīng)在特征向量里的小尾巴會(huì)讓向量長(zhǎng)度漂移有些向量的模長(zhǎng)變成了0.985或者1.03而舍入算法假設(shè)它們嚴(yán)格落在單位球上符號(hào)判斷的準(zhǔn)確率自然掉得厲害。修復(fù)方式是在舍入之前做清洗把特征值做clip負(fù)值截?cái)酁?重新構(gòu)造一個(gè)盡量貼近原始解的半正定矩陣再對(duì)所有向量歸一化到單位長(zhǎng)度。清洗之后重新跑幾千組隨機(jī)超平面近似比穩(wěn)定回到了0.9附近。這一步的代碼其實(shí)只有幾行但效果立竿見影現(xiàn)在它已經(jīng)成為我所有SDP后處理流程的固定環(huán)節(jié)。5.4 建模完成后必做的三問檢查法踩過這么多坑之后我給自己定了一個(gè)SDP模型提交前的三問檢查第一問約束里有沒有冗余等式冗余約束會(huì)讓對(duì)偶尺度退化有時(shí)還會(huì)在Slater點(diǎn)附近制造數(shù)值陷阱能刪就刪。第二問是否存在嚴(yán)格正定的可行點(diǎn)如果X_iI或者某個(gè)合理構(gòu)造的正定矩陣代入都不滿足約束就要考慮加正則項(xiàng)。第三問目標(biāo)函數(shù)有沒有無用的常數(shù)項(xiàng)常數(shù)項(xiàng)不影響最優(yōu)解但會(huì)影響對(duì)偶gap的讀數(shù)干擾你看收斂曲線。這三問花不了五分鐘但能避免大多數(shù)“求解器莫名其妙不工作”的局面。最后再分享一個(gè)我最近一直在用的習(xí)慣每個(gè)SDP模型求解完成后別急著看目標(biāo)值先打印最優(yōu)X的特征值譜。如果譜在某個(gè)k之后迅速衰減說明這個(gè)松弛的解本質(zhì)上是低秩的后處理階段完全可以把尾部噪聲權(quán)重丟掉轉(zhuǎn)成普通的結(jié)構(gòu)化問題如果譜從頭到尾都拖得很長(zhǎng)說明模型大概率太松得回去補(bǔ)約束。這個(gè)檢查十秒鐘就能做完卻能省下大量在舍入階段試錯(cuò)的時(shí)間。