劉瑞娟, 吳業(yè)軍 , 張　勇

(南京工程學(xué)院 數(shù)理部，江蘇 南京 210067)

?

二階錐規(guī)劃求解的新光滑牛頓算法

劉瑞娟, 吳業(yè)軍 , 張勇

(南京工程學(xué)院 數(shù)理部，江蘇 南京 210067)

研究一個(gè)新的求解二階錐規(guī)劃的光滑牛頓法,算法采用一個(gè)新的價(jià)值函數(shù),同時(shí)利用一個(gè)擾動(dòng)的牛頓方程去獲得搜索方向.在不需要滿足嚴(yán)格互補(bǔ)的條件下,證明算法是全局和局部二次收斂的,最后數(shù)值實(shí)驗(yàn)表明算法是有效的.

二階錐規(guī)劃；光滑牛頓法；全局收斂；二次收斂

論文考慮如下二階錐規(guī)劃問(wèn)題

(1)

其中：A∈Rm×n,c∈Rn,b∈Rm,Kn?Rn是n維的二階錐，其定義為

(2)

其中：‖·‖表示向量的歐式范數(shù).(P)的對(duì)偶問(wèn)題定義為(D),即下式

(3)

二階錐規(guī)劃在控制、金融、組合優(yōu)化等諸多領(lǐng)域有著廣泛的應(yīng)用，是數(shù)學(xué)規(guī)劃領(lǐng)域備受關(guān)注的一個(gè)方向[1-2].光滑牛頓法是求解二階錐規(guī)劃最有效的方法之一，這類方法將二階錐規(guī)劃問(wèn)題等價(jià)轉(zhuǎn)化成一個(gè)單參數(shù)光滑方程，然后利用牛頓法去求解該方程，當(dāng)參數(shù)趨于零時(shí)，即可得到二階錐規(guī)劃的最優(yōu)解.Chi等[3-4]基于不同的光滑函數(shù)，給出了求解二階錐規(guī)劃的光滑牛頓法，并證明了算法的全局與局部二階收斂性質(zhì).Fang等[5-6]、Tang等[7-10]基于不同的光滑函數(shù)對(duì)二階錐規(guī)劃的光滑算法做了進(jìn)一步的研究.受已有文獻(xiàn)的啟發(fā)，論文給出了一個(gè)新的求解二階錐規(guī)劃的光滑算法，在不需要滿足嚴(yán)格互補(bǔ)條件下，證明了算法是全局和局部二次收斂的.

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

為了簡(jiǎn)單起見(jiàn)，對(duì)任意的x,y,z∈Rn，用(x,y,z)表示(xΤ,yΤ,zΤ)Τ.

其中：i=1,2,?∈Rn-1是滿足‖?‖=1的任意向量.

眾所周知,光滑牛頓法依賴于光滑函數(shù). 論文采用文獻(xiàn)[6]提出的光滑函數(shù),定義如下

(4)

下面定理給出了光滑函數(shù)φ的一些性質(zhì)，其具體證明見(jiàn)文獻(xiàn)[7]中的定理3.3.

定理1設(shè)(μ,x,s)∈R++×Rn×Rn且φ(μ,x,s)由(4)定義，則下面結(jié)論成立

(i) 對(duì)于任意的μ>0, φ(μ,x,s)全局Lipschitz連續(xù)且處處強(qiáng)半光滑.此外，φ(μ,x,s)在任意的(μ,x,s)∈R++×Rn×Rn處連續(xù)可微且雅格比矩陣為

其中

2　算法描述

假設(shè)1(P)和(D)嚴(yán)格可行.

在假設(shè)1下，(P)和(D)都有最優(yōu)解且最優(yōu)值相等[1]，并且二階錐規(guī)劃等價(jià)于其KKT條件

Ax=b,

對(duì)任意z∶=(μ,x,y)∈R+×Rn×Rm，定義函數(shù)H(z):R+×Rn×Rm→R+×Rm×Rn如下

(5)

其中

(6)

由(5)和(6)可知z*∶=(μ*,x*,y*)是H(z)=0的解當(dāng)且僅當(dāng)(x*,y*,c-AΤy*)滿足最優(yōu)性條件(3),即(x*,y*,c-AΤy*)是(P)和(D)的最優(yōu)解. 下面定理給出H(z)的雅各比矩陣及其可逆條件，其具體證明可參見(jiàn)文獻(xiàn)[7]中的引理4.1.

定理2設(shè)z∶=(μ,x,y)∈R+×Rn×Rm且H:R1+n+m→R1+m+n,則有

(i)H(z)是R1+n+m上的全局Lipschitz連續(xù)函數(shù)且處處強(qiáng)半光滑，并且在任意的(μ,x,y)∈R++×Rn×Rm處連續(xù)可微，其雅各比矩陣為

其中

(ii) 如果矩陣A行滿秩，則對(duì)任意的μ>0,有H′(z)可逆.

對(duì)任意的z∶=(μ,x,y)∈R+×Rn×Rm，一般采用如下價(jià)值函數(shù)G1(z)∶=‖H(z)‖2或者G2(z)∶=‖H(z)‖.而論文采用了一個(gè)新的價(jià)值函數(shù)，其定義如下

(7)

下面給出算法的具體描述.

算法1(二階錐規(guī)劃的光滑牛頓法)

步驟0取常數(shù)δ,σ∈(0,1), μ0∈R++， 選取任意的初始點(diǎn)x0∈Rn,y0∈Rm.令z0∶=(μ0,x0,y0). 取常數(shù)τ,γ∈(0,1)，使得γ<μ0且τ+γ<1.令 k∶=0.

步驟1如果‖H(zk)‖=0,則停止迭代.

步驟2令

(8)

其中

(9)

求解方程組

(10)

得到搜索方向Δzk∶=(Δμk,Δxk,Δyk)∈R×Rn×Rm.

步驟3令lk是使得下式成立的最小值

(11)

令αk∶=δlk.

步驟4令zk+1∶=zk+αkΔzk和k∶=k+1.轉(zhuǎn)步驟1.

注傳統(tǒng)的光滑算法[3-10]通常利用如下牛頓方程去獲得搜索方向

(12)

而算法采用了一個(gè)擾動(dòng)的牛頓方程(10)去獲得搜索方向.顯然，如果取τ=0，則(10)即變?yōu)閭鹘y(tǒng)的牛頓方程(12).

引理1令Λk由(9)定義，如果μk≥0,則有

(13)

證明因?yàn)?/p>

故‖H(zk)‖≤G(zk). 又因?yàn)椤?zk)‖≤G(zk), 故可知

這表明對(duì)任意的k≥0, ‖Λk‖≤τ,并且‖Λk‖≤τG(zk)2.因此結(jié)論成立.

引理2設(shè)βk,Λk由(9)定義，則對(duì)任意的k≥0,有

(14)

證明因?yàn)閙in{1,ξ2}≤ξ對(duì)任意的ξ≥0都成立，故由(9)可得

進(jìn)而可知結(jié)論成立.

定理3假設(shè)A行滿秩，對(duì)所有的k≥0，如果zk=(μk,xk,yk)∈R++×Rn×Rm可由算法1產(chǎn)生，則zk+1可由算法1產(chǎn)生，并且zk+1∈R++×Rn×Rm.

(15)

對(duì)任意的α∈(0,1], 定義

則Fk(α)=ο(α),這是因?yàn)棣Ｔ谌我獾膠k∈R++×R2n處連續(xù)可微.因此，對(duì)任意的α∈(0,1],有

(16)

因此，由(15)和(16)可得

(17)

因此，zk+1可由算法1產(chǎn)生，并且zk+1∈R++×Rn×Rm. 證畢.

引理3假設(shè)點(diǎn)列{zk=(μk,xk,yk)}由算法產(chǎn)生，則對(duì)任意的k≥0,有μk≥βk.

因此，由數(shù)學(xué)歸納法可得對(duì)任意的k≥0，有μk≥βk.

3　算法的收斂性分析

由引理3可知，對(duì)任意的k≥0有μk≥βk.故μ*≥μ0β*>0,從而由定理2知H′(z*)存在且可逆.因此，對(duì)于充分大的k，令Δzk=(Δμk,Δxk,Δyk)∈R×Rn×Rm為下面方程組的解

在上式兩端取極限，可知

下面分析算法1的局部收斂性質(zhì).為此，作如下假設(shè)

假設(shè)2假設(shè)z*滿足非奇異條件，即所有的V∈?H(z*)都是非奇異的.

引理4假設(shè)Υk由(9)定義，則對(duì)于充分大的k，有‖Υk‖=Ο(‖H(zk)2‖).

(18)

進(jìn)一步，由H的定義可知μk≤‖H(zk)‖并且‖Γ(zk)‖≤‖H(zk)‖.因此

進(jìn)而由(14)和(18)可知對(duì)于充分大的k，有

定理5(局部收斂性質(zhì))假設(shè)矩陣A行滿秩并且z*是算法1產(chǎn)生的迭代點(diǎn)列{zk}的任意聚點(diǎn).如果假設(shè)2成立，則{zk}二次收斂到z*,即‖zk+1-z*‖=Ο(‖zk-z*‖2).

證明利用引理4，類似于文獻(xiàn)[11]中定理8的證明可以證得結(jié)論成立，此處省略.

4　數(shù)值實(shí)驗(yàn)

為檢驗(yàn)算法1的實(shí)算效果，用Matlab7.0.1編程在電腦上做數(shù)值實(shí)驗(yàn).在所有的實(shí)驗(yàn)中，選擇x0=e∈Rn,y0=0∈Rm作為初始點(diǎn).參數(shù)選擇為μ0=0.01, σ=0.25, δ=0.85, γ=0.001, τ=0.25.終止準(zhǔn)則為‖H(zk)‖≤10-6.

測(cè)試問(wèn)題是隨機(jī)生成的規(guī)模n=(2m)從100到800不等的二階錐規(guī)劃問(wèn)題,每個(gè)規(guī)模的問(wèn)題生成10個(gè)，共生成80個(gè)測(cè)試問(wèn)題， 計(jì)算結(jié)果列于表1.其中AIT和ACPU分別表示算法1求解10個(gè)問(wèn)題所需的迭代次數(shù)和CPU時(shí)間(單位：s)的平均值，“AFV”表示算法1終止時(shí)10個(gè)測(cè)試問(wèn)題的‖H(zk)‖的平均值.從表1可以看出算法對(duì)求解較大規(guī)模的二階錐規(guī)劃問(wèn)題是穩(wěn)定有效的.

表1　算法1求解不同測(cè)試問(wèn)題的結(jié)果

[1]ALIZADEH F, GOLDFARB D.Second-order cone programming[J]. Mathematical Programming, 2003, 95: 3-51.

[2]LOBO M S, VANDENBERGHE L, BOYD S, et al. Applications of second-order cone programming[J]. Linear Algebra and its Applications,1998, 284: 193-228.

[3]CHI X N, LIU S Y. A one-step smoothing Newton method for second-order cone programming[J]. Journal of Computational and Applied Mathematics, 2009, 223: 114-123.

[4]CHI X N, LIU S Y. A non-interior continuation method for second-order cone programming[J]. Optimization, 2009, 58: 965-979.

[5]FANG L, HE G P, HU Y H. A new smoothing Newton-type method for second-order cone programming problems[J]. Applied Mathematics and Computation, 2009, 215: 1020-1029.

[6]FANG L, FENG Z Z. A smoothing Newton-type method for second-order cone programming problems based on a new smoothing Fischer-Burmeister function[J]. Computational and Appl Mathematics, 2011, 30 :569-88.

[7]TANG J Y, HE G P, DONG L, et al. A smoothing Newton method for second-order cone optimization based on a new smoothing function[J]. Applied Mathematics and Computation, 2011, 218: 1317-1329.

[8]TANG J Y, DONG L, FANG L, et al. Smoothing Newton algorithm for the second-order cone programming with a nonmonotone line search[J]. Optimization Letters, 2014, 8: 1753-771.

[9]TANG J Y, DONG L, FANG L, et al. Analysis of a non-monotone smoothing-type algorithm for the second-order cone programming[J]. Applications of Mathematics, 2015, 60 (1): 35-39.

[10]TANG J Y, HE G P, DONG L, et al. A new non-interior continuation method for second order cone programming[J]. Journal of Numerical Mathematics, 2013, 21 (4): 301-24.

[11]QI L, SUN D, ZHOU G. A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities[J].Mathematical Programming, 2000, 87: 1-35.

(責(zé)任編輯朱夜明)

New smoothing Newton algorithm for solving the second-order cone programming

LIU Ruijuan, WU Yejun, ZHANG Yong

(Department of Mathematics and Physics,Nanjing Institute of Technology,Nanjing 210067, China)

In this paper, a new one-step smoothing Newton method was investigated for solving the second-order cone programming(SOCP).It adopted a new smoothing value function and used a Newton equation with disturbance to gain the search direction.Without strict complementarity,it proved that the algorithm was globally and locally quadratically convergent.Finally, numerical experiments demonstrated the feasibility and efficiency of our algorithm.

second-order cone programming;smoothing Newton method;global convergence;quadratucal convergence

10.3969/j.issn.1000-2162.2016.05.002

2016-01-12

國(guó)家自然科學(xué)基金青年科學(xué)基金資助項(xiàng)目(11401301)；南京工程學(xué)院校級(jí)科研基金資助項(xiàng)目 (QKJA201508)

劉瑞娟(1983-)，女，河南安陽(yáng)人，南京工程學(xué)院講師.

O231.2

A

1000-2162(2016)05-0008-06