約束優(yōu)化問題的內(nèi)點(diǎn)正則牛頓法

劉三明

(上海電機(jī)學(xué)院數(shù)理教學(xué)部,上海 200240)

0 前言

對(duì)于二次可微的強(qiáng)凸函數(shù),Newton方向是下降方向,當(dāng)初始點(diǎn)充分靠近極小點(diǎn)時(shí),Newton法是收斂的。但當(dāng)初始點(diǎn)遠(yuǎn)離極小點(diǎn)時(shí),其收斂性不能保證。為此,在牛頓法中引入步長(zhǎng)因子,得到保證全局收斂的阻尼Newton法。當(dāng)函數(shù)不是強(qiáng)凸函數(shù)時(shí),Newton方向不一定是下降方向。為了保證Newton法的全局收斂性,對(duì)Hessian矩陣采用Levenberg-Marquardt正則化方法[1]。文獻(xiàn)[2]對(duì)Newton法提出了三次正則化方法。在每次迭代時(shí),只需求解 1個(gè)與牛頓法相同的二次函數(shù)的無(wú)約束最優(yōu)化問題,但其正則項(xiàng)是三次的。

文獻(xiàn)[3]中提出了一種求解無(wú)約束凸規(guī)劃最優(yōu)解的正則Newton法,該方法不要求函數(shù)是強(qiáng)凸的,且具有全局收斂性。在正則 Newton法中,凸函數(shù)在一點(diǎn)的正則化基于近似點(diǎn)算法[3-6],而近似參數(shù)取為該點(diǎn)梯度的模,即凸函數(shù)f(x)在點(diǎn)x處的正則化函數(shù)為:

通過上述方法,文獻(xiàn)[7]給出了求解任意凸規(guī)劃minx∈Rnf(x)的具有全局收斂性的Newton法。

本文考慮具有不等式約束的凸規(guī)劃問題:

其中,x∈Rn,f,gj(j=1,2,…,m):Rn→R是凸函數(shù)。

對(duì)凸規(guī)劃問題(P),把對(duì)數(shù)障礙函數(shù)法同正則Newton法結(jié)合起來,提出了求解具有不等式約束的凸規(guī)劃問題(P)的內(nèi)點(diǎn)正則Newton法?？梢宰C明該算法具有全局收斂性。

1 內(nèi)點(diǎn)正則New ton法的建立

對(duì)問題(P),作如下假設(shè)(A):

(1)f,gj(j=1,2,…,m):Rn→R是二階連續(xù)可微的凸函數(shù)。(2)int X={x∈Rn|gj(x)＜0,j=1,2,…,m}是非空的。(3)問題(P)的最優(yōu)解集X*是非空的緊集。(4)存在x∈ int X。

用f*記問題(P)的最優(yōu)目標(biāo)函數(shù)值,記問題(P1)的最優(yōu)目標(biāo)函數(shù)值,下面給出求解問題(P)的內(nèi)點(diǎn)正則Newton法。

內(nèi)點(diǎn)正則Newton法:步1,取μ1＞0,0＜β＜1,x0∈int X,ε1＞0。

步2,對(duì)i=1,2,…,定義如下問題:

步3,對(duì)k=1,2,…,定義

步4,內(nèi)循環(huán):求解問題(P1)。①置xi,0=xi-1,若≤εi,則置εi+1=,xi=xi,0,轉(zhuǎn)步5,退出內(nèi)循環(huán);否則,轉(zhuǎn)②,繼續(xù)進(jìn)行內(nèi)循環(huán)。②計(jì)算New ton方向s(xi,k)=-[▽2fi(xi,k)+I]-1▽fi(xi,k)。③用Armijo準(zhǔn)則確定步長(zhǎng)αi,k使得:fi(xi,k+αi,ks(xi,k))≤fi(xi,k)+ραi,k▽fi(xi,k)Ts(xi,k)且xi,k+αi,ks(xi,k)∈int X,其中0＜ρ＜1,αi,k＞0。記xi,k+1=xi,k+αi,ks(xi,k)。④若＞εi,令k∶=k+1,xi,k=xi,k+1,轉(zhuǎn)②,繼續(xù)對(duì)k進(jìn)行內(nèi)循環(huán);否則,置εi+1=,xi= xi,k+1,轉(zhuǎn)步 5,退出內(nèi)循環(huán)。

步5,令μi+1=βμi,置i=i+1,μi∶=μi+1。轉(zhuǎn)步2。

2 收斂性分析

為了證明內(nèi)點(diǎn)正則Newton法的收斂性,還需作如下假設(shè)(B):

(1)對(duì)任意x,y∈X,f(x)、gj(x)(j=1,2,…,m)滿足≤L≤L, j=1,2,…,m。

(2)對(duì)任意x∈X,以及y∈Rn,存在0≤n(x)＜N(x)＜+∞,使得:

(3)對(duì)每個(gè)緊集S?X,存在0＜C2S＜C1S＜+∞滿足:

引理1 設(shè)問題(P)滿足條件(A)和條件(B),對(duì)任意x0∈int X,記Ω={x∈Rn:fi(x)≤fi(x0), gj(x)＜0(j=1,2,…,m)},則存在M0＞0,L0＞0,使得:

證明 由Ω是緊集及問題(P)滿足條件(A)和條件(B)可證。

引理2 設(shè)問題(P)滿足條件(A)和條件(B),對(duì)任意x0∈int X,記Ω={x∈Rn:fi(x)≤fi(x0), gj(x)＜0(j=1,2,…,m)},則:

(1)對(duì)任意x∈Ω,y∈Rn,有n(x)〈y,y〉≤〈▽2fi(x)y,y〉。

證明 由Ω是緊集及問題(P)滿足條件(A)和條件(B)可證。

定理1 設(shè)問題(P)滿足條件(A)和條件(B),則內(nèi)點(diǎn)正則Newton法的內(nèi)循環(huán)在有限步后終止。

因?yàn)閷?duì)任意x,y∈X,有fi(x+y)=fi(x)+∫10〈▽fi(x+τy),y〉dτ,所以可得:

由s(xi,k)=-[▽2fi(xi,k)+▽fi(xi,k)I]-1▽fi(xi,k),得[▽2fi(xi,k)+▽fi(xi,k)I]s(xi,k)=-▽fi(xi,k),從而有〈[▽2fi(xi,k)+▽fi(xi,k)I]s(xi,k),s(xi,k)〉=-〈▽fi(xi,k),s(xi,k)〉,所以:

由引理2的結(jié)論1知:

取αi,k=θ(n(xi,k)+▽fi(xi,k))L,其中0＜θ≤1,且使αi,k滿足Armijo準(zhǔn)則,所以有:

因?yàn)閇▽2fi(xi,k)+▽fi(xi,k)I]s(xi,k)=-▽fi(xi,k),所以:

從而可得:

定理2 設(shè)問題(P)滿足條件(A)和條件(B),則內(nèi)點(diǎn)正則Newton法產(chǎn)生的點(diǎn)列{xi}至少有一個(gè)聚點(diǎn),且{xi}的每個(gè)聚點(diǎn)都是問題(P)的最優(yōu)解。

證明 由定理1知:對(duì)每個(gè)i∈{1,2,…}內(nèi)循環(huán)在有限步后終止,且由內(nèi)點(diǎn)正則New ton法知產(chǎn)生的點(diǎn)列{xi}屬于水平集Ω={x∈Rn:fi(x)≤fi(x0),gj(x)＜0 (j=1,2,…,m)}。由文獻(xiàn)[3]知Ω是緊集,所以點(diǎn)列{xi}有聚點(diǎn),下面證明{xi}的每一個(gè)聚點(diǎn)都是問題(P)的最優(yōu)解。

設(shè)x*是{xi}的聚點(diǎn),不妨設(shè){xij}是{xi}的收斂子列,且jl→im∞xij=x*,x*∈Ω。由內(nèi)點(diǎn)正則New ton法知▽fij(xij≤εij且εij=。設(shè)是問題(P1)當(dāng)i=ij時(shí)的最優(yōu)解,因?yàn)閒ij(x)是可微的凸函數(shù),所以:

即:

又因?yàn)閮?nèi)點(diǎn)正則Newton法產(chǎn)生的點(diǎn)列{xi}中的每一點(diǎn)xi均屬于緊水平集Ω={x∈Rn:fi(x)≤fi(x0), gl(x)＜0 (l=1,2,…,m)},所以xij-x**是有界的。又因?yàn)?x**,所以-x**有界。從而存在C＞0使得xij-≤C。在式(5)中讓j→+∞,得:

下面證明{xij}收斂到問題(P)的最優(yōu)解。由xij=x*,x*∈Ω及f(x)、gl(x)(l=1,2,…,m)的連續(xù)性得f(xij)=f(x*),(xij)=gl(x*)由式(6)及fij(x)的表達(dá)式知(-gl(xij))

存在且有:

3 結(jié)論

對(duì)具有不等式約束的凸規(guī)劃問題,通過把對(duì)數(shù)障礙函數(shù)法同正則Newton法結(jié)合起來,構(gòu)造了求解具有不等式約束的凸規(guī)劃問題的內(nèi)點(diǎn)正則 Newton法,并證明了該算法具有全局收斂性。

[1] Nocedal J,W right SJ.Numerical Op timization[M].北京:科學(xué)出版社,2006.

[2]Nesterov Y,Polyak B T.Cubic Regularization of Newton Method and Its Global Performance[J].Mathematical Programming,2006,108(1):177-205.

[3] Kantorovich L V.Functional Analysis and Applied Mathematics[J].Uspekhi Mat Nauk,1948,3(6):89-185.

[4] Guler O.New Proximal Point Algorithms for Convex Minimization[J].SIAM Journalon Optimization,1992,2:649-664.

[5] Bernard F,Thibault L.Prox-regularity of Functions and Sets in Banach Spaces[J].Set-Valued Anal,2004,12(1):25-47.

[6] Bernard F,Thibault L.Prox-regular Functions in H ilbert Spaces[J].Journal of Mathematical Analysis and Application, 2005,303(1):1-14.

[7] Polyak R A.Regularized Newton Method for Unconstrained Convex Optimization[J].Math Program:Ser B,2009,120(1): 125-145.

[8] 袁亞湘,孫文瑜.最優(yōu)化理論與方法[M].北京:科學(xué)出版社,1999.