解特殊凸二次半定規(guī)劃的邊界點(diǎn)法

李成進(jìn)

（福建師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350007）

1 前言

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

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

問題（1.1）是特殊的非線性半定規(guī)劃問題，因此可以利用文獻(xiàn)［1］中的過濾集序列線性化方法來求解。但考慮到其特殊結(jié)構(gòu)，故而本文將利用邊界點(diǎn)法對(duì)其進(jìn)行求解。

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

它又等價(jià)與以下的條件：

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

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

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

最后，介紹一下本文的結(jié)構(gòu)：在第二節(jié)中將介紹解問題（1.1）的邊界點(diǎn)法，同時(shí)分析其全局收斂性；而在第三、四節(jié)中分別給出其初步的數(shù)值試驗(yàn)與結(jié)論。

2 邊界點(diǎn)法

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

算法2.1（邊界點(diǎn)法）

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

重復(fù)迭代直至δ＜ε被滿足。

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

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

k=k+1；

結(jié)束。

其中‖·‖F(xiàn)，‖·‖2分別表示矩陣空間的F-范數(shù)與向量空間的2-范數(shù)。算法2.1的運(yùn)行過程中不需要用到文獻(xiàn)［2］中邊界點(diǎn)方法的外部迭代，這是因?yàn)椋?.2）的第一個(gè)等式中包含X。

由構(gòu)造可知，每次由邊界點(diǎn)法產(chǎn)生的迭代點(diǎn)對(duì)X，S滿足

這就是“邊界點(diǎn)”這個(gè)名稱的由來。停止準(zhǔn)則‖φ（X）-b‖≤ε保證迭代點(diǎn)列的極限點(diǎn)會(huì)充分接近問題（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，接下來先介紹文獻(xiàn)中的一個(gè)重要結(jié)論。

引理2.2 對(duì)任意的V，V∈Sn有

類似于文獻(xiàn)［3］中引理2.7的證明過程，可推導(dǎo)下引理。

引理2.3 對(duì)任意的S，S∈有

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

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

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

那么（X，S）是個(gè)不動(dòng)點(diǎn)，即，（X，S）=P（V（S））因此，（X，y，S），其中y=y（S），是問題（1.1）的一個(gè)KKT點(diǎn)。

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

‖P（V（S））-P（V（S*））‖F(xiàn)≤‖V（S）-V（S）*‖F(xiàn)≤‖S-S*‖F(xiàn)聯(lián)立（2.3）與‖S-S*‖F(xiàn)≤‖X-X*，S-S*‖F(xiàn)，可得

成立。從而有

再由（1.2）的第一個(gè)等式，V（S）*的公式，（2.5）以及（2.4）的后一式，可推導(dǎo)出

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

現(xiàn)在，可以來推導(dǎo)本節(jié)的主要結(jié)論了。

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

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

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

聯(lián)立（2.7）的后三個(gè)關(guān)系式與‖Sk-S*‖F(xiàn)≤‖（Xk-Sk）-（X*-S*）‖F(xiàn)，可得序列｛‖（Xk，Sk）-（X*，S*）‖F(xiàn)｝是單調(diào)下降的。因此，

其中（X′，S′）可以取為點(diǎn)列｛（Xk，Sk）｝的任意一個(gè)聚點(diǎn)。由P（V（·））的連續(xù)性可知的像

也是｛（Xk，Sk）｝的一個(gè)聚點(diǎn)。因此有

即，點(diǎn)列（Xk，Sk）收斂到唯一的一個(gè)極限點(diǎn)（，）證畢。

3 結(jié)論

本文給出了解一類特殊凸二次半定規(guī)劃問題的邊界點(diǎn)算法，并證明了其具有全局收斂性。最后，還針對(duì)此算法進(jìn)行了初步的數(shù)值試驗(yàn)，得到的數(shù)據(jù)證實(shí)了邊界點(diǎn)法的有效性。

［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(xiàn) 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）.