基于自適應(yīng)參數(shù)校正策略求解SDP的Mehrotra型內(nèi)點(diǎn)算法

黃方艷，張明望，黃正偉

（1.三峽大學(xué)理學(xué)院，湖北宜昌443002；2.三峽大學(xué)經(jīng)濟(jì)與管理學(xué)院，湖北宜昌443002）

基于自適應(yīng)參數(shù)校正策略求解SDP的Mehrotra型內(nèi)點(diǎn)算法

黃方艷1，張明望1，黃正偉2

（1.三峽大學(xué)理學(xué)院，湖北宜昌443002；2.三峽大學(xué)經(jīng)濟(jì)與管理學(xué)院，湖北宜昌443002）

最近，Salahi對(duì)線性規(guī)劃提出了一個(gè)基于新的自適應(yīng)參數(shù)校正策略的Mehrotra型預(yù)估-校正算法，該策略使其在不使用安全策略的情況下，證明了算法的多項(xiàng)式迭代復(fù)雜界.本文將這一算法推廣到半定規(guī)劃的情形.通過(guò)利用Zhang的對(duì)稱化技術(shù)，得到了算法的多項(xiàng)式迭代復(fù)雜界，這與求解線性規(guī)劃的相應(yīng)算法有相同的迭代復(fù)雜性階.

Mehrotra型算法；半定規(guī)劃；迭代復(fù)雜性；對(duì)稱化技術(shù)

1　引言

自Karmarkar［1］的開(kāi)創(chuàng)性文章發(fā)表以來(lái)，內(nèi)點(diǎn)算法成為最熱門(mén)的研究對(duì)象之一，取得了大量的成果.1991年，Mehrotra［2］提出的預(yù)估-校正算法，也就是所謂的Mehrotra型預(yù)估-校正算法，是內(nèi)點(diǎn)算法用于實(shí)際計(jì)算的一個(gè)里程碑式的成果.由于Mehrotra型預(yù)估―校正算法的優(yōu)良的實(shí)際計(jì)算效果，Mehrotra型預(yù)估-校正算法及其變形算法成為一些著名內(nèi)點(diǎn)算法軟件包的基礎(chǔ)［3-5］.遺憾的是關(guān)于Mehrotra型預(yù)估-校正算法的理論研究卻很匱乏.直到2007年，在文獻(xiàn)［6］中，Salahi等人通過(guò)分析一個(gè)極具啟發(fā)性的數(shù)值實(shí)例發(fā)現(xiàn)：按照Mehrotra的預(yù)估-校正算法中中心參數(shù)的選擇方法，為了使迭代點(diǎn)保持在特定鄰域內(nèi)，算法不得不作過(guò)多的小步迭代（步長(zhǎng)難有下界），而迭代點(diǎn)保持在特定鄰域內(nèi)及步長(zhǎng)有下界對(duì)證明算法的多項(xiàng)式復(fù)雜性及實(shí)際計(jì)算都非常重要.受此數(shù)值實(shí)例啟示，他們?cè)贛ehrotra的算法中加入了“安全策略”來(lái)克服算法的缺陷，在此基礎(chǔ)上提出了一個(gè)改進(jìn)Mehrotra型預(yù)估-校正算法（下稱改進(jìn)Mehrotra型預(yù)估-校正算法）.這樣，既能使迭代點(diǎn)始終在所討論的寬鄰域內(nèi)，又能得到步長(zhǎng)一個(gè)正的下界，進(jìn)而證明了改進(jìn)Mehrotra型預(yù)估-校正算法的迭代復(fù)雜性為O（n2log（x0）Ts0/ε）；通過(guò)對(duì)校正方向的稍加修改，他們將算法的迭代復(fù)雜性降至O（nlog（x0）Ts0/ε）（見(jiàn)文獻(xiàn)［6］）.隨后，Salahi等學(xué)者對(duì)線性規(guī)劃的Mehrotra型預(yù)估-校正算法做了進(jìn)一步研究.在文獻(xiàn)［7］中，Salahi和Amiri基于文獻(xiàn)［6］的思想，提出了一種求解線性規(guī)劃的二階Mehrotra型預(yù)估-校正算法（其要點(diǎn)是在原有的二階Mehrotra型預(yù)估-校正算法中加“安全策略”），并證明了二階算法與文獻(xiàn)［6］的方法有相同的迭代復(fù)雜性.在文獻(xiàn)［8］中，Salahi和Terlaky給出了線性規(guī)劃的Mehrotra型預(yù)估-校正算法的一個(gè)新的改進(jìn)形式.新方法的主要?jiǎng)?chuàng)新之處是在算法的校正步用“障礙參數(shù)的延時(shí)選擇”（Postponing the choice of the barrier parameter）取代文獻(xiàn)［6］中的“安全策略”，在精心給定一個(gè)校正步長(zhǎng)的情況下，通過(guò)求解一個(gè)一維優(yōu)化問(wèn)題，得到目標(biāo)障礙參數(shù)的取值范圍，相應(yīng)地可得到校正步搜索方向，最后證明了新算法與文獻(xiàn)［6］的算法有相同的迭代復(fù)雜性.文章還得到了新算法的超線性收斂性，并給出了數(shù)值實(shí)驗(yàn)結(jié)果.最近，Salahi在文獻(xiàn)［9］中提出了一種新的求解線性規(guī)劃的Mehrotra型預(yù)估-校正算法，其主要?jiǎng)?chuàng)新之處是在算法的校正步利用自適應(yīng)參數(shù)校正策略取代文獻(xiàn)［6］中的“安全策略”，在沒(méi)有采用任何安全策略的情況下，證明了新算法的迭代復(fù)雜性與文獻(xiàn)［6］的迭代復(fù)雜性是一樣的.前面幾項(xiàng)改進(jìn)工作，其基本想法都是設(shè)法使得Mehrotra型預(yù)估-校正算法“既保持迭代點(diǎn)在所討論的寬鄰域內(nèi)，又能得到步長(zhǎng)一個(gè)正的下界”.應(yīng)該指出的是Salahi等人的改進(jìn)Mehrotra型預(yù)估-校正算法文獻(xiàn)［6-7］發(fā)表以后，人們通過(guò)利用Zhang［10］的對(duì)稱化技術(shù)將其推廣到半定規(guī)劃［11-12］，并證明了算法的迭代復(fù)雜性.

基于文獻(xiàn)［9］的思想，本文對(duì)半定規(guī)劃提出了一個(gè)自適應(yīng)校正參數(shù)Mehrotra型預(yù)估校正算法.收斂分析中遇到的主要困難是保持算法迭代方向的對(duì)稱性.為此，采用Zhang［10］的對(duì)稱化技術(shù)，通過(guò)建立和利用一些技術(shù)性引理，證明了算法的迭代復(fù)雜性為O（nlogX0·S0/ε），這與求解線性規(guī)劃的相應(yīng)算法有相同的迭代復(fù)雜性階.

本文將用到如下符號(hào)：Rm表示m維歐式空間.Rn×n表示n×n實(shí)矩陣空間.Sn和Sn++分別表示n×n對(duì)稱矩陣錐和對(duì)稱正定矩陣錐.||·||F和||·||分別表示矩陣的Frobenius范數(shù)和譜范數(shù).對(duì)任意M，N∈Sn，M?N（或M?N）表示M-N是半正定（或正定）矩陣，M·N=Tr（MTN）.對(duì)任意A∈Sn，λi（A）表示A的第i個(gè)特征值，λmin（A）和λmax（A）分別表示A的最小和最大特征值，cond（A）=λmax（A）/λmin（A）表示矩陣A的條件數(shù).X?S表示矩陣X和S的Kronecker積.對(duì)任意X∈Rn×n，vec（X）表示矩陣的X的列展開(kāi).此外，I表示單位矩陣.

2　預(yù)備知識(shí)

本文討論如下標(biāo)準(zhǔn)形式的半定規(guī)劃：

類似于文獻(xiàn)［9］的引理2.2和2.4，可得以下兩個(gè)引理.注意，在以下討論中，取

由引理2.1和引理2.3可得到以下推論.

引理2.4對(duì)算法產(chǎn)生的所有迭代點(diǎn)（X，y，S），方程（11）總有兩個(gè)正根.

綜上，算法框架描述如下：

算法1

3　算法的復(fù)雜性分析

為簡(jiǎn)化主要結(jié)果證明，（9）式中第三式改寫(xiě)為以下等價(jià)式子：

其中，H≡HI是普通對(duì)稱化算子，由矩陣的Kronecker積、vec（·）的定義和（12）式，則有

其中

利用（7）式和（13）式有

為建立算法1的迭代復(fù)雜界，需確定校正步的最大步長(zhǎng)αc的一個(gè)下界，下面幾個(gè)引理起著重要作用.

推論3.3假設(shè)P是N-T尺度矩陣，注意μ=μt，如果σ＞4且γ=1/σ，則有

證明由引理2.2和引理3.2即可得證.

引理3.4假設(shè)P是N-T尺度矩陣，定義

成立的最大步長(zhǎng)αc滿足

定理3.6算法1至多經(jīng)過(guò)

次迭代后，便可得到問(wèn)題（1）和（2）滿足X·S≤ε的ε-近似解.

4　數(shù)值結(jié)果

本節(jié)報(bào)告一些數(shù)值實(shí)驗(yàn)結(jié)果.設(shè)原始問(wèn)題與對(duì)偶問(wèn)題分別按（1）式與（2）式確定，其中

的情形［19］.下面在Matlab R2014 a環(huán)境下驗(yàn)證算法的可行性.容易驗(yàn)證X=I原始可行，y=（1，1，1）T和S=I對(duì)偶可行.取精度ε=10-7和不同的γ，對(duì)本文的算法1與文獻(xiàn)［11］中的算法1（下稱KT算法）進(jìn)行測(cè)試，并對(duì)兩者的測(cè)試結(jié)果進(jìn)行比較（見(jiàn)表1）.從表1可知算法是可行的，迭代次數(shù)與γ有關(guān)，且γ相同時(shí)算法1先于KT算法終止迭代.又因?yàn)镵T算法采取了安全策略，而我們的算法1沒(méi)有采用任何的安全策略，所以本文提出的算法1與KT算法相比具有一定的優(yōu)越性.

表1　本文算法1與KT算法的比較

［1］Karmarkar N K.A new polynomial-time algorithm for linear programming［J］.Combinatorica，1984，4：373-395.

［2］Mehrotra S.On the implementation of a primal-dual interior point method［J］.SIAM Journal on Optimization，1992，2：575-601.

［3］Andersen E D，Andersen K D.The Mosek Interior Point Optimizer for Linear Programming：an Implementation of the Homogeneous Algorithm［M］.Holland：Kluwer Academic Publishers，2000：197-232.

［4］Vanderbei R J.Loqo：an interior-point code for quadratic programming［J］.Optimization Methods and Software，1999，12：451-488.

［5］Zhang Y.Solving large-scale linear programmes by interior point methods under the Matlab environment［J］.Optimization Methods and Software，1999，10：1-31.

［6］Salahi M，Peng J，Terlaky T.On Mehrotra-type predictor-corrector algorithms［J］.SIAM Journal on Optimization，2007，18（4）：1377-1397.

［7］Salahi M，Mahdavi-Amiri N.Polynomial time second order Mehrotra-type predictor-corrector algorithms［J］.Applied Mathematics and Computation，2006，183：646-658.

［8］Salahi M，Terlaky T.Postponing the choice of the barrier parameter in Mehrotra-type predictor-corrector algorithms［J］.European Journal of Operational Research，2007，182：502-513.

［9］Salahi M.New Barrier Parameter Updating technique in mehrotra-type algorithm［J］.Bulletin of the Iranian Mathematical Society，2010，36（2）：99-108.

［10］Zhang Y.On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming［J］.SIAM Journal on Optimization，1998，8：365-386.

［11］Koulaei H M，Terlaky T.On the extension of a mehrotra-type algorithm for semidefinite optization［R］.Hamilton，Ontario，Canada：McMaster University，2007.

［12］Zhang M W.A second order Mehrotra-type predictor-corrector algorithm for semidefinite optimization［J］.Journal of Systems Science Complexity，2012，25：1108-1121.

［13］Roos C，Terlaky T.Theory and Algorithms for Linear Optimization：an Interior Point Approach［M］.Chichester，UK：John Wiley and Sons，1997.

［14］Klerk De E.Aspects of Semidefinite Programming：Interior Point Algorithms and Selected Applications［M］.Dordrecht，The Netherlands：Kluwer Academic Publishers，2002.

［15］Nesterov Y E，Nemirovsky A S.Interior Point Methods in Convex Programming：Theory and Applications［M］.Philadelphia：Society for Industrial and Applied Mathematics，1994.

［16］Wolkowicz H，Saigal R，Vandenberghe L.Handbook of Semidefinite Programming，Theory，Algorithms，and Applications［M］.The Netherlands：Kluwer Academic Publishers，2000.

［17］Horn R A，Johnson C R.Matrix Analysis［M］.New York：Cambridge University Press，1990.

［18］Wright S J.Primal-Dual Interior-Point Methods［M］.USA：SIAM，1997.

［19］Wang G Q，Bai Y Q，Roos C.Primal-dual interior-point algorithms for semi-definite optimization based on a simple kernel function［J］.Journal of Mathematical Modelling and Algorithms，2005，4（4）：409-433.

A mehrotra-type algorithm for SDP based on a new adap-tive updating technique of barrier parameter

Huang Fangyan1，Zhang Mingwang1，Huang Zhengwei2
（1.College of Science，China Three Gorges University，Yichang 443002，China；2.College of Economics and Management，China Three Gorges University，Yichang 443002，China）

Salahi in his recent work proposed a Mehrotra-type predictor-corrector algorithm based on a new adaptive updating technique of barrier parameter for linear program，which enables him to derive the iteration complexity bound of Mehrotra-type algorithm without a safeguard.This paper extends the Mehrotra-type algorithm to semidefinite program.By using Zhang′s general symmetrization scheme，the polynomial iteration complexity bound of the algorithm is obtained，which is of the same order as that of the corresponding algorithm for linear program.

Mehrotra-type algorithm，semidefinite program，iteration complexity，symmetrization scheme

O178；O174.6

A

1008-5513（2015）06-0650-11

10.3969/j.issn.1008-5513.2015.06.014

2015-06-21.

國(guó)家自然科學(xué)基金（71471102）.

黃方艷（1990-），碩士生，研究方向：錐優(yōu)化問(wèn)題的內(nèi)點(diǎn)算法.

張明望（1959-），碩士，教授，研究方向：最優(yōu)化理論與應(yīng)用.

2010 MSC：26D15，26D10