无约束优化的非单调三次正则BB算法

楚王莉,刘红卫,刘泽显

(1.西安电子科技大学 数学与统计学院,西安 710126；2.中国科学院 数学与系统科学研究院,北京 100190)

0 引 言

目前,求解无约束优化问题的方法主要分为两类: 线搜索法和信赖域法.线搜索法主要有牛顿法、拟牛顿法、梯度法、共轭梯度法,其中梯度算法以其计算简单、易于存储的特点更适应现代大数据计算的要求.

考虑一般无约束优化问题：

(1)

其中:f:n→是目标函数;x是决策变量.最简单的梯度算法是最速下降法[1],其步长也被称为Cauchy步长或者最优步长、精确步长,算法在迭代点接近极小点时,易产生锯齿现象.Barzilai-Borwein算法(简称BB算法)[2]以其良好的数值性能得到广泛关注,目前已成为求解大规模优化问题的重要方法之一.BB算法中的两个BB步长分别为

其中:sk-1=xk-xk-1;yk-1=gk-gk-1.本文中fk=f(xk),gk=g(xk),g(xk)=f(xk),‖·‖表示Euclid范数.对于严格凸二次函数,BB算法具有全局收敛性和R-线性收敛性[3-4],其计算效果远超过最速下降法.但对于一般的目标函数,BB步长可能为负,不能保证目标值单调下降.Raydan[5]通过结合Grippo等[6]提出的非单调线搜索,设计了一种高效的用于求解无约束优化问题的全局BB算法.对于大多数问题,非单调BB算法的表现均较好.之后,许多学者从不同的角度推导出了不同类型的修正BB步长[7-8],数值实验表明,修正的BB类型步长数值效果较好,但对于最优的BB步长目前尚未达成共识.Liu等[9]从近似模型的角度解释了BB步长,引入了一类新的步长----近似最优步长,提出了一种高效的求解大规模无约束优化问题的近似最优梯度法.文献[10-11]在文献[9]的基础上给出了几种高效的求解一般无约束优化问题的近似最优梯度算法.

三次正则化算法是通过对目标函数取三次过高估计,在目标函数的二次估计上加上一个三次正则项,构成三次模型,作为一种正则化技术计算下一步迭代的步长,因此,三次正则模型比二次模型包含了更多的函数信息.近年来,三次正则化算法作为一种新的求解无约束优化问题的方法已被广泛关注：Cartis等提出了一个自适应的三次正则算法(ARC)[12],并指出在较差条件下,ARC算法享有O(ε-3/2)的迭代复杂度[13].实际上,三次正则算法需要在子空间上进行多次迭代求解试探步,使子问题的求解变得更复杂,而且需要大量的计算和存储空间,因此,构造出更接近目标函数的近似模型和高效求解三次正则化算法的子问题是三次正则化算法的核心.文献[14]给出了一种计算立方模型近似最小值的方法；文献[15]使用BB类型参数构造了一个非单调简单模型的信赖域算法;基于非单调信赖域方法[16],文献[17]给出了一种非单调三次过高估计算法；文献[18]给出了一种将三次正则化方法与线搜索和非单调技术相结合的新算法.

本文首先利用修正的BB类型参数γk构造对角阵来近似目标函数的Hessian矩阵；然后利用近似最优步长构造当前迭代点处的三次正则化近似模型,通过极小化三次近似模型求解试探步,以降低试探步的计算成本,并给出三次正则BB算法；最后基于BB类型算法的非单调性质,为了在试探步长被拒绝时充分发挥BB类型步长的优势,引入非单调策略,得到非单调三次正则BB算法.此外,还对本文算法的接受条件做了一些修正.在合理的假设条件下,给出本文算法的收敛性分析.数值实验表明了本文算法具有良好的数值性能.

1 算法设计

考虑无约束优化问题(1),在当前迭代点,自适应三次正则化模型为

(2)

其中:Bk为目标函数f(x)的Hessian矩阵在xk处的近似;σk为正则化参数.问题(2)的解sk称为当前迭代点处的试探步.设计算目标函数从xk到xk+sk的实际下降量与模型预测下降量之间的比率为ρk,若ρk>v,v∈(0,1),则试探步sk被接受,否则增加正则化参数σk,重新计算试探步.

其中

(3)

对子问题用求导的方式求极值,可得

gk+γks*+σk‖s*‖s*=0,

(4)

其中s*是式(3)的极小值,式(4)也可以写为

gk+γks*+λ*s*=0,

(5)

其中λ*=σk‖s*‖,则由式(5)可得

s*=-[(γk+λ*)I]-1gk,

从而

(6)

由λ*≥0,对式(6)求解,易得

综合上述计算,可解得式(3)的极小值为

sk=s*=-αkgk.

(7)

从而在试探步的计算过程中只需考虑一阶信息,不需要Hessian矩阵存储,使算法计算更简便、存储量小、效率高.

此时,情形1)中的BFGS更新不能保证Bk的正定性.为了得到当前点处的试探步sk,需要构造新的三次近似模型以简化三次正则算法子问题的求解.考虑三次正则子问题：

试探步sk可表示为sk=αkdk,其中:αk为步长;dk为搜索方向,本文取dk=-gk.则试探步可近似实现Cauchy点的迭代效果.试探步可由下列计算得出：

(8)

对于足够小的τk>0,有

则式(8)可表示为

(9)

由于τk>0,σk>0,式(9)的分母是正数,αk是近似最优步长,因此当前迭代点处试探步可表示为

(10)

(11)

因此由式(11)易得

从而可得一个新的三次近似最优模型：

(12)

参照式(8)的求解方式,可得新的试探步为

(13)

综合上述两种情形可得当前迭代点处的近似试探步,极大降低了三次正则算法子问题求解的计算难度.

考虑到三次正则算法试探步接受条件的计算,本文对比率ρk做一些改进,用Zhang-Hager线搜索方法[20]中的Ck代替当前点处的函数值,由上述计算过程可知sk是三次正则子问题的解,则目标函数值的实际下降量为

Ared(sk)=Ck-f(xk+sk),

由构造的三次近似模型对目标函数的预测下降量为

Pred(sk)=mk(0)-mk(sk),

则

(14)

其中Ck的取值参考Zhang-Hager线搜索[20]：

(15)

式中

参数ηk-1∈[ηmin,ηmax],ηmin∈[0,1),ηmax∈[ηmin,1].

如果Ared(sk)和Pred(sk)的比值ρk在一定范围内,则可保持正则参数不变或者减少,此时可接受试探步sk,则有xk+1=xk+sk,否则,增加正则化参数σk,并在当前迭代点xk处重新求解子问题.

下面给出三次正则BB(简称ARC-BB)算法.

算法1ARC-BB算法.

初始点选取: 令x0为初始点,x0∈n,δ∈(0,1),常量ε>0,δ,ηmin,η1,ηmax,σ0,1≤γ1≤γ2,1≥v2≥v1>0,令Q0=1,C0=f0,k=0.

步骤1) 如果‖gk‖∞≤ε,则停止计算.

步骤3) 用式(14)计算比率ρk,如果ρk

步骤4) 令xk+1=xk+sk,更新正则参数：

(16)

步骤5) 选择合适的ηk∈[ηmin,ηmax],按下式更新Qk+1和Ck+1：

(17)

令k=k+1,返回步骤1).

考虑到BB类型算法的非单调性,本文将一些非单调策略应用到三次正则BB算法的框架中.在本文算法中,当试探步产生的函数值实际下降量不能与预测值下降量有一定的匹配度时,试探步被拒绝.考虑到当迭代远离最优点时,使用非单调策略能获得更佳的收敛结果,因此采用非单调线搜索策略以避免子问题的重复求解.

下面结合非单调线搜索策略,给出非单调三次正则BB(简称NMARC-BB)算法.

算法2NMARC-BB算法.

初始点选取: 令x0为初始点,x0∈n,δ∈(0,1),常量ε>0,δ,ηmin,η1,ηmax,σ0,1≤γ1≤γ2,1≥u2≥u1>0,令Q0=1,C0=f0,k=0.

步骤1) 如果‖gk‖∞≤ε,则停止计算.

步骤3) 用式(14)计算比率ρk,如果ρkv,则令xk+1=xk+sk,按式(16)更新正则参数, 转步骤5).

步骤4) 用文献[15]更新

步骤5) 选择合适的ηk∈[ηmin,ηmax],按式(17)更新Qk+1和Ck+1;令k=k+1,返回步骤1).

2 收敛性分析

下面给出ARC-BB和NMARC-BB算法的收敛性证明,主要由三次近似模型求得试探步sk的性质分析.

假设1 对模型mk(sk),对任意的k≥0,κB≥0,‖Bk‖≤κB均成立.

假设2f(x)在n上是连续可微的.

假设3 梯度g(x)在n上是Lipschitz连续的,即存在L>0,使得

‖g(x)-g(y)‖≤L‖x-y‖, ∀x,y∈n.

由dk=-gk,易知搜索方向是下降方向.本文中试探步sk是通过极小化三次近似模型mk(sk)得到的,而mk(sk)实质上是一个梯度模型,因此试探步sk可表示为sk=-αkgk,其中αk可视为沿负梯度方向的步长.

引理1假设试探步sk是由ARC-BB和NMARC-BB算法计算得出的,则对任意的k≥0,有

证明：证明过程类似于文献[12]中引理2.1,故略.

引理2假设试探步sk是由ARC-BB和NMARC-BB算法计算得出的,对任意的k≥0,有κB≥0,使得‖Bk‖≤κB成立,则

证明：证明过程类似于文献[12]中引理2.2,故略.

引理3若序列{xk}是由ARC-BB和NMARC-BB算法计算得出的,则对任意的k≥0,有fk+1≤Ck+1≤Ck.

证明：证明过程类似于文献[21]中引理3.1和文献[20]中定理2.2,故略.

引理4NMARC-BB算法的步骤4)是合理的,即步骤4)不会无限循环.

证明：对于步骤4),当ρk

利用Taylor展式和引理3,可得

对于ξk∈(0,1),有

若αk→0,则有

(18)

定理1假设f有下界,序列{xk}是由ARC-BB和NMARC-BB算法计算得出的,则有

(19)

证明：当ρk

当ρk≥v时,用反证法.假设存在一个常数τ>0,使得对任意的k,有

‖gk‖≥τ,

(20)

则有

结合Ck的定义,可得

再结合假设式(20)可知

(21)

由引理3可知,对任意的k≥0,有fk+1≤Ck,且序列{Ck}是单调不增的,再结合假设f(x)在n上是连续可微的,则序列{Ck}是收敛的,因此

(22)

又由ηk∈[ηmin,ηmax]⊂[0,1]及Ck,Qk的定义可知

再结合式(21),(22)可得

(23)

因此,对任意的k∈Γ,第k次迭代都有

这与已知ρk≥v矛盾,从而式(19)成立.证毕.

3 数值实验

下面先对所提出的两种算法ARC-BB和NMARC-BB的数值性能进行比较,然后给出NMARC-BB算法与BB算法和GM-AOS(cone)[10]算法的数值实验比较,其中BB算法是公认的解决无约束优化问题非常有效的方法,GM-AOS(cone)算法是目前数值效果非常好的近似最优梯度算法.本文使用与GM-AOS(cone)算法相同的测试函数集,即Andrei测试函数集中的80个测试函数(http://camo.ici.ro/neculai/AHYBRIDM).

本文所有算法程序均由C语言实现,每个测试问题的维数都为104,算法中用到的参数为：ε=10-6,v=0.01,v1=0.3,v2=0.7,γ1=1.5,γ2=2,ξ1=1.07,ξ2=0.85,σ0=50,δ=0.55,ηk=1,ηmax=ηmin=1,∂=5.当满足‖gk‖∞≤10-6时,算法停止迭代,迭代次数超过5×104或者函数的计算次数超过8×104时,算法也停止迭代.

本文利用Dolan等[22]提出的数值性能比较方法给出不同算法数值性能的比较结果.下面以迭代次数为例说明文献[22]方法的性能图.用函数P(τ)表示测试算法s在最少迭代次数集I*的τ倍内所能解的问题个数占总问题个数的比率,它反映了测试算法迭代次数的数值性能.对每种测试算法,给出P(τ)的曲线图,最高的曲线表示该测试算法在最少迭代次数集的τ倍内能求解的问题最多,因此该测试算法在迭代次数方面的数值性能更好.

数值实验分两组,第一组先对ARC-BB和NMARC-BB算法进行比较,其中ARC-BB算法可以成功求解79个问题,NMARC-BB算法可以成功求解测试函数集中的全部80个问题.消除ARC-BB算法不可解的问题后,剩下79个问题,因此下面分析只考虑余下的79个问题.图1～图4分别为两种算法的迭代次数、函数值计算次数、梯度计算次数以及CPU时间的性能评估结果.由图1～图4可见,NMARC-BB算法的数值效果好于ARC-BB算法.因此,在下面的数值实验过程中,使用数值效果较好的NMARC-BB算法与其他算法比较.

图1 两种算法迭代次数的性能评估Fig.1 Performance evaluation of iteration numbers for two algorithms

图2 两种算法函数值计算次数的性能评估Fig.2 Performance evaluation of calculation numbers of function values for two algorithms

图3 两种算法梯度计算次数的性能评估Fig.3 Performance evaluation of calculation numbers of gradient for two algorithms

图4 两种算法的CPU性能评估Fig.4 Performance evaluation of CPU for two algorithms

图5 3种算法迭代次数的性能评估Fig.5 Performance evaluation of iteration numbers for three algorithms

图6 3种算法梯度计算次数的性能评估Fig.6 Performance evaluation of calculation numbers of gradient for three algorithms

第二组实验对NMARC-BB、BB和GM-AOS(cone)3种算法的数值结果进行比较.结果表明,NMARC-BB算法可以成功解决80个测试函数集中的全部问题,GM-AOS(cone)算法可以成功求解79个问题,BB算法只能成功求解其中的74个问题.消除3种算法中不可解的问题后,剩下74个问题,因此下面分析中只考虑剩下的74个问题.图5和图6分别为NMARC-BB、BB和GM-AOS(cone)3种算法的迭代次数和梯度计算次数的比较结果.由图5和图6可见,NMARC-BB算法比BB和GM-AOS(cone)算法的数值性能更好,其中NMARC-BB算法迭代次数和梯度计算次数最小的问题占总问题的55%,BB算法和GM-AOS(cone)算法迭代次数和梯度计算次数最小的问题分别占总问题的44%和19%.

图7为3种算法的函数计算次数性能评估结果.由图7可见,NMARC-BB比BB算法具有更大的优势,并且相对GM-AOS(cone)算法表现突出.NMARC-BB算法函数值计算次数最小的问题占总问题的62%,GM-AOS(cone)和BB算法函数值计算次数最小的问题分别占总问题的42%和21%.图8为3种算法CPU运行时间的比较.由图8可见,在解决本文所给的测试函数集函数时,NMARC-BB算法比BB和GM-AOS(cone)算法所用的时间更少.

图7 3种算法函数值计算次数的性能评估Fig.7 Performance evaluation of calculation numbers of function values for three algorithms

图8 3种算法CPU性能评估Fig.8 Performance evaluation of CPU for three algorithms

由上述实验结果可见,NMARC-BB算法具有良好的数值性能,通过将三次正则技术与BB算法相结合给出的新的求解大规模无约束优化问题的NMARC-BB算法,比原有的BB类型算法更灵活、高效.

综上所述,本文提出了两种新的求解大规模无约束优化问题的ARC-BB和NMARC-BB算法.基于BB算法的高效性和简洁性,利用一个BB类型参数近似目标函数的Hessian矩阵,通过构造当前迭代点处的三次近似梯度模型,用极小化三次近似模型的方法求解当前点处的试探步.在试探步被拒绝的情形下,利用非单调线搜索策略设计求解新的试探步.数值实验结果表明,NMARC-BB算法不仅具有高效性和简便性,同时还有比传统的BB类型算法包含更多的函数值信息,更精确.