一类具有充分下降性的修正FR共轭梯度法

张 鹏

考虑无约束优化问题

其中f:Rn→R是连续可微的函数.共轭梯度法因为迭代简单存储量小,因此常被用来求解具有问题(1)形式的大规模优化问题.共轭梯度法的一般迭代格式为

其中αk是由线搜索确定的步长,搜索方向dk满足

βk是共轭参数,βk的不同取法对应于不同的非线性共轭梯度法.著名的共轭梯度法有1964年Fletcher和Reeves提出的FR方法[1],1969年Polar-Ribiere和Polyak分别独立提出的PRP方法[2,3],1952年Hestenes和Stiefel提出的HS方法[4],1999年Dai和Yuan提出的DY方法[5],βk分别由下式给出

其中,‖·‖为欧几里得范数,yk-1=gk-gk-1.

在共轭梯度法的许多理论分析和数值实现中,常常采用非精确线搜索如强Wolfe线搜索.强Wolfe线搜索要求步长αk满足

其中0＜δ≤σ＜1.

Al-Baali[6]证明了当强Wolfe线搜索参数σ被限制在时FR方法是全局收敛的.Liu等[7]将Al-Baali的结果推广到σ=.Zhang[8]提出一种修正的PRP方法,其中βk被定义为

并证明了NPRP在强_Wolfe线搜索下的充分下降性和全局收敛性.最近,Dai等[9]提出一种修正的NPRP方法 (记为:DPRP方法),βk被定义为

证明了DPRP方法不依赖线搜索而具有充分下降性,且对Armijo线搜索和Wolfe线搜索具有全局收敛性.受Zhang[8]和Dai[9]的启发,这里构造一类如下的修正FR方法,共轭梯度参数βk具有如下形式

其中μ＞1.当目标函数是严格凸二次函数并采用精确线搜索时,MFR退化为经典的FR方法.可以证明新方法不依赖线搜索,具有充分下降性且在强Wolfe线搜索下具有全局收敛性.

1 MFR算法

Step 0 给定常数σ∈(0,1),δ∈(0,σ),ε≥0,选取初始点x0∈Rn,计算d0=-g(x0),置k=0.

Step 1 如果‖gk‖∞≤ε,则算法终止.

Step 2 计算αk＞0满足强Wolfe线搜索 (4)-(5).

Step 3 令xk+1=xk+αkdk,gk+1=g(xk+1).如果‖gk+1‖∞≤ε,则算法终止.

Step 4 由式 (3),(6)计算dk+1,置k=k+1,转Step 2.

2 MFR算法的收敛性

假设

(A)目标函数f(x)在水平集L={x∈Rn∣f(x)≤f(x0)}上有下界,其中x0∈Rn为算法初始点.

(B)目标函数f(x)在水平集L的一个领域N内连续可微,且其梯度函数g满足Lipschitz条件,即存在常数l＞0,使 ‖g(x)-g(y)‖ ≤l‖x-y‖,∀x,y∈L.

引理1 βkMFR满足0≤βkMFR≤βkFR.

证 由βkMFR的表达式(6)知

引理2 考虑具有式(2)和 (3)的迭代方法,其中βk=βkMFR,则对任意的线搜索有

证 由βkMFR的表达式(6),有

因此

由引理1和文献[10]中的定理3.2可以直接得到下面的定理.

定理 若假设(A)(B)成立,MFR算法中步长αk满足强Wolfe条件(4)和(5),参数0＜δ＜σ＜=0.

参考文献:

[1]Fletcher R,Reeves C M.Function minimization by conjugate gradients[J].The Computer Journal,1964,7(2):149-154.

[2]Polak E,Ribiere G.Note sur la convergence de methodes de directions conjuguees[J].ESAIM:Mathematical Modelling and Numerical Analysis-Modélisation Mathematique et Analyse Numerique,1969,3(R1):35-43.

[3]Polyak B T.The conjugate gradient method in extremal problems[J].USSR Computational Mathematics and Mathematical Physics,1969,9(4):94-112.

[4]Hestenes M R,Stiefel E.Methods of conjugate gradients for solving linear systems[M].Washington,DC:National Bureau of Standards,1952:409-436.

[5]Dai Y H,Yuan Y.A nonlinear conjugate gradient method with a strong global convergence property[J].SIAM Journal on Optimization,1999,10(1):177-182.

[6]Al-Baali M.Descent property and global convergence of the Fletcher-Reeves method with inexact line search[J].IMA Journal of Numerical Analysis,1985,5(1):121-124.

[7]Liu G H,Han J Y,Yin H X.Global convergence of the Fletcher-Reeves algorithm with inexact linesearch[J].Applied Mathematics-A Journal of Chinese Universities,1995,10(1):75-82.

[8]Zhang L.An improved Wei-Yao-Liu nonlinear conjugate gradient method for optimization computation[J].Applied Mathematics and Computation,2009,215(6):2269-2274.

[9]Dai Z,Wen F.Another improved Wei-Yao-Liu nonlinear conjugate gradient method with sufficient descent property[J].Applied Mathematics and Computation,2012,218(14):7421-7430.

[10]Gilbert J C,Nocedal J.Global convergence properties of conjugate gradient methods for optimization[J].SIAM Journal on optimization,1992,2(1):21-42.