一類帶有混合約束的二次半定規劃及其投影收縮算法

田朝薇，宋海洲

（華僑大學數學科學學院，福建泉州362021）

一類帶有混合約束的二次半定規劃及其投影收縮算法

田朝薇，宋海洲

（華僑大學數學科學學院，福建泉州362021）

研究帶有線性等式及線性不等式約束的二次半定規劃問題.討論對偶理論、最優性條件及其等價的單調變分不等式，給出相應的投影收縮算法.經收斂性分析，可得該算法是全局收斂的.

二次半定規劃；投影方程；變分不等式；投影收縮算法

半定規劃在系統論、控制論、組合優化、特征值優化等諸多領域中有著廣泛的應用，而且它有行之有效的多項式時間算法.目前，研究較多的是在滿足約束對稱矩陣的仿射組合半正定的條件下，使線性函數極小化，即線性半定規劃問題［1－3］.在文［4］給出的求解半定規劃的二次攝動方法中，其攝動問題的對偶規劃可轉化為一個只有變量半正定約束的二次半定規劃問題（QSDP）.文［5］在文［4］基礎上加以等式約束進行討論.本文在文［5］的基礎上加上不等式約束，討論對應的投影收縮算法.

1 二次半定規劃問題

考慮二次半定規劃問題，即

式中：C，X均為n階實對稱矩陣；vec（X）表示由矩陣X的列疊成的n2維列向量，并且Rl×n2；Aj（j＝1，…，l）；Fi（i＝1，…，m）；Ek（k＝1，…，h）；b∈Rl；d∈Rm；g∈Rh；X≥0表示矩陣X是半正定的.A·B＝∑i，jAi，jBi，j＝tr（ATB），矩陣運算A·B的定義為矩陣A，B的內積，tr為矩陣的跡.

假設Fi（i＝1，…，m）線性獨立，對于問題（1），因為ATA是對稱半正定的，其目標函數是一個凸二次函數，而且矩陣的半正定約束也是凸的.因此，式（1）是一個凸二次優化問題.

2 對偶理論

若引入拉格朗日乘子λ∈Rm，μ∈Rh，Z＝ZT∈Rn×n，且μ≥0，Z≥0，則二次半定規劃（1）的拉格朗日函數為

易知，式（2）也是一個二次半定規劃問題，其目標函數為拉格朗日函數L（X，λ，μ，Z）在可行域上的簡化.

引理1［1］設A和B是兩個n階實對稱矩陣，若A≥0，B≥0，則A·B≥0.

由凸規劃的對偶理論，有如下的弱對偶定理.

定理1 設X為二次半定規劃問題（1）的可行解，X，λ，μ，Z為對偶問題（2）的可行解，則有

證明 設Y為二次半定規劃（1）的可行解，X，λ，μ，Z為對偶問題的（2）的可行解.由f（X）的凸性，得?X，Y∈D，則

D＝｛X＝XT∈Rn×n｜Fi·X＝di，i＝1，…，m；Ek·X≤gk，k＝1，…，h；X≥0｝

為問題（1）的可行域，有

3 投影收縮算法

在問題（1）的不等式約束中加入松弛變量γ∈Rh且γ≥0，則式（1）變為

設S＝｛X∈Rn×n｜X＝XT≥0｝為n階實對稱半定矩陣的集合.

引理2［1］設A∈S，B∈S，則A·B＝0當且僅當AB＝0.

引理3［6］若A∈S，B∈S，則AB＝0當且僅當E（A）＝0.其中：E（A）＝A－PS［A－B］，PS表示到S上的正交投影.

由引理2，3可知，最優性條件（6）等價于投影方程［6］，即S（n＋h）×（n＋h）×R（m＋h），Ih×h為h階單位矩陣.因為M半正定，所以投影方程（7）實際是一個單調線性投影方程.由文［7］可知，方程（7）與變分不等式

等價.其中：u＊∈Ω＊，Ω＊為投影方程（7）的解集合.因此，變分不等式（8）是單調線性變分不等式，可利用投影收縮算法求解二次半定規劃問題（4）.

另外，對于β＞0和任意的u∈Ω［4］，有

其分別與式（8）和式（7）等價.

下面給出求解單調線性變分不等式（8）的投影收縮算法.

給定初始點μ0∈Ω，參數β＞0和要求的精度ε＞0，則有如下3個步驟.

（1）方向和步長可按如下3種方法選擇：

（a）當Q＝I時，有

其中：e（uk，β）＝uk－PΩ［uk－β（Muk＋q）］，e（uk）＝e（uk，1），即迭代過程中投影方程的偏差.

（2）迭代格式為

（3）停止準則.對給定精度ε＞0，當‖e（uk）‖≤ε時，算法停止.

4 算法的收斂性分析

［1］ HELMBERG C.Semidefinite programming for combinatorial optimization［M］.Berlin：Konrad－Zuse－Zentrum for Information Stechnik，2000.

［2］ VANDENBERGHE L，BOYD S.Semi－definite programming［J］.SIAM Review，1996，38（1）：49－95.

［3］ ALIZADEH F.Interior point methods in semi－definite programming with application to combinatorial optimization［J］.SIAM J on Optim，1995，5（1）：13－51.

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

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

［6］ HAN Q.Projection and contraction methods for semi－definite programming［J］.Appl Math Compute，1998，95（2／3）：275－289.

［7］ HARKER P T，PANG J S.Finite dimensional variational inequality and nonlinear complementary problems：A survey of theory algorithms and applications［J］.Mathematical Programming，1990，48（1／2／3）：161－220.

［8］ HE B.Solving a class of linear projection equations［J］.Numer Math，1994，68（1）：71－80.

［9］ HE B.A new method for a class of linear variational inequalities［J］.Math Programming，1994，66（2）：137－144.

A Class of Quadratic Semi－Definite Programming with Mixed Constraints and Its Projection and Contraction Algorithm

TIAN Zhao－wei，SONG Hai－zhou
（School of Mathematical Sciences，Huaqiao University，Quanzhou 362021，China）

In this paper，we discuss a class of quadratic semi－definite programming problem with linear inequality constraints and linear inequality constraints.The duality theories are presented.After proving the equivalence of its optimality conditions and monotonous linear variational inequalities，we present its projection and contraction algorithm.It is proved that the algorithm is global convergence after analyzing its convergence.

quadratic semi－definite programming problem；projection equation；variational inequalities；projection and contraction algorithms

O 221.2

A

（責任編輯：陳志賢 英文審校：張金順，黃心中）

1000－5013（2011）01－0113－05

2009－01－04

田朝薇（1977－），女，講師，主要從事運籌與優化的研究.E－mail：tzhw＠hqu.edu.cn.

福建省自然科學基金資助項目（Z0511028）