李 鑫 季 萍 張明望

（三峽大學理學院，湖北宜昌 443002）

一種新的求解CQSDP的全-Newton步內點算法

李 鑫 季 萍 張明望＊

（三峽大學理學院，湖北宜昌 443002）

對凸二次半定規(guī)劃提出了一種新的全-Newton步原始-對偶內點算法．通過建立和應用一些新的技術性結果，證明了算法的迭代復雜性為這與目前凸二次半定規(guī)劃的小步校正內點算法最好的迭代復雜性一致．

凸二次半定規(guī)劃；內點算法；全-Newton步；迭代復雜性

1 引 言

本文討論如下標準形式的凸二次半定規(guī)劃（CQSDP）原始問題及其對偶問題．

其中：C, Ai∈Sn且假設矩陣Ai, i=1,…,m線性無關，b∈Rm．Ω(X)是Sn→Sn上的一個自共軛半正定線性算子，即對任意的A, B∈Sn，有Ω(A)·B=A·Ω(B)，Ω(A)·A≥0．為了方便起見，我們類似于文獻[1，2]，考慮如下特殊的情況，

其中，Hi是Rn×n上的矩陣，l為小于或等于n2的整數(shù)．

CQSDP是半定規(guī)劃（SDP）的推廣，它在求解歐幾里德距離矩陣問題[3]、最近相關矩陣問題[4]中有重要的應用．近些年來，關于CQSDP的研究，已取得一系重要的成果，詳細研究見文獻[1，2，5]．2003年，Darvay[6]提出了一種基于新的搜索方向（Darvay方向）求解線性規(guī)劃（LP）的原始-對偶路徑跟蹤內點算法，并證明了算法的迭代復雜性為2006年，Roos[7]對線性規(guī)劃提出了一種全-Newton步不可行內點算法，并得到了算法的迭代復雜性為2009年，Wang等[8]將Darvay提出的算法[6]推廣到SDP模型中，并得到了與文獻[6]同樣好的迭代復雜性．2014年，Ahmadi等[9]對線性規(guī)劃提出了一種基于Darvay方向的全-Newton步不可行內點算法，并得到了算法的迭代復雜性為同年，Wang等[10]提出了一種求解() *P k線性互補問題的全-Newton步可行內點算法，得到了算法迭代復雜性為

受其工作的啟發(fā)，本文提出了一種新的求解CQSDP的全-Newton步原始-對偶內點算法．由于算法中迭代方向的非正交性，導致相應算法的分析有別于LP和SDP的情形．通過建立和應用一些新的技術性結果，我們證明了算法的迭代復雜性結果為這與目前CQSDP的小步校正內點算法最好的迭代復雜性一致．

本文采用如下記號：A·B=Tr（AB）表示矩陣A與B的內積分別表示對稱，對稱半正定和對稱正定的n×n矩陣集合．R表示實數(shù)集，Rm表示m維向量空間，Rn×n表示n×n實矩陣集合．符號和分別表示矩陣X是半正定對稱矩陣和正定對稱矩陣．和分別表示矩陣V的特征值，最小特征值和最大特征值．X=diag（x）表示由向量x的分量構成的對角矩陣X．F-范數(shù)表示為||·||F，E表示n×n單位矩陣．符號A～B表示矩陣A與矩陣B相似，即存在可逆矩陣Z，使得A=ZBZ-1．如果f（x）≥0是一個實值函數(shù)，那么f（x）=O（x）表示存在正實數(shù)c，使得()f xcx≤．

2 預備知識

2.1 中心路徑

不失一般性，假設問題（P）和（D）滿足內點算法條件[11]，即存在滿足

若（X，y，S）是問題（P）和（D）的可行解，則由對偶理論知，（X，y，S）是問題（P）和（D）的最優(yōu)解的充要條件為：

根據(jù)原始-對偶內點算法的基本思想，用參數(shù)方程XS=μE（μ為正實數(shù))，來代替系統(tǒng)（3）中的第三個等式（互補條件），得到如下系統(tǒng)：

由文獻[12]知，若問題（P）和（D）滿足內點條件，則對任意的μ＞0，系統(tǒng)（4）有唯一解(X(μ),y(μ),S(μ))，稱X(μ)為問題（P）的μ-中心，(y(μ),S(μ))為問題（D）的μ-中心．μ-中心組成的集合(X(μ),y(μ),S(μ))形成了一個同倫路徑，稱之為問題（P）和（D）的中心路徑．當μ→0時，中心路徑的極限值存在．又因為此極限值滿足互補條件，故此極限點即為問題（P）和（D）的最優(yōu)解．

2.2 迭代方向

類似于SDP的情形[8]，本文用來代替XS=μE，其中()ψ·是[0,)+∞上的可導實值函數(shù)，則系統(tǒng)（4）可寫成：

對系統(tǒng)（5）運用牛頓法，得

應用文獻[8]中引理2.5并忽略ΔXΔS項，有

從系統(tǒng)（7）中容易看出，雖然ΔS是對稱的，但ΔX不一定對稱．為了使得ΔX對稱，本文采用NT對稱化策略[11]．

定義

則矩陣D可以將矩陣X，S尺度化，使之成為同一個對稱正定矩陣V，即

于是，我們有

根據(jù)定義1，有

進一步，定義

這樣，系統(tǒng)（7）等價于

由于矩陣Ai線性無關及問題（P）和（D）滿足內點條件，所以對任意μ＞0，系統(tǒng)（10）存在唯一解（DX，Δy，DS）[12]250．再應用（9）式便可得到算法的迭代方向（ΔX，Δy，ΔS）．

不難看出，若（X，y，S）≠（X（μ），y（μ），S（μ）），則（ΔX，Δy，ΔS）≠（0，0,0）．沿此方向取全步長，得到新的迭代點，

又因為()XΩ是自共軛半正定算子，所以

注1：在LP和SDP情形中[6-9]，DX·DS=0，即DX與DS正交，由（12）式可知，對于CQSDP的情形，DX與DS不再正交，這正是本文新算法與SDP相應算法及其分析的主要不同之處．

在算法分析中，我們引入一個鄰近度量δ（V），其定義為：

容易驗證，(,,)X Sδμ當且僅當V=E，當且僅當XS=μE．

3 CQSDP的全-Newton步原始-對偶內點算法

CQSDP的全-Newton步原始-對偶內點算法的基本框架如下圖1．下一部分我們將證明該算法是良定義的．

Input：

閾值參數(shù)01τ＜＜；精度參數(shù)0ε＞；

障礙校正參數(shù)θ，01θ＜＜；

嚴格初始可行點(X0,y0,S0)，μ0=1使得

求解系統(tǒng)(10)，再應用(9)得到算法的迭代方向(ΔX,Δy,ΔS )；

更新(X, y, S):=(X, y, S)+(ΔX,Δy,ΔS )；

圖1 算法

注2：在算法的復雜性分析中，閾值參數(shù)τ和障礙校正參數(shù)θ的選取也是至關重要的．通常，如果θ是一個與問題規(guī)模n無關的常數(shù)，例如那么稱相應的算法為大步校正算法．如果θ的選取依賴于問題的規(guī)模n，例如那么稱相應的算法為小步校正算法．

4 算法分析

首先，我們引入記號QV:=DX-DS，則

由（12）式，得

引理2 （[8]引理6.3） 如果δ:=δ(X, S;μ)＜1，那么全-Newton步是嚴格可行的．

引理3 （[8]引理6.4）如果δ:=δ(X, S;μ)＜1，

下面給出幾個重要的引理．

那么

引理4 （[8]引理6.5）經(jīng)過一次全-Newton步迭代后，有

引理5 （[8]引理6.6）如果δ:=δ(X, S;μ)＜1，μ+:=(1-θ) μ，其中0＜θ＜1，那么

引理6 假設Xk，Sk是新算法第k次迭代生

成的迭代點且μ:=μk，則當

時，有kkXSε·≤．

證明 由引理4，知

要使不等式kkXSε·≤成立，則只需證

成立．對上式兩邊取對數(shù)，得

又因為，當01θ＜＜時，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.

（責任編輯：于開紅）

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-），男，甘肅武威人，三峽大學碩士研究生，主要研究最優(yōu)化理論與應用．季 萍（1989-），女，湖北武漢人，三峽大學碩士研究生，主要研究最優(yōu)化理論與應用．

張明望（1959-），男，湖北宜昌人，三峽大學教授，主要研究最優(yōu)化理論及應用．

國家自然科學基金（71471102）階段性成果