一種求解半定規劃的鄰近外梯度算法

于冬梅，高雷阜，趙世杰，楊培

（遼寧工程技術大學優化與決策研究所，遼寧阜新123000）

一種求解半定規劃的鄰近外梯度算法

于冬梅，高雷阜，趙世杰，楊培

（遼寧工程技術大學優化與決策研究所，遼寧阜新123000）

本文提出了一種求解半定規劃的鄰近外梯度算法.通過轉化半定規劃的最優性條件為變分不等式，在變分不等式滿足單調性和Lipschitz連續的前提下，構造包含原投影區域的半空間，產生鄰近點序列來逼近變分不等式的解，簡化了投影的求解過程.將該算法應用到教育測評問題中，數值實驗結果表明，該方法是解大規模半定規劃問題的一種可行方法.

半定規劃；變分不等式；次梯度半空間；外梯度算法

1　引言

半定規劃（Semidefinite Programming，SDP）是線性規劃（Linear Programming，LP）的一種拓廣.與線性規劃的約束條件不同，半定規劃是在滿足約束條件“對稱矩陣的仿射組合半正定”的條件下，求目標函數極大（極小）化的問題.在半定規劃模型下，線性規劃、凸二次規劃（Convex Quadratic Programming，CQP）、二階錐規劃（Second-order Cone Programming，SOCP）等規劃問題均可看作其特殊形式［1］.于此同時，半定規劃在特征值優化、控制論、組合優化以及工業工程設計等許多領域都具有廣泛的應用.目前，半定規劃的研究主要集中在求解方法上，線性規劃內點法的巨大成功，啟發人們將線性規劃的內點法推廣到半定規劃上.在理論上，內點算法已經非常成熟，被證明是求解半定規劃問題的有效方法之一［2］，但是內點法的運行通常需要一對嚴格的原始一對偶初始可行解，而選擇合適的嚴格原始一對偶初始可行解非常困難，更為重要的是內點算法的每步迭代涉及到大量矩陣運算，這在很大程度上限制了其在大規模問題中的應用.

變分不等式問題（Variational Inequalities，VIP）不僅是數學規劃領域的一個重要的組成部分，而且它還與其它數學規劃問題有著緊密的聯系.線性規劃、非線性規劃及互補問題都是變分不等式的特殊情形［3］.對于變分不等式問題的求解算法研究在近十幾年中取得了很多優秀的研究成果.Pang和Chan在文獻［4］中全面地介紹了變分不等式問題的解法及其收斂性，主要包括線性化求解方法，非線性化求解方法（如非線性Jacobi方法）等.20世紀90年代，何炳生教授提出了投影收縮算法［5］，韓喬明基于投影收縮算法的思想提出了解半定規劃的二次攝動方法［6］，關秀翠證明了二次半定規劃的最優性條件與線性對稱變分不等式的等價性，并利用投影收縮算法求解［7］，徐鳳敏等轉化半定規劃的最優性條件，提出了一種新的投影算法［8］.本文把半定規劃問題轉化為等價的變分不等式，在變分不等式滿足單調性和Lipschitz連續的前提下，提出了一種鄰近外梯度算法求解半定規劃問題，通過數值實驗驗證本文的鄰近外梯度算法對于半定規劃問題的求解是可行的.

2　問題的提出

考慮如式（2.1）所示的標準形式的半定規劃問題和如式（2.2）所示的其對偶問題.

其中矩陣C，Ai∈Rn×n，X∈Sn×n表示對稱矩陣，表示X為半正定矩陣，“·”表示Frobenius內積，CX=Tr（CX）=表示矩陣CX的跡，

為給定的m維向量.

半定規劃原問題（2.1）和其對偶問題（2.2）的最優性充分條件如下：

轉化最優性條件（2.3）為變分不等式，利用鄰近外梯度算法對SDP問題進行求解.

2.1變分不等式

定義2.1［9］設C為有限維歐氏空間中的非空閉凸子集，映射F：C→Rn，若對任意的x∈C，尋求x?∈C使得下式恒成立

稱式（2.5）為變分不等式問題，記為VIP（?，F）.

Noor在文獻［10］中把上述變分不等式的經典定義推廣到實Hilbert空間，給出如下定義.

定義2.2［10］設H為實Hilbert空間，其內積記為〈·，·〉，范數記為‖·‖，??H為一非空閉凸集，映射F：H→H，對任意的v∈?，求u∈?，使下式恒成立

定義2.3設H為實Hilbert空間，F：H→H為一映射，

（1）若對任意的u，v∈?，都有〈F（u）-F（v），v-u〉≥0成立，則稱F在?上是單調的.

（2）若對任意的u，v∈?，存在τ＞0，使得

成立，則稱F在?上強單調，其中τ被稱為映射F的強單調常數.

（3）若對任意的u，v∈?，存在L＞0，使得

則稱F在?上Lipschitz連續，其中L為常數，稱其為映射F的Lipschitz常數.

定義2.4設?為實Hilbert空間H上一非空閉凸集，記為??H，給定其中一點u?H，如果存在z??，使得

則稱z是u在?上的投影，記為z=P?［u］.

2.2半定規劃問題的轉化

考慮半定規劃原問題（2.l）的對偶問題（2.2），去掉其松弛矩陣S可寫為

從而（2.3）式的最優性條件可表示為

定義有限維歐式空間Rn×n×Rn上的內積和范數，若令u=（X，y）T，則對任意的，定義內積為〈u1，u2〉=，則由此內積誘導出的范數為‖u‖=，用vec（X）表示矩陣X的列依次按列的順序尾首連接成的n2維向量.

由矩陣論［11］理論易知，任一個對稱矩陣A可以寫成A=WTDW的形式，其中W為正交矩陣，D為對角陣.定義，而且分別為對角陣D+，D-的對角元素，則

并且P1［A］=WTD+W表示對稱矩陣A在上的正交投影，P2［A］=WTD-W表示對稱矩陣A在上的正交投影［12］.在凸緊集上的投影具有一個重要的性質［13］：對于任意的v∈Rn×n×Rm和w∈?，有

下面給出的引理和定理建立了互補松弛條件和投影方程之間的等價關系.

引理2.1 A∈Sn，B∈，如果〈A，B〉=0當且僅當AB=0.

定理2.1［14］X0∈，S0∈，若X0S0=0當且僅當

證必要性：令X=X0-S0，對于?XT=X，則在如下的不等式

得到

由引理2.1可知

通過不等式（2.9）和（2.10），得到E（X0）=0.

充分性：由E（X0）=0，得到X0=.由

成立，從而得到

記

于是由引理2.1得到X0S0=0.

定理2.2設u=（X，y）T∈?，那么最優性條件（2.7）與如下的投影方程等價

證最優性條件（2.3）等價于

于是SDP的最優性條件等價于式（2.15）的變分不等式問題.所以求解半定規劃最優解的問題，可以通過求解變分不等式（2.15）實現，能夠解決該變分不等式的方法，都可能同時獲得SDP的最優解.而在本文中提出鄰近外梯度算法解決該問題.

3　半定規劃的鄰近外梯度算法

有許多求解變分不等式的算法和研究成果，如投影法［15］、Wiener-Hopf方程法、逐點逼近法等［16-18［19］，通過每次迭代中增加一個投影來克服一般投影算法限制太強的缺點.并且，何炳生教授在2004年提出了一種近似鄰近外梯度類型算法［20］.本文針對迭代步驟中不規則閉凸區域上投影計算難的問題，結合近似鄰近點算法，外梯度算法以及次梯度半空間投影算法，提出鄰近外梯度算法求解半定規劃問題，在每次迭代步中定義誤差限ε，保證算法具有很好的收斂性.

3.1半定規劃的鄰近外梯度算法的實現

通過最優性條件（2.15），SDP問題可等價轉化為一個定義在有限維歐氏空間中，并在閉凸集?=×Rm上的變分不等式問題

其中

由F（u）的定義可知F（u）單調且Lipschitz連續［21，22］.本文結合外梯度算法，構造包含原投影區域的半空間，將投影建立在半空間上，簡化投影的求解過程，并對新的鄰近點序列作相應限制.下面給出鄰近外梯度算法具體的實現過程.

步驟1給定β0=1，ε≥0，0＜u＜v＜1，0＜ρ＜1，0＜γ＜2，u0∈?，k=0.

步驟2計算預測點

停，否則轉步驟3.

步驟3令rk=，若rk≤v，計算

步驟4構造半空間Hk，

計算在半空間上Hk投影

計算下一個迭代點

步驟5若e（F（uk），βk）=0，計算

否則k=k+1，轉步驟1.

3.2數值試驗

教學測試穩定性的統計研究中有一類重要問題即教育測試問題（ETP）.為了驗證算法的可行性，在Matlab2012中執行該算法，在Intel（R），Pentium（R），Core（TM）i7-3520M CPU，2.9GHz，4.00GB內存，Windows 7操作系統上進行數值實驗.在實施算法時，為了與外梯度算法和半定規劃軟件包SDP packuser內點算法的計算結果進行比較［23-24］，實驗參數的設置相同.教育測試問題模型如下.

給定一個對稱正定矩陣C，求

其中Diag（y）表示由向量y為對角元素得到的對角矩陣，e表示元素全為1的列向量.Iter表示求解問題過程中算法得到最終結果所需要的迭代次數，CPU-time表示完成計算所需要的時間，單位s，問題規模從n=4到n=180，ε=10-4為停止準則.下表給出了求解SDP問題的迭代次數和CPU計算時間的結果.

表1：數值實驗結果比較

表2：數值實驗結果比較

表1和2分別給出了求解半定規劃問題一次計算的迭代次數和CPU計算時間，與解半定規劃的內點法相比，本文算法編程容易，單步計算量小，能充分利用原始數據的稀疏性，占用內存小.可以看出，在精度要求相同的情況下，本文提出的鄰近外梯度算法在求解半定規劃問題時運行速度比內點算法快得多，迭代次數明顯減少，算法運行時間短.與外梯度算法相比，本文算法的迭代次數和運行時間更優.從數值實驗結果可以看出，提出的算法對于半定規劃問題的求解是可行的.

4　結論

本文通過把求解半定規劃問題有效的轉化為求解變分不等式問題，把變分不等式的數值解法從歐式空間推廣到有限維空間，給出了一個求解半定規劃問題的鄰近外梯度算法.并在算法中考慮不規則閉凸區域上投影計算難的問題來構造半空間上的投影，在算法中引入特殊的迭代步長因子，增加了迭代點的靈活性，通過數值實驗說明該算法是求解半定規劃問題的一種可行方法.半定規劃與許多優化問題有著緊密的聯系，將半定規劃和互補問題結合是今后的研究重點.

［1］Henry Wolkowicz，Romesh Saigal，Lieven Vandenbrghe.Handbook of semidefinite programming［M］. Boston：Kluwer Academic Publishers，2000：1-27.

［2］Chen X，Tseng P.Non-interior continuation methods for solving semidefinite complementarity problems［J］.Math.Prog.，2003（9）：624-645.

［3］Harker P T，Pang J S.Finite-dimensional variational inequality and nonlinear complementarity problems：a survey of theory，algorithms and applications［J］.Math.Prog.，1990，48：161-220.

［4］Pang J S，Chan D.Iterative methods for variational and complementarity problems［J］.Math.Prog.，1982，24：284-313.

［5］He B S.A class of projection and contraction methods for monotone varational inequalities［J］.Appl. Math.Opti.，1997，35：69-76.

［6］韓喬明.解半定規劃的二次攝動方法［J］.應用數學學報，1999，1：84-90.

［7］關秀翠，刁在筠.二次半定規劃問題及其投影收縮算法［J］.高等學校計算數學學報，2002，2：97-108.

［8］徐鳳敏，劉三陽.半定規劃的一種新算法［J］.西安電子科技大學學報，2000，6：773-777.

［9］韓繼業，修乃華，戚厚鐸.非線性互補理論與算法［M］.上海：上海科學技術出版社，2006.

［10］Noor M A.Extragradient methods for pseudomonotone variational inequalities［J］.J.Opti.The. Appli.，2003，117（3），475-488.

［11］Bhatia R.Matrix analysis［M］.Germany：Springer，1985.

［12］楊國平，劉三陽.半定規劃問題的一種新的預測校正算法［J］.應用數學，2005，18：5-9.

［13］Luenberger D G.Introduction to linear and nonlinear programming［M］.USA：Addison-Wesley，1973.

［14］Han Qiaoming.Projection and contraction methods for semidefinite programming［J］.Appl.Math. Comput.，1998，95：275-289.

［15］鄭蓮.解擬變分不等式的超平面投影算法［J］.系統科學與數學，2013，5：579-584.

［16］張麗麗，李興斯.箱式約束變分不等式的一類新光滑gap函數［J］.應用數學和力學，2013，1：27-37.

［17］劉英.Banach空間中關于變分不等式組與嚴格偽壓縮映射的粘滯逼近法［J］.應用數學學報，2013，2：324-336.

［18］烏力吉，陳國慶.箱約束變分不等式的一個簡單光滑價值函數和阻尼牛頓法［J］.應用數學和力學，2005，26（8）：988-996.

［19］He B S，Liao L Z.Improvements of some projection methods for monotone nonlinear variational inequalities［J］.Optim.Theory Appl.，2002，112（1），111-128.

［20］He B S，Yang Z H，Yuan X M.An approximate proximal-extragradient type method for monotone variational inequalities［J］.J.Math.Anal.Appl.，2004，300：362-374.

［21］Censor Y，Gibali A，Reich S.The subgradient extra-gradient method for solving variational inequalities in hilbert space［J］.J.Optim.Theory Appl.，2011，148：318-335.

［22］Abdellah Bnouhachem，Muhammad Aslam Noor.Mohalfaoui and Sheng zhaohan.An approximate proximal point algorithm for nonlinear complementtarity problems［J］.Hacettepe J.Math.Stat.，2012，41（1），103-117.

［23］Toh K C，Todd M J，T¨ut¨unc¨u R H.SDPT3-a Matlab software package for semidefinite programming，version 2.1［J］.Opti.Meth.Soft.，1999，11（2）：1-30.

［24］李蕊.半定規劃的外梯度法研究［D］.西安：西安電子科技大學碩士學位論文，2010.

A PROXIMAL EXTRAGRADIENT ALGORITHM FOR SEMIDEFINITE PROGRAMMING

YU Dong-mei，GAO Lei-fu，ZHAO Shi-jie，YANG Pei
（Research Institute of Optim.and Decision，Liaoning Technical University，Fuxin 123000，China）

In this paper，we present a proximal extragradient algorithm for solving semidefinite programming probem.The optimality conditions for semidefinite programming are transformed into variational inequality problem.Under the premise of variational inequality monotone and Lipschitz continuous，half-space contains the original projection area is constructed，generated points sequence is approaching the solution of variational inequalities，such that the projection of the solution process is simplified.The algorithm is applied to educational evaluation questions，and numerical results show that the proposed method is feasible for solving large-scale semidefinite programming problem.

semidefinite programming（SDP）；variational inequalities；subgradient half space；extragradient algorithm

MR（2010）主題分類號：90C22O221.2

A

0255-7797（2016）05-1047-09

2014-04-02接收日期：2014-07-02

教育部高校博士學科科研基金聯合資助項目（20132121110009）；國家自然科學基金天元基金（11326224）；遼寧省教育廳基金資助項目（L2012105）.

于冬梅（1986-），女，滿族，遼寧岫巖，博士，主要研究方向：半定規劃理論與應用，錐規劃.

2010 MR Subject Classification：90C22