基于半定規劃原始對偶內點法的一種新的核函數

陳言

〔關鍵詞〕 半定規劃；原始對偶內點法；核函數

〔中圖分類號〕 G643.8 〔文獻標識碼〕 A

〔文章編號〕 1004—0463（2014）22—0092—02

迄今為止，半定規劃問題（SDP）成為了數學規劃領域最熱門的研究課題之一.半定規劃之所以得到越來越多的研究者的關注得益于以下的原因：首先，在Karmarkar的突破性的文章中，他提出了一種有效的處理線性規劃問題的多項式算法——內點法（IPM）.在這之后，許多的研究者比如Nesterov、Nemirovsky和Todd開始研究和分析如何去利用內點法對有效地解決各種各樣的凸規劃問題，比如二階錐規劃和半定規劃.其次，半定規劃在各個領域都有著廣泛的應用，比如工程領域和數據結構領域.在本文中，我們利用原始對偶內點算法去求解半定規劃問題.在理論分析中，我們給出了一種基于原始對偶內點法的新的核函數.我們考慮的半定規劃問題（P）及對偶問題（D）如下：

（P）minC·X （D）maxbty

s.t.Ai·X=bi，i=1，2，……，m s.t.■yiAi+S=C

X？叟0. S？叟0.

在這里Ai∈Sn，并且假設他們是線性無關的，其中b∈Rm，X∈■，S∈Sn.Nesterov和Nemirovsky在1988年研究了障礙函數的自協調性，他們認為內點法從理論上講能夠應用與所有的凸優化問題.因為半定規劃是線性規劃的推廣，所以基于線性規劃的內點法也能夠被推廣至求解半定規劃.基于大多數線性規劃問題的原始對偶內點法利用一個經典的對數障礙函數如下：

？椎c（x，s，？滋）=■-■log（■）-n.

通過引入向量如下：

v=■，

并且定義如下函數：

？準c（t）=■-log（t），t>0

上述函數成為對數障礙函數的核函數，能夠被表達為向量的函數，形式如下：

？椎c（x，s，？滋）=2？準c（v）=2■？準c（vi）

這個經典的核函數已經被證明基于大步迭代和小步迭代的迭代上界分別為O（nlog（■））和O（■log（■））.盡管比起小步迭代，大步迭代有著更好的迭代上界，但是上面的結果并不是令人滿意的.因此無論是基于半定規劃還是線性規劃，一個新的研究方向是如何找到一種更好的核函數，使得基于這種核函數的原始對偶算法有著更小的理論迭代上界，下表是一些來自不同文獻[4-7]的研究成果：

表1 一些核函數的重要結果

■

在本文中，我們提出的新的核函數如下所示：

？準（t）=■-■loglog（e-1）t+1.

這個核函數并沒有在其他的文獻中出現過，我們能夠證明這個核函數有著較好的迭代上界.在大步迭代中它的理論迭代上界是■■32■（V）+1+32e）log（■）.這是本文中給出的新的結果.在本文中■是指每個分量都大于等于0的維向量，而是指每個分量都大于0的n維向量。Sn，■，■分別表示對稱矩陣，半定矩陣，和正定矩陣全體構成的錐.對于對稱矩陣A，B A？叟B，A？叟B分別指A-B是半定矩陣和正定矩陣.A·B=Tr（AtB），對于任何的V∈■，我們假定V的特征值是按照單調遞減的順序排列，即？姿1（V）>？姿2（V）…>？姿3（V）.

本文基于半定規劃問題給出了原始對偶內點法的一種新的核函數，并在理論上推導了其迭代上界.其理論分析步驟和復雜性分析結果[8-10]如下：

第一步：輸入核函數，更新參數？茲，0<？茲<1，截止參數？子和精度參數？著.

第二步：求解方程-■？準'（t）=s，如果不能得到反函數的解析解，則需要估計反函數的上下界.

第三步：計算最優的迭代步，并且在對核函數的下降做出估計，通過求解

f（■）？燮-■.

第四步：估計的下界.

？啄（V）？叟-■.

第五步：利用第三步和第四步的結果估計

f（■）？燮-k？準c（V）1-？酌.

第六步：估計核函數的上界

？準c（v+）？燮L？準（n，？茲，？子）=n？準（■）.

第七步：計算總共的迭代步數

■log■？燮■■ log■.

第八步：代入新的核函數計算大步迭代上界為.

■■32■+1）+32elog（■）.

？笙 編輯：謝穎麗endprint