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

（遼寧工程技術(shù)大學(xué)優(yōu)化與決策研究所，遼寧阜新123000）

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

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

（遼寧工程技術(shù)大學(xué)優(yōu)化與決策研究所，遼寧阜新123000）

本文提出了一種求解半定規(guī)劃的鄰近外梯度算法.通過(guò)轉(zhuǎn)化半定規(guī)劃的最優(yōu)性條件為變分不等式，在變分不等式滿(mǎn)足單調(diào)性和Lipschitz連續(xù)的前提下，構(gòu)造包含原投影區(qū)域的半空間，產(chǎn)生鄰近點(diǎn)序列來(lái)逼近變分不等式的解，簡(jiǎn)化了投影的求解過(guò)程.將該算法應(yīng)用到教育測(cè)評(píng)問(wèn)題中，數(shù)值實(shí)驗(yàn)結(jié)果表明，該方法是解大規(guī)模半定規(guī)劃問(wèn)題的一種可行方法.

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

1　引言

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

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

2　問(wèn)題的提出

考慮如式（2.1）所示的標(biāo)準(zhǔn)形式的半定規(guī)劃問(wèn)題和如式（2.2）所示的其對(duì)偶問(wèn)題.

其中矩陣C，Ai∈Rn×n，X∈Sn×n表示對(duì)稱(chēng)矩陣，表示X為半正定矩陣，“·”表示Frobenius內(nèi)積，CX=Tr（CX）=表示矩陣CX的跡，

為給定的m維向量.

半定規(guī)劃原問(wèn)題（2.1）和其對(duì)偶問(wèn)題（2.2）的最優(yōu)性充分條件如下：

轉(zhuǎn)化最優(yōu)性條件（2.3）為變分不等式，利用鄰近外梯度算法對(duì)SDP問(wèn)題進(jìn)行求解.

2.1變分不等式

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

稱(chēng)式（2.5）為變分不等式問(wèn)題，記為VIP（?，F(xiàn)）.

Noor在文獻(xiàn)［10］中把上述變分不等式的經(jīng)典定義推廣到實(shí)Hilbert空間，給出如下定義.

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

定義2.3設(shè)H為實(shí)Hilbert空間，F(xiàn)：H→H為一映射，

（1）若對(duì)任意的u，v∈?，都有〈F（u）-F（v），v-u〉≥0成立，則稱(chēng)F在?上是單調(diào)的.

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

成立，則稱(chēng)F在?上強(qiáng)單調(diào)，其中τ被稱(chēng)為映射F的強(qiáng)單調(diào)常數(shù).

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

則稱(chēng)F在?上Lipschitz連續(xù)，其中L為常數(shù)，稱(chēng)其為映射F的Lipschitz常數(shù).

定義2.4設(shè)?為實(shí)Hilbert空間H上一非空閉凸集，記為??H，給定其中一點(diǎn)u?H，如果存在z??，使得

則稱(chēng)z是u在?上的投影，記為z=P?［u］.

2.2半定規(guī)劃問(wèn)題的轉(zhuǎn)化

考慮半定規(guī)劃原問(wèn)題（2.l）的對(duì)偶問(wèn)題（2.2），去掉其松弛矩陣S可寫(xiě)為

從而（2.3）式的最優(yōu)性條件可表示為

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

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

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

下面給出的引理和定理建立了互補(bǔ)松弛條件和投影方程之間的等價(jià)關(guān)系.

引理2.1 A∈Sn，B∈，如果〈A，B〉=0當(dāng)且僅當(dāng)AB=0.

定理2.1［14］X0∈，S0∈，若X0S0=0當(dāng)且僅當(dāng)

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

得到

由引理2.1可知

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

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

成立，從而得到

記

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

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

證最優(yōu)性條件（2.3）等價(jià)于

于是SDP的最優(yōu)性條件等價(jià)于式（2.15）的變分不等式問(wèn)題.所以求解半定規(guī)劃最優(yōu)解的問(wèn)題，可以通過(guò)求解變分不等式（2.15）實(shí)現(xiàn)，能夠解決該變分不等式的方法，都可能同時(shí)獲得SDP的最優(yōu)解.而在本文中提出鄰近外梯度算法解決該問(wèn)題.

3　半定規(guī)劃的鄰近外梯度算法

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

3.1半定規(guī)劃的鄰近外梯度算法的實(shí)現(xiàn)

通過(guò)最優(yōu)性條件（2.15），SDP問(wèn)題可等價(jià)轉(zhuǎn)化為一個(gè)定義在有限維歐氏空間中，并在閉凸集?=×Rm上的變分不等式問(wèn)題

其中

由F（u）的定義可知F（u）單調(diào)且Lipschitz連續(xù)［21，22］.本文結(jié)合外梯度算法，構(gòu)造包含原投影區(qū)域的半空間，將投影建立在半空間上，簡(jiǎn)化投影的求解過(guò)程，并對(duì)新的鄰近點(diǎn)序列作相應(yīng)限制.下面給出鄰近外梯度算法具體的實(shí)現(xiàn)過(guò)程.

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

步驟2計(jì)算預(yù)測(cè)點(diǎn)

停，否則轉(zhuǎn)步驟3.

步驟3令rk=，若rk≤v，計(jì)算

步驟4構(gòu)造半空間Hk，

計(jì)算在半空間上Hk投影

計(jì)算下一個(gè)迭代點(diǎn)

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

否則k=k+1，轉(zhuǎn)步驟1.

3.2數(shù)值試驗(yàn)

教學(xué)測(cè)試穩(wěn)定性的統(tǒng)計(jì)研究中有一類(lèi)重要問(wèn)題即教育測(cè)試問(wèn)題（ETP）.為了驗(yàn)證算法的可行性，在Matlab2012中執(zhí)行該算法，在Intel（R），Pentium（R），Core（TM）i7-3520M CPU，2.9GHz，4.00GB內(nèi)存，Windows 7操作系統(tǒng)上進(jìn)行數(shù)值實(shí)驗(yàn).在實(shí)施算法時(shí)，為了與外梯度算法和半定規(guī)劃軟件包SDP packuser內(nèi)點(diǎn)算法的計(jì)算結(jié)果進(jìn)行比較［23-24］，實(shí)驗(yàn)參數(shù)的設(shè)置相同.教育測(cè)試問(wèn)題模型如下.

給定一個(gè)對(duì)稱(chēng)正定矩陣C，求

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

表1：數(shù)值實(shí)驗(yàn)結(jié)果比較

表2：數(shù)值實(shí)驗(yàn)結(jié)果比較

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

4　結(jié)論

本文通過(guò)把求解半定規(guī)劃問(wèn)題有效的轉(zhuǎn)化為求解變分不等式問(wèn)題，把變分不等式的數(shù)值解法從歐式空間推廣到有限維空間，給出了一個(gè)求解半定規(guī)劃問(wèn)題的鄰近外梯度算法.并在算法中考慮不規(guī)則閉凸區(qū)域上投影計(jì)算難的問(wèn)題來(lái)構(gòu)造半空間上的投影，在算法中引入特殊的迭代步長(zhǎng)因子，增加了迭代點(diǎn)的靈活性，通過(guò)數(shù)值實(shí)驗(yàn)說(shuō)明該算法是求解半定規(guī)劃問(wèn)題的一種可行方法.半定規(guī)劃與許多優(yōu)化問(wèn)題有著緊密的聯(lián)系，將半定規(guī)劃和互補(bǔ)問(wèn)題結(jié)合是今后的研究重點(diǎn).

［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］韓喬明.解半定規(guī)劃的二次攝動(dòng)方法［J］.應(yīng)用數(shù)學(xué)學(xué)報(bào)，1999，1：84-90.

［7］關(guān)秀翠，刁在筠.二次半定規(guī)劃問(wèn)題及其投影收縮算法［J］.高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào)，2002，2：97-108.

［8］徐鳳敏，劉三陽(yáng).半定規(guī)劃的一種新算法［J］.西安電子科技大學(xué)學(xué)報(bào)，2000，6：773-777.

［9］韓繼業(yè)，修乃華，戚厚鐸.非線(xiàn)性互補(bǔ)理論與算法［M］.上海：上?？茖W(xué)技術(shù)出版社，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］楊國(guó)平，劉三陽(yáng).半定規(guī)劃問(wèn)題的一種新的預(yù)測(cè)校正算法［J］.應(yīng)用數(shù)學(xué)，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］.系統(tǒng)科學(xué)與數(shù)學(xué)，2013，5：579-584.

［16］張麗麗，李興斯.箱式約束變分不等式的一類(lèi)新光滑gap函數(shù)［J］.應(yīng)用數(shù)學(xué)和力學(xué)，2013，1：27-37.

［17］劉英.Banach空間中關(guān)于變分不等式組與嚴(yán)格偽壓縮映射的粘滯逼近法［J］.應(yīng)用數(shù)學(xué)學(xué)報(bào)，2013，2：324-336.

［18］烏力吉，陳國(guó)慶.箱約束變分不等式的一個(gè)簡(jiǎn)單光滑價(jià)值函數(shù)和阻尼牛頓法［J］.應(yīng)用數(shù)學(xué)和力學(xué)，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］李蕊.半定規(guī)劃的外梯度法研究［D］.西安：西安電子科技大學(xué)碩士學(xué)位論文，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，F(xiàn)uxin 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）主題分類(lèi)號(hào)：90C22O221.2

A

0255-7797（2016）05-1047-09

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

教育部高校博士學(xué)科科研基金聯(lián)合資助項(xiàng)目（20132121110009）；國(guó)家自然科學(xué)基金天元基金（11326224）；遼寧省教育廳基金資助項(xiàng)目（L2012105）.

于冬梅（1986-），女，滿(mǎn)族，遼寧岫巖，博士，主要研究方向：半定規(guī)劃理論與應(yīng)用，錐規(guī)劃.

2010 MR Subject Classification：90C22