一種新的求解CQSDP的全-Newton步內(nèi)點(diǎn)算法

李 鑫 季 萍 張明望

（三峽大學(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ù)雜性

1 引 言

本文討論如下標(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 預(yù)備知識(shí)

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．

3 CQSDP的全-Newton步原始-對(duì)偶內(nèi)點(diǎn)算法

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)的算法為小步校正算法．

4 算法分析

首先，我們引入記號(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）階段性成果