李 鑫 季 萍 張明望
(三峽大學(xué)理學(xué)院,湖北宜昌 443002)
一種新的求解CQSDP的全-Newton步內(nèi)點(diǎn)算法
李 鑫 季 萍 張明望*
(三峽大學(xué)理學(xué)院,湖北宜昌 443002)
對(duì)凸二次半定規(guī)劃提出了一種新的全-Newton步原始-對(duì)偶內(nèi)點(diǎn)算法.通過(guò)建立和應(yīng)用一些新的技術(shù)性結(jié)果,證明了算法的迭代復(fù)雜性為這與目前凸二次半定規(guī)劃的小步校正內(nèi)點(diǎn)算法最好的迭代復(fù)雜性一致.
凸二次半定規(guī)劃;內(nèi)點(diǎn)算法;全-Newton步;迭代復(fù)雜性
本文討論如下標(biāo)準(zhǔn)形式的凸二次半定規(guī)劃(CQSDP)原始問(wèn)題及其對(duì)偶問(wèn)題.
其中:C, Ai∈Sn且假設(shè)矩陣Ai, i=1,…,m線性無(wú)關(guān),b∈Rm.Ω(X)是Sn→Sn上的一個(gè)自共軛半正定線性算子,即對(duì)任意的A, B∈Sn,有Ω(A)·B=A·Ω(B),Ω(A)·A≥0.為了方便起見(jiàn),我們類似于文獻(xiàn)[1,2],考慮如下特殊的情況,
其中,Hi是Rn×n上的矩陣,l為小于或等于n2的整數(shù).
CQSDP是半定規(guī)劃(SDP)的推廣,它在求解歐幾里德距離矩陣問(wèn)題[3]、最近相關(guān)矩陣問(wèn)題[4]中有重要的應(yīng)用.近些年來(lái),關(guān)于CQSDP的研究,已取得一系重要的成果,詳細(xì)研究見(jiàn)文獻(xiàn)[1,2,5].2003年,Darvay[6]提出了一種基于新的搜索方向(Darvay方向)求解線性規(guī)劃(LP)的原始-對(duì)偶路徑跟蹤內(nèi)點(diǎn)算法,并證明了算法的迭代復(fù)雜性為2006年,Roos[7]對(duì)線性規(guī)劃提出了一種全-Newton步不可行內(nèi)點(diǎn)算法,并得到了算法的迭代復(fù)雜性為2009年,Wang等[8]將Darvay提出的算法[6]推廣到SDP模型中,并得到了與文獻(xiàn)[6]同樣好的迭代復(fù)雜性.2014年,Ahmadi等[9]對(duì)線性規(guī)劃提出了一種基于Darvay方向的全-Newton步不可行內(nèi)點(diǎn)算法,并得到了算法的迭代復(fù)雜性為同年,Wang等[10]提出了一種求解() *P k線性互補(bǔ)問(wèn)題的全-Newton步可行內(nèi)點(diǎn)算法,得到了算法迭代復(fù)雜性為
受其工作的啟發(fā),本文提出了一種新的求解CQSDP的全-Newton步原始-對(duì)偶內(nèi)點(diǎn)算法.由于算法中迭代方向的非正交性,導(dǎo)致相應(yīng)算法的分析有別于LP和SDP的情形.通過(guò)建立和應(yīng)用一些新的技術(shù)性結(jié)果,我們證明了算法的迭代復(fù)雜性結(jié)果為這與目前CQSDP的小步校正內(nèi)點(diǎn)算法最好的迭代復(fù)雜性一致.
本文采用如下記號(hào):A·B=Tr(AB)表示矩陣A與B的內(nèi)積分別表示對(duì)稱,對(duì)稱半正定和對(duì)稱正定的n×n矩陣集合.R表示實(shí)數(shù)集,Rm表示m維向量空間,Rn×n表示n×n實(shí)矩陣集合.符號(hào)和分別表示矩陣X是半正定對(duì)稱矩陣和正定對(duì)稱矩陣.和分別表示矩陣V的特征值,最小特征值和最大特征值.X=diag(x)表示由向量x的分量構(gòu)成的對(duì)角矩陣X.F-范數(shù)表示為||·||F,E表示n×n單位矩陣.符號(hào)A~B表示矩陣A與矩陣B相似,即存在可逆矩陣Z,使得A=ZBZ-1.如果f(x)≥0是一個(gè)實(shí)值函數(shù),那么f(x)=O(x)表示存在正實(shí)數(shù)c,使得()f xcx≤.
2.1 中心路徑
不失一般性,假設(shè)問(wèn)題(P)和(D)滿足內(nèi)點(diǎn)算法條件[11],即存在滿足
若(X,y,S)是問(wèn)題(P)和(D)的可行解,則由對(duì)偶理論知,(X,y,S)是問(wèn)題(P)和(D)的最優(yōu)解的充要條件為:
根據(jù)原始-對(duì)偶內(nèi)點(diǎn)算法的基本思想,用參數(shù)方程XS=μE(μ為正實(shí)數(shù)),來(lái)代替系統(tǒng)(3)中的第三個(gè)等式(互補(bǔ)條件),得到如下系統(tǒng):
由文獻(xiàn)[12]知,若問(wèn)題(P)和(D)滿足內(nèi)點(diǎn)條件,則對(duì)任意的μ>0,系統(tǒng)(4)有唯一解(X(μ),y(μ),S(μ)),稱X(μ)為問(wèn)題(P)的μ-中心,(y(μ),S(μ))為問(wèn)題(D)的μ-中心.μ-中心組成的集合(X(μ),y(μ),S(μ))形成了一個(gè)同倫路徑,稱之為問(wèn)題(P)和(D)的中心路徑.當(dāng)μ→0時(shí),中心路徑的極限值存在.又因?yàn)榇藰O限值滿足互補(bǔ)條件,故此極限點(diǎn)即為問(wèn)題(P)和(D)的最優(yōu)解.
2.2 迭代方向
類似于SDP的情形[8],本文用來(lái)代替XS=μE,其中()ψ·是[0,)+∞上的可導(dǎo)實(shí)值函數(shù),則系統(tǒng)(4)可寫成:
對(duì)系統(tǒng)(5)運(yùn)用牛頓法,得
應(yīng)用文獻(xiàn)[8]中引理2.5并忽略ΔXΔS項(xiàng),有
從系統(tǒng)(7)中容易看出,雖然ΔS是對(duì)稱的,但ΔX不一定對(duì)稱.為了使得ΔX對(duì)稱,本文采用NT對(duì)稱化策略[11].
定義
則矩陣D可以將矩陣X,S尺度化,使之成為同一個(gè)對(duì)稱正定矩陣V,即
于是,我們有
根據(jù)定義1,有
進(jìn)一步,定義
這樣,系統(tǒng)(7)等價(jià)于
由于矩陣Ai線性無(wú)關(guān)及問(wèn)題(P)和(D)滿足內(nèi)點(diǎn)條件,所以對(duì)任意μ>0,系統(tǒng)(10)存在唯一解(DX,Δy,DS)[12]250.再應(yīng)用(9)式便可得到算法的迭代方向(ΔX,Δy,ΔS).
不難看出,若(X,y,S)≠(X(μ),y(μ),S(μ)),則(ΔX,Δy,ΔS)≠(0,0,0).沿此方向取全步長(zhǎng),得到新的迭代點(diǎn),
又因?yàn)?)XΩ是自共軛半正定算子,所以
注1:在LP和SDP情形中[6-9],DX·DS=0,即DX與DS正交,由(12)式可知,對(duì)于CQSDP的情形,DX與DS不再正交,這正是本文新算法與SDP相應(yīng)算法及其分析的主要不同之處.
在算法分析中,我們引入一個(gè)鄰近度量δ(V),其定義為:
容易驗(yàn)證,(,,)X Sδμ當(dāng)且僅當(dāng)V=E,當(dāng)且僅當(dāng)XS=μE.
CQSDP的全-Newton步原始-對(duì)偶內(nèi)點(diǎn)算法的基本框架如下圖1.下一部分我們將證明該算法是良定義的.
Input:
閾值參數(shù)01τ<<;精度參數(shù)0ε>;
障礙校正參數(shù)θ,01θ<<;
嚴(yán)格初始可行點(diǎn)(X0,y0,S0),μ0=1使得
求解系統(tǒng)(10),再應(yīng)用(9)得到算法的迭代方向(ΔX,Δy,ΔS );
更新(X, y, S):=(X, y, S)+(ΔX,Δy,ΔS );
圖1 算法
注2:在算法的復(fù)雜性分析中,閾值參數(shù)τ和障礙校正參數(shù)θ的選取也是至關(guān)重要的.通常,如果θ是一個(gè)與問(wèn)題規(guī)模n無(wú)關(guān)的常數(shù),例如那么稱相應(yīng)的算法為大步校正算法.如果θ的選取依賴于問(wèn)題的規(guī)模n,例如那么稱相應(yīng)的算法為小步校正算法.
首先,我們引入記號(hào)QV:=DX-DS,則
由(12)式,得
引理2 ([8]引理6.3) 如果δ:=δ(X, S;μ)<1,那么全-Newton步是嚴(yán)格可行的.
引理3 ([8]引理6.4)如果δ:=δ(X, S;μ)<1,
下面給出幾個(gè)重要的引理.
那么
引理4 ([8]引理6.5)經(jīng)過(guò)一次全-Newton步迭代后,有
引理5 ([8]引理6.6)如果δ:=δ(X, S;μ)<1,μ+:=(1-θ) μ,其中0<θ<1,那么
引理6 假設(shè)Xk,Sk是新算法第k次迭代生
成的迭代點(diǎn)且μ:=μk,則當(dāng)
時(shí),有kkXSε·≤.
證明 由引理4,知
要使不等式kkXSε·≤成立,則只需證
成立.對(duì)上式兩邊取對(duì)數(shù),得
又因?yàn)?,?dāng)01θ<<時(shí),log(1)θθ --≥.所以有兩邊同除以θ,即引理得證.
[1]Wang G Q,Bai Y Q.Primal-dual Interior-point Algorithm for Convex Quadratic Semi-definite Optimization [J].Nonlinear Analysis:Real World,Applications,2009,71:3389-3402.
[2]Zhang M W.A Large-update Interior-point Algorithm for Convex Quadratic Semi-definite Optimization Based on A New Kernel Function [J].Acta Mathematica Sinica,English Series,2012,28(11):2313-2328.
[3]Aifakin A Y,Khandani A,Wolkowicz H.Solving Euclidean Distance Matrix Completion Problem Via Semi-definite Programming [J].Computation Optimization and Applications,1999,12:13-30.
[4]Qi H,Sun D.A Quadratically Convergent Newton Method for Computing the Nearest Correlation Matrix [J]. SIAM Journal of Matrix Analysis and Application, 2006,28:360-385.
[5]Achache M,Guerra L.A Full-Nesterov-Todd-step Feasible Primal-dual Interior-point Algorithm for Convex Quadratic Semi-definite Optimization [J]. Applied Mathematics and Computation,2014,231:581-590.
[6]Daravy Z.New Interior-point Algorithms in Linear Optimization [J].Advanced Modeling Optimization,2003,5(1):51-92.
[7]Roos.C. A Full-Newton Step O(n) Infeasible Interior-point Algorithm for Linear Optimization [J].SIAM Journal on Optimization,2006,16(4):1110-1136.
[8]Wang G Q,Bai Y Q.A New Primal-dual Path-following Interior-point Algorithm for Semi-definite Optimization [J].Journal of Mathematical Analysis and Applications,2009,353:339-349.
[9]Ahmadi K,Hasani F,Behrouz K.A Full-Newton Step Infeasible Interior-point Algorithm Based on Darvay Directions for Linear Optimization [J]. Journal of Mathematics Modeling and Algorithms,2014,12:191-208.
[10]Wang G Q,F(xiàn)an X J,Zhu D T. New Complexity Analysis of A Full-Newton Step Feasible Interiorpoint Algorithm for P*(k)-LCP [J]. Optimization Letters,2014,DOI 10.1007/s11590-014-0800-4.
[11]Nesterov Y E,Todd M J. Self-scaled Barriers and Interior-point for Convex Programming [J]. Mathematics of Operations Research,1997,22(1):1-42.
[12]Klerk E D. Aspects of Semi-definite Programming:Interior Point Algorithms and Selected Applications [M].Kluwer Academic Publishers,Dordrecht,The Netherlands,2002.
(責(zé)任編輯:于開紅)
A New Full-Newton Step Interior-point Algorithm for Convex Quadratic Semi-definite Programming
LI Xin JI Ping ZHANG Mingwang
(School of Science, Three Gorges University, Yichang Hubei 443002)
In this paper, we propose a new full-Newton step primal-dual interior-point algorithm for solving convex quadratic semi-definite programming. By establishing and using new technical results, we show that the iteration complexity of algorithm asis as good as the currently best iteration complexity for small-update interior-point algorithms of convex quadratic semi-definite programming.
convex quadratic semi-definite programming; interior-point algorithm; full-Newton step; iteration complexity
G812.78
A
1009-8135(2015)03-0031-06
2015-02-25
李 鑫(1989-),男,甘肅武威人,三峽大學(xué)碩士研究生,主要研究最優(yōu)化理論與應(yīng)用.季 萍(1989-),女,湖北武漢人,三峽大學(xué)碩士研究生,主要研究最優(yōu)化理論與應(yīng)用.
張明望(1959-),男,湖北宜昌人,三峽大學(xué)教授,主要研究最優(yōu)化理論及應(yīng)用.
國(guó)家自然科學(xué)基金(71471102)階段性成果
重慶三峽學(xué)院學(xué)報(bào)2015年3期