一類二次半定規(guī)劃Gauss-Newton方向的存在唯一性

游 揚(yáng)，張圣貴

（1．福州外語外貿(mào)學(xué)院，福建 福州 350202；2.福建師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院）

一類二次半定規(guī)劃Gauss-Newton方向的存在唯一性

游 揚(yáng)1，張圣貴2

（1．福州外語外貿(mào)學(xué)院，福建 福州 350202；2.福建師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院）

本文在半定規(guī)劃中的Gauss-Newton搜索方向的基礎(chǔ)上研究一類特殊的二次半定規(guī)劃（QSDP）求解問題，基于矩陣論和和凸規(guī)劃理論中原始-對偶算法的NT搜索方向?qū)⒋祟惗伟攵ㄒ?guī)劃問題轉(zhuǎn)化為求解線性半定規(guī)劃的最小二乘問題，為了驗(yàn)證此理論的可行性本文驗(yàn)證了Gauss-Newton搜索方向在最小二乘問題中的存在性和唯一性.

半定規(guī)劃；二次半定規(guī)劃（QSDP）；最小二乘問題；線性最小二乘問題（LQ）；Gauss-Newton方向

1 引言

近年來，半定規(guī)劃（SDP）是最優(yōu)化理論領(lǐng)域發(fā)展較完善、應(yīng)用最廣泛的規(guī)劃.伴隨著半定規(guī)劃的發(fā)展，原始對偶內(nèi)點(diǎn)算法已成為解決此類問題最有效的算法中的一員.20世紀(jì)90年代末隨著線性半定規(guī)劃的日趨成熟，人們自然而然地開始考慮更為復(fù)雜的半定規(guī)劃——非線性半定規(guī)劃，其中最為簡單的一種規(guī)劃就是二次半定規(guī)劃（QSDP）.它在系統(tǒng)論、控制論等諸多領(lǐng)域具有著廣泛的應(yīng)用，而且憑借著矩陣?yán)碚摵驮紝ε妓惴ㄖ蠳T方向的相關(guān)理論可以將二次半定規(guī)劃轉(zhuǎn)化為線性半定最小二乘問題，使得二次半定規(guī)劃在證券，金融風(fēng)險(xiǎn)分析，穩(wěn)健性二次優(yōu)化等領(lǐng)域中起著非常重要的作用.

在半定規(guī)劃的原始對偶內(nèi)點(diǎn)算法中目前為止已經(jīng)被驗(yàn)證的應(yīng)用最為廣泛的搜索方向主要有如下四種：①AHO方向［1］；②K..S..H方向［2］；③H..K..M方向［3］；④NT方向［4］.其中NT方向和H..K..M方向已被人成功地推廣到某類二次半定規(guī)劃上［6，12］.到目前為止NT方向被認(rèn)為是此四個(gè)方向中應(yīng)用最廣泛最有效的的搜索方向.在找尋搜索方向時(shí)采用牛頓法，借助對稱化將互補(bǔ)松弛條件用來求解KKT系統(tǒng)，搜索方向的合理性雖然得到了保障，但求解的過程不僅增加計(jì)算的復(fù)雜性而且容易導(dǎo)致KKT系統(tǒng)的不穩(wěn)定.故而此方法還尚待完善.在文獻(xiàn)［5］中SergeKruk等學(xué)者提出了用于求解線性SDP的新搜索方向即Gauss-Newton方向.若改用此方向可以避免松弛條件的對稱化過程，計(jì)算的復(fù)雜性就得以降低，系統(tǒng)的穩(wěn)定性也相應(yīng)的增強(qiáng).基于此，，本文選取具有特殊算子的一類QSDP，以NT方向?yàn)榛A(chǔ)將其推廣成二次半定規(guī)劃中的Gauss-Newton方向，并運(yùn)用優(yōu)化中的相關(guān)理論證明了Gauss-Newton方向的存在唯一性.

2 QSDP的Gauss-Newton搜索方向的存在唯一性

二次半定規(guī)劃的一般形式為

其中Q是Sn到Sn的具有半正定性質(zhì)的自伴隨線性算子，X≥0規(guī)定X為半正定矩陣，Bi是n階實(shí)對稱陣（i=1，…，k），且B1，…，Bk是線性無關(guān)的，ai為n維列向量.

再由KKT條件以及類似于文獻(xiàn)［6］的處理方法利用松弛條件對上述半定規(guī)劃（2）進(jìn)行改寫，得到了擾動(dòng)方程組

上述系統(tǒng)（3）的解被稱為中心路徑，記為（X（μ），λ（μ），Z（μ），其中μ為中心路徑參數(shù).

若規(guī)定原始對偶算法中變量X，Z迭代過程產(chǎn)生的下一步步長分別為ΔX，ΔZ，故此步長變量在理想情形下即為如下系統(tǒng)的解［7］

正是因?yàn)橄到y(tǒng)（4）的非線性，zhang等學(xué)者在文獻(xiàn)［8］中利用互補(bǔ)松弛條件的對稱化這一技巧將此系統(tǒng)轉(zhuǎn)化為線性系統(tǒng).但這一過程卻大大增加了系統(tǒng)計(jì)算的復(fù)雜性，在1998年Kruk于文獻(xiàn)［5］中將此非線性系統(tǒng)問題轉(zhuǎn)化為最小二乘問題來考慮，并在文中嚴(yán)謹(jǐn)?shù)刈C明了求解此類問題的Gauss-Newton方向的存在性和唯一性.基于上述事實(shí)，本文將此方法加以推廣用以求解下列最小二乘問題（5），并推導(dǎo)出求解系統(tǒng)（3）相應(yīng)的Gauss-Newton方向，最后論證該搜索方向的存在性和唯一性.

系統(tǒng)（4）可等價(jià)地改寫為如下最小二乘問題：

由文獻(xiàn)［6］中的NT方向，定義如下矩陣

從而系統(tǒng)（6）可等價(jià)轉(zhuǎn)化為

由于問題（7）中含有非線性項(xiàng)WX，WZ，直接求解此最小二乘問題很繁瑣.文獻(xiàn)［5］已經(jīng)證明忽略問題中出現(xiàn)的非線性項(xiàng)WX，WZ不會(huì)改變該問題本身固有屬性，并忽略此項(xiàng)后，因?yàn)樗》稊?shù)的類型決定了該最小二乘問題的最優(yōu)解，故當(dāng)所給問題的范數(shù)類型確定時(shí)問題也隨之被唯一確定.這里選取由內(nèi)積導(dǎo)出的范數(shù).內(nèi)積做如下定義：：此內(nèi)積可被看作是由障礙函數(shù)f（V）=-lndet（V）的Hessian矩陣誘導(dǎo)出的局部范數(shù).因?yàn)閒的Hessian矩陣V的值是一個(gè)線性的算子▽2f（V）：H→V-1HV-1.所以我們就相應(yīng)的得到如下最小二乘問題［7］

這里最小二乘問題的范數(shù)取F-范數(shù)［9］.為了方便敘述，

如果問題（10）只存在零解，我們便可以推出問題（9）有唯一解.因此下面主要驗(yàn)證問題（10）只存在零解.因?yàn)閱栴}（10）

3 問題與總結(jié)

本文以線性半定規(guī)劃的Gauss-Newton方向以及二次半定規(guī)劃 （QSDP）的NT搜索方向的理論為基礎(chǔ)，將Gauss-Newton方向從LSDP推廣到一類特殊的QSDP，并驗(yàn)證了Gauss-Newton方向的存在性及其唯一性.但本文中只給出了與原始問題等價(jià)的線性最小二乘問題，在文獻(xiàn)［11］中研究者A.Bjorck提出了用矩陣QR分解簡化求解此類問題，若可以將其推廣并應(yīng)用到本文所提的優(yōu)化問題中，便將進(jìn)一步完善本文所提理論的系統(tǒng)性.

〔1〕F.Alizadeh，J.P.A.Haeberly and M.L.Overton.Primal dual methods for semidefinite programming：convergence rates，stability and numerical results［J］.SIAM J.Optim.，1998，8（3）：746-768.

〔2〕R.D.C.Monteiro.Primal dual path following algorithms for semidefinite programming［J］.SIAM J.Optim.，1997，7：663-678.

〔3〕M.Kojima，S.Shindoh and S.Hara.Interiorpoint methods for the monotone semidefinite complementarity promble in symmtric matrices［J］.SIAM J.Optim.，1997，7：86-125.

〔4〕M.J.Todd， K.C.Toh and R.H.Tutuncu. On the Nesterov-Todd direction in semidefinite programming［J］. SIAM J.Optim.，1998，8（3）：769-796.

〔5〕S.Kruk，M.Muramatsu，F(xiàn).Rendletal.TheGauss-Newton direction in semidefinite programming［J］. Optimization Methods and Software，2001，issue 1：1-28.

〔6〕游揚(yáng)，張圣貴.一類二次半定規(guī)劃內(nèi)點(diǎn)算法的K..S..H搜索方向的存在唯一性［J］.福建師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，28（1）：16-20.

〔7〕E.deKlerk，J.Peng，C.Roos， T.Terlaky.A scaled Gauss-Newton Primal-DualSearch Direction for Semidefinite Optimization.http：//citeseerx.ist.psu. edu/ viewdoc.

〔8〕Y.Zhang.On extending some primal-dualinterior point algorithms from linear programming to semidefinite programming.SIAM Journal on Optimization，1998，8（2）：365-386.

〔9〕陳寶林.最優(yōu)化理論與算法（第2版）［M］.北京：清華大學(xué)出版社，2005.10.

〔10〕Dimitri P.Bertsekas with Angelia Nedic and Asuman E. Ozdaglar.Convex Analysis and Optimization：凸分析與優(yōu)化（第二版）［M］.北京：清華大學(xué)出版社，2006.2.

〔11〕A.Bjorck.NumericalMethods for Least Squares Problems.SIAM，Philadelphia，1996.

〔12〕黃靜靜，王愛文.二次半定規(guī)劃的原始對偶內(nèi)點(diǎn)算法的H..K..M搜索方向的存在唯一性 ［J］.數(shù)學(xué)實(shí)踐與認(rèn)識，2008，38（18）：233-238.

O221

A

1673-260X（2015）05-0001-03

福建省教育廳B類項(xiàng)目（JB13364S）資助