约束优化问题的内点正则牛顿法

刘三明

(上海电机学院数理教学部,上海 200240)

0 前言

对于二次可微的强凸函数,Newton方向是下降方向,当初始点充分靠近极小点时,Newton法是收敛的。但当初始点远离极小点时,其收敛性不能保证。为此,在牛顿法中引入步长因子,得到保证全局收敛的阻尼Newton法。当函数不是强凸函数时,Newton方向不一定是下降方向。为了保证Newton法的全局收敛性,对Hessian矩阵采用Levenberg-Marquardt正则化方法[1]。文献[2]对Newton法提出了三次正则化方法。在每次迭代时,只需求解 1个与牛顿法相同的二次函数的无约束最优化问题,但其正则项是三次的。

文献[3]中提出了一种求解无约束凸规划最优解的正则Newton法,该方法不要求函数是强凸的,且具有全局收敛性。在正则 Newton法中,凸函数在一点的正则化基于近似点算法[3-6],而近似参数取为该点梯度的模,即凸函数f(x)在点x处的正则化函数为:

通过上述方法,文献[7]给出了求解任意凸规划minx∈Rnf(x)的具有全局收敛性的Newton法。

本文考虑具有不等式约束的凸规划问题:

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

对凸规划问题(P),把对数障碍函数法同正则Newton法结合起来,提出了求解具有不等式约束的凸规划问题(P)的内点正则Newton法。可以证明该算法具有全局收敛性。

1 内点正则New ton法的建立

对问题(P),作如下假设(A):

(1)f,gj(j=1,2,…,m):Rn→R是二阶连续可微的凸函数。(2)int X={x∈Rn|gj(x)＜0,j=1,2,…,m}是非空的。(3)问题(P)的最优解集X*是非空的紧集。(4)存在x∈ int X。

用f*记问题(P)的最优目标函数值,记问题(P1)的最优目标函数值,下面给出求解问题(P)的内点正则Newton法。

内点正则Newton法:步1,取μ1＞0,0＜β＜1,x0∈int X,ε1＞0。

步2,对i=1,2,…,定义如下问题:

步3,对k=1,2,…,定义

步4,内循环:求解问题(P1)。①置xi,0=xi-1,若≤εi,则置εi+1=,xi=xi,0,转步5,退出内循环;否则,转②,继续进行内循环。②计算New ton方向s(xi,k)=-[▽2fi(xi,k)+I]-1▽fi(xi,k)。③用Armijo准则确定步长α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,转②,继续对k进行内循环;否则,置εi+1=,xi= xi,k+1,转步 5,退出内循环。

步5,令μi+1=βμi,置i=i+1,μi∶=μi+1。转步2。

2 收敛性分析

为了证明内点正则Newton法的收敛性,还需作如下假设(B):

(1)对任意x,y∈X,f(x)、gj(x)(j=1,2,…,m)满足≤L≤L, j=1,2,…,m。

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

(3)对每个紧集S⊂X,存在0＜C2S＜C1S＜+∞满足:

引理1 设问题(P)满足条件(A)和条件(B),对任意x0∈int X,记Ω={x∈Rn:fi(x)≤fi(x0), gj(x)＜0(j=1,2,…,m)},则存在M0＞0,L0＞0,使得:

证明 由Ω是紧集及问题(P)满足条件(A)和条件(B)可证。

引理2 设问题(P)满足条件(A)和条件(B),对任意x0∈int X,记Ω={x∈Rn:fi(x)≤fi(x0), gj(x)＜0(j=1,2,…,m)},则:

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

证明 由Ω是紧集及问题(P)满足条件(A)和条件(B)可证。

定理1 设问题(P)满足条件(A)和条件(B),则内点正则Newton法的内循环在有限步后终止。

因为对任意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的结论1知:

取αi,k=θ(n(xi,k)+▽fi(xi,k))L,其中0＜θ≤1,且使αi,k满足Armijo准则,所以有:

因为[▽2fi(xi,k)+▽fi(xi,k)I]s(xi,k)=-▽fi(xi,k),所以:

从而可得:

定理2 设问题(P)满足条件(A)和条件(B),则内点正则Newton法产生的点列{xi}至少有一个聚点,且{xi}的每个聚点都是问题(P)的最优解。

证明 由定理1知:对每个i∈{1,2,…}内循环在有限步后终止,且由内点正则New ton法知产生的点列{xi}属于水平集Ω={x∈Rn:fi(x)≤fi(x0),gj(x)＜0 (j=1,2,…,m)}。由文献[3]知Ω是紧集,所以点列{xi}有聚点,下面证明{xi}的每一个聚点都是问题(P)的最优解。

设x*是{xi}的聚点,不妨设{xij}是{xi}的收敛子列,且jl→im∞xij=x*,x*∈Ω。由内点正则New ton法知▽fij(xij≤εij且εij=。设是问题(P1)当i=ij时的最优解,因为fij(x)是可微的凸函数,所以:

即:

又因为内点正则Newton法产生的点列{xi}中的每一点xi均属于紧水平集Ω={x∈Rn:fi(x)≤fi(x0), gl(x)＜0 (l=1,2,…,m)},所以xij-x**是有界的。又因为=x**,所以-x**有界。从而存在C＞0使得xij-≤C。在式(5)中让j→+∞,得:

下面证明{xij}收敛到问题(P)的最优解。由xij=x*,x*∈Ω及f(x)、gl(x)(l=1,2,…,m)的连续性得f(xij)=f(x*),(xij)=gl(x*)由式(6)及fij(x)的表达式知(-gl(xij))

存在且有:

3 结论

对具有不等式约束的凸规划问题,通过把对数障碍函数法同正则Newton法结合起来,构造了求解具有不等式约束的凸规划问题的内点正则 Newton法,并证明了该算法具有全局收敛性。

[1] Nocedal J,W right SJ.Numerical Op timization[M].北京:科学出版社,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] 袁亚湘,孙文瑜.最优化理论与方法[M].北京:科学出版社,1999.