解特殊凸二次半定規劃的邊界點法

李成進

（福建師范大學 數學與計算機科學學院，福建 福州 350007）

1 前言

本文將要考慮的是具有如下形式的凸二次半定規劃問題：

其中，實數a≠0，b∈Rm，C∈Sn，符號＜.，.＞表示Frobenius內積，而Rm，Sn，分別表示m-維實向量空間，n×n實對稱矩陣空間表示空間以及Sn中的半正定矩陣錐。另外，I表示單位矩陣，線性算子φ（X）：=（＜A1，X＞，Λ＜Am，X＞），其中

問題（1.1）是特殊的非線性半定規劃問題，因此可以利用文獻［1］中的過濾集序列線性化方法來求解。但考慮到其特殊結構，故而本文將利用邊界點法對其進行求解。

易知，問題（1.1）的KKT條件為：

它又等價與以下的條件：

A：=（svec（A1），svec（A2），svec（Am））T

則可以得到φ（X）=Asvec（X），φ*（y）=smat（ATy）為了討論方便，假設以下的假定條件成立。

假定1.1 矩陣A滿行秩；且問題（1.1）存在嚴格可行點，即Slater條件成立。

最后，介紹一下本文的結構：在第二節中將介紹解問題（1.1）的邊界點法，同時分析其全局收斂性；而在第三、四節中分別給出其初步的數值試驗與結論。

2 邊界點法

通過條件（1.3）可以很容易地構造出解問題（1.1）的邊界點法：由初始點S0出發，在第k-次迭代中先暫時固定S=Sk然后通過（1.3）的第三式求出yk+1；當yk+1確定下來后可由（1.3）中的第一、二式再求出Xk+1與Sk+1。把上述過程編成程序便可得到以下的邊界點法。

算法2.1（邊界點法）

取ε＞0，k=0，Sk=0，δ≥ε；

重復迭代直至δ＜ε被滿足。

求解yk+1：AATyk+1=ab-Asvec（Sk-C）；

δ＝‖φ（Xk+1）-b‖/（1+‖b‖2）；

k=k+1；

結束。

其中‖·‖F，‖·‖2分別表示矩陣空間的F-范數與向量空間的2-范數。算法2.1的運行過程中不需要用到文獻［2］中邊界點方法的外部迭代，這是因為（1.2）的第一個等式中包含X。

由構造可知，每次由邊界點法產生的迭代點對X，S滿足

這就是“邊界點”這個名稱的由來。停止準則‖φ（X）-b‖≤ε保證迭代點列的極限點會充分接近問題（1.1）的可行域。

定義y（S）：=（AAT）-1（b-Asvec（S-C）），V（S）：=smat（AT（y（S）））-C=smat［AT（AAT）-1b-AT（AAT）-1Asvec（S-C）］-C，P（V）：=（V1，V2）：=（a-1（V）；（-V））

以及M：=AT（AAT）-1A，接下來先介紹文獻中的一個重要結論。

引理2.2 對任意的V，V∈Sn有

類似于文獻［3］中引理2.7的證明過程，可推導下引理。

引理2.3 對任意的S，S∈有

證明：直接計算可得V（S）-V（）=smat（Msvec（-S））而M是一個譜半徑為1的正交投影矩陣，從而有

上述引理說明算子P（V（·））是收縮的，這對于邊界點法的全局收斂性分析是至關重要的。

引理2.4 設（X*，y*，S*）其中y*=y（S*）是問題（1.2）的一個解并且X，S∈，XS=0。如果

那么（X，S）是個不動點，即，（X，S）=P（V（S））因此，（X，y，S），其中y=y（S），是問題（1.1）的一個KKT點。

證明：由引理2.2與引理2.3可知

‖P（V（S））-P（V（S*））‖F≤‖V（S）-V（S）*‖F≤‖S-S*‖F聯立（2.3）與‖S-S*‖F≤‖X-X*，S-S*‖F，可得

成立。從而有

再由（1.2）的第一個等式，V（S）*的公式，（2.5）以及（2.4）的后一式，可推導出

聯立（2.6）式與X，S∈，XS=0可得到（X，S）=PV（S）證畢。

現在，可以來推導本節的主要結論了。

定理2.5 從任意一個起始點（X0，y0，S0）開始迭代，由算法2.1產生的迭代點列（Xk，yk，Sk）收斂到點（X*，y*，S*）∈Θ其中Θ表示（1.2）的解集。

證明：對任意的（X*，y*，S*）∈Θ由P（V（·））的收縮性可得

從而有｛Sk｝是一個緊集.由（2.7）的后三個關系式與集合｛Sk｝的緊性可推導出點列｛（Xk，Sk）｝是一緊集，故而至少存在一個聚點，不妨設其中｛kj｝是指標集｛k｝的某個子集。由算法2.1中對Xk，Sk的迭代更新可知，且＜，＞=0。

聯立（2.7）的后三個關系式與‖Sk-S*‖F≤‖（Xk-Sk）-（X*-S*）‖F，可得序列｛‖（Xk，Sk）-（X*，S*）‖F｝是單調下降的。因此，

其中（X′，S′）可以取為點列｛（Xk，Sk）｝的任意一個聚點。由P（V（·））的連續性可知的像

也是｛（Xk，Sk）｝的一個聚點。因此有

即，點列（Xk，Sk）收斂到唯一的一個極限點（，）證畢。

3 結論

本文給出了解一類特殊凸二次半定規劃問題的邊界點算法，并證明了其具有全局收斂性。最后，還針對此算法進行了初步的數值試驗，得到的數據證實了邊界點法的有效性。

［1］C.J.Li and W.Y.Sun，On filter-successive linearization methods for nonlinear semidefinite programming［J］.Sci，2009，（39）.

［2］J Povh，F Rendl，A Wiegele.A boundary point method to solve semidefinite programs［J］.Computing，2006（78）.

［3］Z Wen，D Goldfarb，W Yin.Alternating direction augmented lagrangian methods for semidefinite programming［J］.preprint，2009，（10）.