基于半定規(guī)劃原始對偶內點法的一種新的核函數(shù)

陳言

〔關鍵詞〕 半定規(guī)劃；原始對偶內點法；核函數(shù)

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

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

迄今為止，半定規(guī)劃問題（SDP）成為了數(shù)學規(guī)劃領域最熱門的研究課題之一.半定規(guī)劃之所以得到越來越多的研究者的關注得益于以下的原因：首先，在Karmarkar的突破性的文章中，他提出了一種有效的處理線性規(guī)劃問題的多項式算法——內點法（IPM）.在這之后，許多的研究者比如Nesterov、Nemirovsky和Todd開始研究和分析如何去利用內點法對有效地解決各種各樣的凸規(guī)劃問題，比如二階錐規(guī)劃和半定規(guī)劃.其次，半定規(guī)劃在各個領域都有著廣泛的應用，比如工程領域和數(shù)據(jù)結構領域.在本文中，我們利用原始對偶內點算法去求解半定規(guī)劃問題.在理論分析中，我們給出了一種基于原始對偶內點法的新的核函數(shù).我們考慮的半定規(guī)劃問題（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年研究了障礙函數(shù)的自協(xié)調性，他們認為內點法從理論上講能夠應用與所有的凸優(yōu)化問題.因為半定規(guī)劃是線性規(guī)劃的推廣，所以基于線性規(guī)劃的內點法也能夠被推廣至求解半定規(guī)劃.基于大多數(shù)線性規(guī)劃問題的原始對偶內點法利用一個經(jīng)典的對數(shù)障礙函數(shù)如下：

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

通過引入向量如下：

v=■，

并且定義如下函數(shù)：

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

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

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

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

表1 一些核函數(shù)的重要結果

■

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

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

這個核函數(shù)并沒有在其他的文獻中出現(xiàn)過，我們能夠證明這個核函數(shù)有著較好的迭代上界.在大步迭代中它的理論迭代上界是■■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）.

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

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

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

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

f（■）？燮-■.

第四步：估計的下界.

？啄（V）？叟-■.

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

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

第六步：估計核函數(shù)的上界

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

第七步：計算總共的迭代步數(shù)

■log■？燮■■ log■.

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

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

？笙 編輯：謝穎麗endprint