一种基于L-函数的非单调自适应信赖域算法

张 杰，朱子旋，芮绍平，曾 柔

（淮北师范大学数学科学学院，安徽淮北 235000）

考虑无约束最优化问题[1]

其中：f:Rn→R为连续可微函数。信赖域方法是求解无约束优化问题的一类重要的数值方法，由Powell[2]提出，该方法具有良好的适应性与稳定性。对于无约束优化问题，传统的信赖域方法利用二次函数逼近函数f，得到信赖域算法的子问题[3]：

其中：gk=∇f(xk)；Bk为Hesse 矩阵∇2f(xk)的第k次近似；Δk为信赖域半径；‖ ⋅ ‖是Euclidean范数。

引入Aredk=f(xk)-f(xk+dk)和Predk=φk(0)-φk(dk)分别代表目标函数的实际下降量和预测下降量[4]。

另外，近年来非单调技术得到广泛应用[9-10]，其中Ahookhosh[11]提出的非单调方法中，步长αk满足条件：

这里δ∈(0,1),γk∈[γmin,γmax],γmax∈[γmin,1)γmin∈(0,1)。

非单调项fl(k)定义为：

其中：m(0)=0,m(k)=max{m(k-1)+1,2M}，对于k≥1，M为给定的非负整数[12]。在此技术中，当前非单调项是前一非单调项和当前目标函数的凸组合。

利用L-函数，设计信赖域半径迭代依赖比值rk的连续变化而变化的自适应算法。同时采用非单调wolfe 线搜索技术，得到迭代步长。算法的全局收敛性得到证明，数值实验表明算法稳定可靠。

1 算法

借助L-函数，给出更新信赖域半径策略，设计新算法。L-函数定义如下：

定义1[8]函数L(t)称为L-函数，如果它满足下列条件：

(1)L(t)在(-∞,η1)中非减，在(2 -η1,+∞)中非增，当t∈[η1,2 -η1]，L(t)=β1，

这里的常数满足:0 2 -η1。由文献[8]可知L-函数有界。

采用的信赖域半径更新规则为Δk+1=L(rk)Δk，其中L(rk)是一个关于比值rk的L-函数，结合非单调技术将比率rk更改为：

基于此更新策略，设计算法1。

算法1 非单调自适应线搜索信赖域算法(NTTR)

步0 给定x0∈Rn,B0∈Rn×n和Δ0>0，γ∈(0,1)，0 0，M≥1，令k=0；

步1 计算gk=∇f(xk),如果‖gk‖≤ε，则算法终止；否则转步2；

步2 求解信赖域子问题 (2) 的近似解dk，‖ dk‖≤ Δk；

步4 若rk≥μ，令xk+1=xk+dk,否则求步长αk，满足非单调wolfe线搜索：

令xk+1=xk+αkdk；

根据林雪川的说法，黎永兰倒下之后，左边耳朵就流血出来了，嘴里也吐白沫，他自己也吓倒了。林雪川将倒地的黎永兰通过出租车送到了广安市人民医院。

步5 更新信赖域半径：Δk+1=L(rk)Δk；

步6 更新Bk，令k=k+1，转步1。

2 收敛性分析

为了证明算法的收敛性，以下假设条件成立：

A1：水平集

L(x0)={x∈Rn|f(x) ≤f(x0)}。

有界且f(x)在水平集上连续可微有下界；

A2：g(x)=∇f(x)在水平集上是Lipschitz连续，即存在常数L>0，使∀x,y∈Rn,‖ ∇f(x) -∇f(y) ‖≤L‖x-y‖；

A3:序列{Bk} 一致有界，即∃M1>0 使得∀k∈N，有‖Bk‖

引理1[13]子问题(2)的解中dk满足φk(0) -其中σ∈(0,1]。

引理2[14]算法1产生的点列{xk} 满足：

引理3[11]算法1 产生的点列{xk} 满足：fk+1≤Dk+1≤fl(k+1)。

证明 由假设条件A1 可知，点列{f(xk)}有下界。假设定理1 不成立，即存在一个常数ε>0，使得下证

由算法1，产生的迭代点列满足：

又由m(k+1) ≤m(k)+1 及{fl(k)} 定义知：fl(k+1)≤fl(k)，即{fl(k)} 单调递减，再由假设条件A2 和A3 知有其有下界，所以{fl(k)} 收敛。因此对(6)式两边取极限可得

又据引理2，引理3有：

3 数值实验

给出基于L-函数的非单调自适应信赖域算法（NTTR）的数值结果，并且和传统的信赖域算法(TTR) 进行比较。算法运行环境是MATLAB(R2022a)。参数选取如下：

Δ0=‖g(x0) ‖,B0=I。

计算结果见表1 和表2，其中dim 代表测试的维数，num 代表算法迭代次数，val 代表最优值。算例1和算例2来自文献[15]。

表1 算例1 数值实验结果

表2 算例2 数值实验结果

算例1 测试函数为：

算例2 测试函数为：

初始点x0=(3,-1,0,3,...3,-1,0,3)T。

从表1 可以看出，对于不同的初始点选择，由于非单调技术的引入，降低了算法的计算量，迭代次数小于传统的信赖域算法。从表2可以看出，随着测试问题从低维到高维，新的非单调自适应信赖域算法能快速有效地得到最优解，并且具有良好的稳定性，说明算法NTTR适合求解较大规模问题。

4 结语

信赖域方法是求解无约束优化问题的经典方法之一，对该方法改进具有重要的实际意义和应用价值。基于L-函数的非单调自适应信赖域算法很好地解决传统信赖域方法中信赖域半径更新问题，实现了自动更新迭代，非单调技术的使用也大大减少了算法的计算量，调高了算法效率，因此这种方法丰富和推广了现有结果。