基于分式模型的非单调自适应信赖域方法

A Nonmonotone Adaptive Trust Region Method Based on Fractional Model

摘要: 本文针对无约束优化问题提出了一个基于分式模型的非单调自适应信赖域的算法。首先用折线法求解子问题，之后算法结合非单调线搜索技术得到步长，产生下一个迭代点，提高算法的收敛速度；并引入自适应半径，避免传统信赖域半径更新的局限性。在一定的假设条件下，证明了该算法具有全局收敛性，数值实验证明了非单调自适应分式模型信赖域算法是有效的并且优于原来求解分式模型的算法，并且比二次模型和锥模型更为有效和稳健。

Abstract: This paper proposes a nonmonotone adaptive trust region algorithm based on fractional model for unconstrained optimization problems. First, the dogleg step method is used to solve the sub- problem, and then the algorithm combines nonmonotonic line search technology to obtain the step size, generates the next iteration point, and improves the convergence speed of the algorithm; The adaptive radius is introduced to avoid the limitations of traditional trust region radius updating. Under certain assumptions, it is proved that the algorithm has global convergence. Numerical experiments show that the nonmonotonic adaptive fractional model trust region algorithm is effective and superior to the original algorithm for solving fractional models, and is more effective and robust than the quadratic model and the cone model.

1. 引言

目前，最优化理论与方法在自然科学、经济管理、工程设计、环境保护、地震勘探、国家安全等领域上被广泛地应用，现已成为运筹学的一个重要分支。在许多亟待解决的、对社会有重大影响的大规模复杂科学和工程问题一般都是非线性的，如大气科学中的同化问题、信息科学中的模式识别问题、地球科学中的反演问题等。因此，研究高效的非线性最优化计算方法不仅具有重要的科学意义，而且具有广泛的应用前景。

很多非线性优化问题的数学模型本身是无约束的，求解相对容易，而无约束问题解法的基本思想又常常可以推广到一般有约束的情形。求解无约束优化问题的主要方法有信赖域法和线搜索法 [1] 。在实际应用中，信赖域方法比线搜索方法在解决Hessian矩阵不正定和x_k为鞍点等问题上更具优势，使得它在优化领域取得了较好的发展 [2] 。

传统的信赖域方法是基于二次函数，如果目标函数非二次性比较强或者其曲率变化剧烈，那么二次模型方法可能会产生一个比较差的函数极小值的估计值。1980年，Davidon [3] 针对二次模型的不足首次提出了锥函数，即二次函数的推广形式。用锥函数逼近原函数，可以插值较多的函数和梯度信息，比二次函数逼近更为一般 [4] 。以锥函数为基础所形成的方法简称锥模型方法。这类方法的提出引起了很多国内外学者对其做深入的研究，其中包括国外的Ariyawansa，Di，Wright和Sorensen教授，我国的李正峰、倪勤、孙文瑜教授等。此外，锥模型中含有参量a_k，虽然可以提供一定的自由度来充分利用迭代点中的梯度和函数值信息，但其水平参向量只有一个，这会影响其搜索方向的选择。对此，2015年朱红兰和倪勤等人首次提出了分式模型 [5] ，即是锥函数的推广形式，拥有三个水平向量，可以提供更多的插值信息。

近年来，信赖域算法常常应用非单调技术去提升算法的效率和性能。1986年，Grippo等 [6] [7] 为了克服单调技术要求在每次迭代中都减少目标函数值的缺点，提出了一种具有直线搜索技术的非单调信赖域方法。基于Grippo等人提出的非单调技术上，2004年，Zhang和Hager [8] 发现非单调技术有一些缺点。例如，数值性能严重依赖于参数M的选择；在任何迭代中生成的良好函数值可能都没有用处等。为了克服这些缺点，Zhang和Hager提出了另一种非单调技术。受前人的启发，2012年，Ahookhosh等人 [9] 提出了更为简化的非单调参数。

传统信赖域方法通过使用r_k来修改信赖域在迭代点处的半径，效率不高且参数难取。2002年，Zhang等人 [10] 在中提出了自适应半径。2008年，Shi和Guo [11] 提出了另一种自适应半径，解决了Zhang等人提出的自适应半径不适合大规模问题的缺点。2018年，盛洲等人 [12] 提出了一种较为简便的自适应信赖域方法求解无约束优化问题的，该方法由一般信赖域方法和修正正割方程驱动。2019年，Xue等人 [13] 提出了一种新的改进的非单调自适应信赖域方法，用于解决无约束优化问题。2022年，Kamandi [14] 等人在此前的基础上提出了一种有效的非单调自适应信任域方法。

2011年，冯琳和段复建 [15] 基于锥模型提出非单调自适应信赖域算法。2015年，王开荣和曾刘拴 [16] 采用滤子技术改进了锥模型的非单调自适应信赖域方法。

从理论分析的角度出发，基于分式模型非单调自适应信赖域算法是具备全局收敛性的，从数值实验分析，该算法是可行的，有效的。但是，由于分式模型的插值较多，导致计算量较大；以及引用非单调自适应技术，导致算法比较复杂，所以关于分式模型的非单调自适应算法的国内外研究并不多。

因此，为了克服单调技术的局限性以及传统信赖域依靠r_k来设定半径的困难，本文基于朱红兰等人 [5] 提出的分式模型，之后结合Ahookhosh等人 [9] 的非单调技术，盛洲等人 [12] 的自适应技术提出一个求解分式模型的非单调自适应信赖域算法。

2. 非单调自适应分式模型信赖域方法

本文考虑无约束优化问题

$\underset{x\in R^n}{\min }f\left(x\right)$ (1)

其中 $f:R^n\to R$ 是二次连续可微函数。

1980年，Davidon [3] 提出的锥函数为

${\tilde{\varphi }}_k\left(s\right)=f_k+\frac{g_k^{\text{T}}s}{1-a_k^{\text{T}}s}+\frac{s^{\text{T}}{B}_{k}s}{2{\left(1-a_k^{\text{T}}s\right)}^2},$ (2)

其中 $a_k\in R^n$ 是水平参向量。当 $a_k=0$ 时，锥函数退化为二次函数。此外，锥模型中含有参量 $a_k$ ，虽然可以提供一定的自由度来充分利用迭代点中的梯度和函数值信息，但其水平参向量只有一个，这会影响其搜索方向的选择。因此，朱红兰等人首次提出了如下分式模型 [5] ：

${\varphi }_k\left(s\right)=\frac{1+c_k^{\text{T}}s}{\left(1-a_k^{\text{T}}s\right)\left(1-b_k^{\text{T}}s\right)}{g}_k^{\text{T}}s+\frac{{\left(1+c_k^{\text{T}}s\right)}^2}{2{\left(1-a_k^{\text{T}}s\right)}^2{\left(1-b_k^{\text{T}}s\right)}^2}{s}^{\text{T}}{B}_{k}s,$ (3)

以及相应的分式模型信赖域子问题：

$\begin{array}{l}\underset{s\in R^n}{\min }{\varphi }_k\left(s\right)\\ \text{s}\text{.t}.\Vert s\Vert \le \tilde{\Delta },\left|\left(1-a_k^{\text{T}}s\right)\left(1-b_k^{\text{T}}s\right)\right|>\omega .\end{array}$ (4)

其中参数向量 $a_k,b_k,c_k\in R^n$ 是有界的。如果 $b_k=c_k=0$ ， ${\varphi }_k\left(s\right)$ 退化为锥模型。如果 $a_k=b_k=c_k=0$ ，则 ${\varphi }_k\left(s\right)$ 为二次模型。基于这个新的分式模型(4)，文献 [5] 提出了一个简化的分式信赖域子问题：

$\begin{array}{l}\underset{s\in R^n}{\min }{\varphi }_k\left(s\right)\\ \text{s}\text{.t}.\Vert s\Vert \le {\Delta }_k,\end{array}$ (5)

其中 ${\Delta }_k$ 是信赖域半径，且有

${\Delta }_k=\min \left\{{\tilde{\Delta }}_k,\frac{\omega }{\Vert a_k\Vert },\frac{\omega }{\Vert b_k\Vert },\frac{\omega }{\Vert c_k\Vert }\right\},0<\omega <\frac{1}{\text{3}}.$ (6)

参数向量满足

$\Vert a_k\Vert {\Delta }_k<\omega ,\Vert b_k\Vert {\Delta }_k<\omega ,\Vert c_k\Vert {\Delta }_k<\omega .$ (7)

非单调技术由于在信赖域方法中引用可以得到较好的数值结果，得到了很大的发展。Grippo等 [6] [7] 在1986年提出了一种具有直线搜索技术的非单调信赖域方法，其步长α_k满足 ${\alpha }_k\in \left\{s,\rho s,\rho s^2,\cdots \right\}$ ，且有：

$f\left(x_k+{\alpha }_k{s}_k\right)\le f_{l\left(k\right)}+\beta {\alpha }_k{g}_k^{\text{T}}{s}_k$ (8)

其中 $s>0,\rho \in \left(0,1\right),\beta \in \left(0,\frac{1}{2}\right)$ 。一般非单调项f_l(k)定义为：

$f_{l\left(k\right)}=\underset{0\le j\le m\left(k\right)}{\max }\left\{f\left(x_{k-j}\right)\right\}$ (9)

其中

$m\left(0\right)=0,0\le m\left(k\right)\le \min \left\{m\left(k-1\right)+1,N\right\},k\ge 1,$

N为非负整数。

2012年，Ahookhosh等人 [9] 提出了更为简化的非单调参数R_k，满足：

$f\left(x_k+{\alpha }_k{s}_k\right)\le R_k+\beta {\alpha }_k{g}_k^{\text{T}}{s}_k,$ (10)

其中

$R_k={\eta }_k{f}_{l\left(k\right)}+\left(1-{\eta }_k\right)f\left(x_k\right)$ (11)

其中 ${\eta }_k\in \left({\eta }_{\min },{\eta }_{\max }\right);{\eta }_{\min }\in \left[0,1\right);{\eta }_{\max }\in \left[{\eta }_{\min },1\right)$ 是两个前缀常量。

当信赖域半径更新时，通常依赖参数的选取，具有盲目性。2018年，盛洲等人 [12] 提出了一种由修正正割方程驱动的自适应方法，其中修正方程为：

$B_{k+1}{d}_k=q_k,$ (12)

其中

$\begin{array}{l}{q}_k=y_k+h_k{d}_k,\\ y_k=g_{k+1}-g_k,\\ h_k=\frac{{\left(g_{k+1}+g_k\right)}^{\text{T}}{d}_k+2\left(f_k-f_{k+1}\right)}{{\Vert d_k\Vert }^2}.\end{array}$ (13)

新的自适应半径为：

${\Delta }_k:=c^p\frac{\Vert d_{k-1}\Vert }{\Vert q_{k-1}\Vert }\Vert g_k\Vert ,$ (14)

其中 $c\in \left(0,1\right)$ 。

修改后的BFGS更新公式为

$B_{k+1}=B_k-\frac{B_k{d}_k{d}_k^{\text{T}}{B}_k}{d_k^{\text{T}}{B}_k{d}_k}+\frac{q_k{q}_k^{\text{T}}}{q_k^{\text{T}}{d}_k}.$ (15)

3. 基于分式模型的非单调自适应信赖域算法

为了求解问题(5)，我们用如下的分式模型来近似f(x)：

${\phi }_k\left(s\right)=f_k+{\varphi }_k\left(s\right),$ (16)

其中 ${\varphi }_k\left(s\right)$ 由(3)式可得。

该分式模型满足下面五个插值条件 [5] ：

${\varphi }_k\left(0\right)=f_k,\nabla {\varphi }_k\left(0\right)=g_k,$

${\varphi }_k\left(-s_{k-1}\right)=f_{k-1},{\varphi }_k\left(-s_{12}\right)=f_{k-2},{\varphi }_k\left(-s_{13}\right)=f_{k-3},$

其中

$s_{k-1}=x_k-x_{k-1},s_{12}=x_k-x_{k-2},s_{13}=x_k-x_{k-3},$

由上面的插值条件，得到

$a_k=v_1{g}_{k-1},b_k=v_2{B}_{k-1}{s}_{k-1},c_k=v_3{g}_k,$

其中 $v_1,v_2,v_3$ 参考文献 [5] 可得。

接着，给出如下折线法来求解分式模型(16)，求解近似解的详细过程可参考文献 [17] [18] 。

算法1 子问题的求解

步1：计算分式模型(16)的牛顿点 $s_N$ ，最速下降点 $s_{Cp}$ 。

步2：若 $\Vert s_N\Vert \le {\Delta }_k$ ，则 $s_{*}=s_N$ ，算法停止，否则转步3。

步3：令 $s_{*}=s_{Cp}$ 。

有了算法1，结合Ahookhosh等人的非单调技术和盛洲等人的自适应技术，下面给出一个求解分式模型(16)的非单调自适应信赖域算法。

算法2 基于折线法的非单调自适应分式模型信赖域算法

步0. 设

$u\in \left(0,1\right),{\Delta }_{\max }>0,\omega \in \left(0,\frac{1}{\text{3}}\right),\epsilon >0,\eta \in \left(0,1\right),c\in \left(0,1\right),x_0\in R^n,B_0=I,{\Delta }_0\in \left(0,{\Delta }_{\max }\right],\beta \in \left(0,\frac{1}{2}\right),\rho \in \left(0,1\right)$ 。

令k = 0，p = 0。

步1. 计算 $f_k=f\left(x_k\right),g_k=\nabla f\left(x_k\right)$ 。假设满足 $\Vert g_k\Vert \le \epsilon$ 时，则 $x_{k+1}=x_k$ ，算法停止，否则，转步骤2。

步2. 通过算法1计算 $s_k$ 。

步3. 校正信赖域半径。

${\Delta }_k:=c^p\frac{\Vert s_{k-1}\Vert }{\Vert q_{k-1}\Vert }\Vert g_k\Vert .$ (17)

步4. 计算 $R_k$ ，选择合适的参数 ${\eta }_k\in \left[{\eta }_{\min },{\eta }_{\max }\right]$ ，计算

$r_k=\frac{R_k-f\left(x_k+s_k\right)}{{\phi }_k\left(0\right)-\phi \left(s_k\right)}.$ (18)

如果 $r_k\ge u$ ，则 $x_{k+1}=x_k+s_k$ ，转步5；否则，令 $x_{k+1}=x_k+{\alpha }_k{s}_k$ ，计算 ${\alpha }_k$ 使其满足式(10)， $p=p+1$ ，转步3。

步5. 计算 $q_k$ ，如果 $s_k^{\text{T}}{q}_k>0$ ，则用(15)式迭代 $B_{k+1}$ 进行修正，否则令 $B_{k+1}=B_k$ 。令 $k=k+1$ ，转步1。

备注：1) 算法2中“步骤3–步骤4–步骤3”的过程称为内循环。

2) 记集合 $I=\left\{k:r_k\ge u\right\},J=\left\{k:r_k<u\right\}$ 。

3) 定义模型(16)的预测下降量为

$Pred\left(s\right)={\phi }_k\left(0\right)-{\phi }_k(\; s\; )$

4. 收敛性分析

为了证明算法2的收敛性，现给出以下假设：

(H1) 有界闭集 $L\left(x_0\right)=\left\{x\in {ℝ}^n|f\left(x\right)\le f\left(x_0\right)\right\}$ 满足 $L\left(x\right)\subseteq \Omega \subseteq {ℝ}^n$ ，且 $f\left(x\right)$ 二阶连续可微。

(H2) 存在一个正数m使得对所有 $s\in {ℝ}^n,k\in N$ ，有

$s^{\text{T}}{B}_{k}s\ge m{\Vert s\Vert }^2.$ (19)

(H3) 矩阵 $B_k$ 是一致有界的，存在一个正常数M₁使得对所有 $k\in N$ ，有

$\Vert B_k\Vert \le M_1.$ (20)

引理1 [18] 假设(7)成立，如果 $s_k$ 是由算法1生成的子问题(16)的解，则有，

$Pred\left(s_k\right)\ge \frac{1}{2}\frac{\Vert g_k\Vert }{\Vert B_k\Vert }\min \left\{\Vert g_k\Vert ,\frac{\xi {\Delta }_k}{\Vert B_k{}^{-1}\Vert }\right\}.$ (21)

其中 $\xi =\frac{1-\omega }{{\left(1+\omega \right)}^2},\omega \in \left(0,\frac{1}{\text{3}}\right)$ 。

引理2 [12] 如果 $B_{k+1}$ 由BFGS公式(15)更新，则 $B_k$ 正定， $s_k^{\text{T}}{q}_k>0$ 当且仅当 $B_{k+1}$ 正定。

引理3 若 $s_k$ 是由算法1生成的子问题(16)的解， $\Vert g_k\Vert \ne \text{0}$ ，则 $\exists \tilde{k}>0$ ，使得

$g_k^{\text{T}}{s}_k+{\kappa }_k{g}_k^{\text{T}}{s}_k+\frac{1}{2}{s}_k^{\text{T}}{B}_k{s}_k\le -\tilde{k}{\Vert g_k\Vert }^2.$ (22)

其中

$\tilde{k}=\frac{1}{2M_1}\min \left\{1,\xi c^p\right\},\xi =\frac{1-\omega }{{\left(1+\omega \right)}^2},\omega \in \left(0,\frac{1}{\text{3}}\right).$

证明：定义

$Pred\left(s_k\right)=-h_k{g}_k^{\text{T}}{s}_k-\frac{1}{2}{h}_k^2{s}_k^{\text{T}}{B}_k{s}_k.$ (23)

其中

$h_k=\frac{1+c_k^{\text{T}}{s}_k}{\left(1-a_k^{\text{T}}{s}_k\right)\left(1-b_k^{\text{T}}{s}_k\right)}>0.$ (24)

由分式模型定义可得，

$\left|a_k^{\text{T}}{s}_k\right|\le \Vert a_k\Vert {\Delta }_k\le \omega ,\omega \in \left(0,\frac{1}{3}\right).$

同理可得

$\left|b_k^{\text{T}}{s}_k\right|\le \omega ,\left|c_k^{\text{T}}{s}_k\right|\le \omega ,\omega \in \left(0,\frac{1}{3}\right).$

因此，可得

$\frac{\text{1}}{1-a_k^{\text{T}}{s}_k}=1+a_k^{\text{T}}{s}_k+o\left(\Vert s_k\Vert \right),$ (25)

$\frac{\text{1}}{1-b_k^{\text{T}}{s}_k}=1+b_k^{\text{T}}{s}_k+o\left(\Vert s_k\Vert \right),$ (26)

所以，可得

$h_k{g}_k^{\text{T}}{s}_k=g_k^{\text{T}}{s}_k+{\kappa }_k{g}_k^{\text{T}}{s}_k+o\left({\Vert s_k\Vert }^2\right),$ (27)

$h_k^{\text{2}}{s}_k^{\text{T}}{B}_k{s}_k=s_k^{\text{T}}{B}_k{s}_k+o\left({\Vert s_k\Vert }^2\right),$ (28)

其中

${\kappa }_k=a_k^{\text{T}}{s}_k+b^{\text{T}}{s}_k+c^{\text{T}}{s}_k.$ (29)

则由引理1和(27)、(28)得

$-g_k^{\text{T}}{s}_k-{\kappa }_k{g}_k^{\text{T}}{s}_k-o\left({\Vert s_k\Vert }^2\right)-\frac{1}{2}{s}_k^{\text{T}}{B}_k{s}_k-\frac{1}{2}o\left({\Vert s_k\Vert }^2\right)\ge \frac{1}{2}\frac{\Vert g_k\Vert }{\Vert B_k\Vert }\min \left\{\Vert g_k\Vert ,\frac{\xi {\Delta }_k}{\Vert B_k{}^{-1}\Vert }\right\},$

且由(12)和矩阵的相容性可得

${\Delta }_k=c^p\frac{\Vert s_{k-1}\Vert }{\Vert q_{k-1}\Vert }\Vert g_k\Vert \ge c^p\Vert B_k{}^{-1}\Vert \Vert g_k\Vert ,$ (30)

则有

$\begin{array}{c}-g_k^{\text{T}}{s}_k-{\kappa }_k{g}_k^{\text{T}}{s}_k-\frac{1}{2}{s}_k^{\text{T}}{B}_k{s}_k\ge \frac{1}{2}\frac{\Vert g_k\Vert }{\Vert B_k\Vert }\min \left\{\Vert g_k\Vert ,\frac{\xi {\Delta }_k}{\Vert B_k{}^{-1}\Vert }\right\}\\ \ge \frac{1}{2}\frac{\Vert g_k\Vert }{\Vert B_k\Vert }\min \left\{\Vert g_k\Vert ,\frac{\xi c^p\Vert B_k{}^{-1}\Vert \Vert g_k\Vert }{\Vert B_k{}^{-1}\Vert }\right\}\\ \ge \frac{1}{2}\frac{{\Vert g_k\Vert }^2}{\Vert B_k\Vert }\min \left\{1,\xi c^p\right\}\\ \ge \frac{1}{2M_1}\min \left\{1,\xi c^p\right\}{\Vert g_k\Vert }^2\end{array}$

令 $\tilde{k}=\frac{1}{2M_1}\min \left\{1,\xi c^p\right\}$ ，则证明完毕。

引理4 若序列{x_k}由算法2生成。那么对于所有 $k\in {\rm N}\cup \left\{0\right\}$ ，有 $x_k\in L\left(x_0\right)$ ， $\left\{f_{l\left(k\right)}\right\}$ 是递减序列。

证明：根据 $f_{l\left(k\right)},R_k$ 定义，可得

$f_{l\left(k\right)}={\eta }_k{f}_{l\left(k\right)}+\left(1-{\eta }_k\right)f_{l\left(k\right)}\ge {\eta }_k{f}_{l\left(k\right)}+\left(1-{\eta }_k\right)f_k=R_k.$ (31)

显然有， $f_0=R_0$ 。现假设 $x_k\in L\left(x_0\right)$ 成立，我们需通过数学归纳法证明 $x_{k\text{+1}}\in L\left(x_0\right)$ 成立即可。

从以下两个方面证明：

1) 当 $k\in I$ ，则有

$R_k-f\left(x_k+s_k\right)\ge \mu \left(Pred\left(s_k\right)\right)\ge \frac{1}{2}\mu \frac{\Vert g_k\Vert }{\Vert B_k\Vert }\min \left\{\Vert g_k\Vert ,\frac{\xi {\Delta }_k}{\Vert B_k^{-1}\Vert }\right\}\ge 0.$ (32)

2) 当 $k\in J$ ，由 ${\alpha }_k$ 的定义可知 ${\alpha }_k>0$ ，由(7)、(29)可得 $0<\Vert {\kappa }_k\Vert \le 3\omega <1$ ，由假设(H2)得 $s^{\text{T}}{B}_{k}s\ge m{\Vert s\Vert }^2>0$ ，则有

$g_k^{\text{T}}{s}_k<g_k^{\text{T}}{s}_k\text{+}{\kappa }_k{g}_k^{\text{T}}{s}_k\text{+}\frac{1}{2}{s}_k^{\text{T}}{B}_k{s}_k.$

由引理3得到 $\beta {\alpha }_k{g}_k^{\text{T}}{s}_k\le 0$ 。则有

$f\left(x_k+{\alpha }_k{s}_k\right)\le R_k+\beta {\alpha }_k{g}_k^{\text{T}}{s}_k\le R_k.$ (33)

通过式子(31)~(33)可得

$f_{k+1}\le R_k\le f_{l\left(k\right)}\le f_0,k\in {\rm N}\cup \left\{0\right\}$ (34)

所以， $x_{k\text{+1}}\in L\left(x_0\right)$ 成立。

接着，证明序列 $\left\{f_{l\left(k\right)}\right\}$ 是递减数列。为此考虑以下情况：

1) 对 $k<N$ ，明显有 $m\left(k\right)=k$ 。因此，对任意k，有 $f_k\le f_0$ ，可得 $f_{l\left(k\right)}=f_0$ 。

2) 对 $k\ge N$ ， $m\left(k+1\right)\le m\left(k\right)+1$ 。根据 $f_{l\left(k+1\right)}$ 的定义和(34)，可得

$f_{l\left(k+1\right)}=\underset{0\le j\le m(k+1)}{\max }\left\{f\left(x_{k+1-j}\right)\right\}\le \underset{0\le j\le m\left(k\right)+1}{\max }\left\{f_{k+1-j}\right\}=\max \left\{f_{l\left(k\right)},f_{k+1}\right\}\le f_{l\left(k\right)}.$ (35)

因此，这两种情况都表明 $f_{l\left(k+1\right)}$ 是递减序列。

引理5 若序列{x_k}由算法2生成，则有

$f_{k+1}\le R_{k+1},\forall k\in {\rm N}\cup \left\{0\right\}.$ (36)

证明：根据 $f_{l\left(k+1\right)}$ 的定义，对于所有的 $k\in {\rm N}\cup \left\{0\right\}$ ，我们有 $f_{k+1}\le f_{l\left(k+1\right)}$ ，则

$\begin{array}{c}{f}_{k+1}={\eta }_{k+1}{f}_{k+1}+\left(1-{\eta }_{k+1}\right)f_{k+1}\\ \le {\eta }_{k+1}{f}_{l\left(k+1\right)}+\left(1-{\eta }_{k+1}\right)f_{k+1}\\ =R_{k+1},\forall k\in \text{N}\cup \left\{0\right\}.\end{array}$

引理6 [19] 若序列{x_k}由算法2生成，则有

$\underset{k\to \infty }{\lim }{f}_{l\left(k\right)}=\underset{k\to \infty }{\lim }f\left(x_k\right).$ (37)

引理7 假设(H1)、(H2)、(H3)成立，则存在常数Q > 0使得对任意的k有

$\left|\left[f\left(x_k\right)-f\left(x_k+s_k\right)\right]-\left[{\varphi }_k\left(0\right)-{\varphi }_k\left(s_k\right)\right]\right|\le \frac{1}{2}\left(Q-\tilde{k}\right){\Delta }_k^2.$ (38)

证明：假设存在正数Q，使得 $\Vert {\nabla }^{2}f\left(x\right)\Vert \le Q$ ，则由引理3和Taylor展开式得

$\begin{array}{l}\left|\left[f\left(x_k\right)-f\left(x_k+s_k\right)\right]-\left[{\varphi }_k\left(0\right)-{\varphi }_k\left(s_k\right)\right]\right|\\ =\left|f\left(x_k\right)-f\left(x_k+s_k\right)+g_k^{\text{T}}{s}_k+{\kappa }_k{g}_k^{\text{T}}{s}_k+\frac{1}{2}{s}_k^{\text{T}}{B}_k{s}_k+o\left({\Vert s_k\Vert }^2\right)\right|\\ =\left|-\frac{1}{2}{s}_k^{\text{T}}{\nabla }^{2}f\left(x_k+v_k{s}_k\right)s_k+{\kappa }_k{g}_k^{\text{T}}{s}_k+\frac{1}{2}{s}_k^{\text{T}}{B}_k{s}_k+o\left({\Vert s_k\Vert }^2\right)\right|\\ \le \frac{1}{2}\left(Q-\tilde{k}\right){\Vert s_k\Vert }^2\\ \le \frac{1}{2}\left(Q-\tilde{k}\right){\Delta }_k^{\text{2}},\end{array}$

其中 $\tilde{k}=\frac{1}{2M_1}\min \left\{1,\xi c^p\right\}$ 。则结论得证。

定理1 假设(H1)、(H2)、(H3)成立，序列 $\left\{\Vert g_k\Vert \right\},\left\{\Vert B_k\Vert \right\}$ 是有界的，那么对任意的 $\epsilon >0$ ，算法2在有限次迭代后终止。

证明：反证法。

首先证明 $\Vert g_k\Vert >\epsilon >0$ 时必有 $\underset{k\to \infty }{\lim }{\Delta }_k=0$ 。由 $r_k$ 的定义知：

(1) 若 $k\in I$ 时，

$R_k-f\left(x_k+s_k\right)\ge \mu \left(Pred\left(s_k\right)\right)\ge \frac{1}{2}\mu \frac{\Vert g\Vert }{\Vert B\Vert }\min \left\{\Vert g\Vert ,\frac{\xi {\Delta }_k}{\Vert B^{-1}\Vert }\right\}\ge \frac{1}{2}\mu \epsilon \min \left\{\frac{\epsilon }{M_1},\xi {\Delta }_k\right\},$ (39)

其中 $\xi =\frac{1-\omega }{{\left(1+\omega \right)}^2},\omega \in \left(0,\frac{1}{3}\right)$ 。

因 $f_k$ 有界可得 $R_k$ 有界，所以

$+\infty >{\displaystyle \underset{k=1}{\overset{\infty }{\sum }}{R}_k-f\left(x_k+s_k\right)}\ge {\displaystyle \underset{k\in I}{\sum }{R}_k-f\left(x_k+s_k\right)}\ge {\displaystyle \underset{k\in I}{\sum }\mu \left(Pred\left(s_k\right)\right)}\ge {\displaystyle \underset{k\in I}{\sum }\frac{1}{2}\mu \epsilon \min \left\{\frac{\epsilon }{M_1},\xi {\Delta }_k\right\}},$ (40)

又因为

${\displaystyle \underset{k\in I}{\sum }\frac{1}{2}\mu \epsilon \min \left\{\frac{\epsilon }{M_1},\xi {\Delta }_k\right\}}<+\infty ,$ (41)

所以 ${\displaystyle \underset{k\in I}{\sum }{\Delta }_k}$ 是收敛的，故必有 $\underset{k\to \infty }{\lim }{\Delta }_k=0$ 。

由于 ${\Delta }_k:=c^p\frac{\Vert s_{k-1}\Vert }{\Vert q_{k-1}\Vert }\Vert g_k\Vert \ge c^p\frac{\Vert g_k\Vert }{\Vert B_k\Vert }$ ，对充分大的k，则有

${\Delta }_k\ge c^p\frac{\epsilon }{M_1}>0$ (42)

这与 $\underset{k\to \infty }{\lim }{\Delta }_k=0$ 矛盾，从而定理得证。

(2) 若 $k\in J$ 时，由(34)~(36)可得

$f_k\le R_k\le f_{l\left(k\right)},$ (43)

因 $f_k$ 有界以及引理6可得 $R_k$ 有界且收敛，所以 $R_k-f\left(x_k+{\alpha }_k{s}_k\right)\ge -\beta {\alpha }_k{g}_k^{\text{T}}{s}_k>0$ 。

因为 $s_k$ 是下降方向，有 $f_{k+1}\le f_k$ ，可得 $R_k\ge \max \left\{f_{k+1},f_{k+2},\cdots \right\}-\beta {\alpha }_k{g}_k^{\text{T}}{s}_k.$

又根据 $R_k$ 的定义得 $R_{k+1}$ 是 $f_{l\left(k+1\right)}$ 和 $f_{\left(k+1\right)}$ 的凸组合，则有 $R_{k+1}\le \max \left\{f_{l\left(k+1\right)},f_{k+1}\right\}$ ，可得

$R_k-R_{k+1}\ge -\beta {\alpha }_k{g}_k^{\text{T}}{s}_k>0.$ (44)

所以对充分大的k，这与 $R_k$ 收敛矛盾，从而定理得证。

定理2 假设(H1)、(H2)、(H3)成立，则有

$\underset{k\to \infty }{\lim }\inf \Vert g_k\Vert =0.$ (45)

证明：反证法

假设存在充分大的k，有 $g_k\ge {\epsilon }_{\text{0}}>0$ 。由引理7和式子(4-24)得

$\begin{array}{c}\left|\frac{f\left(x_k\right)-f\left(x_k+s_k\right)}{Pred\left(s_k\right)}-1\right|=\left|\frac{\left[f\left(x_k\right)-f\left(x_k+s_k\right)\right]-\left[{\varphi }_k\left(0\right)-{\varphi }_k\left(s_k\right)\right]}{Pred\left(s_k\right)}\right|\\ =\left|\frac{\frac{1}{2}\left(Q-\tilde{k}\right){\Delta }_k^2}{Pred\left(s_k\right)}\right|\le \frac{\left(Q-\tilde{k}\right){\Delta }_k^2}{\epsilon \min \left\{\frac{\epsilon }{M_1},\xi {\Delta }_k\right\}}.\end{array}$

又 $r_k=\frac{R_k-f\left(x_k+s_k\right)}{Pred\left(s_k\right)}\ge \frac{f\left(x_k\right)-f\left(x_k+s_k\right)}{Pred\left(s_k\right)}$ ，令 $k\to \infty$ ，由于 $\underset{k\to \infty }{\lim }{\Delta }_k=0$ ，则

$\underset{k\to \infty }{\lim }\frac{f\left(x_k\right)-f\left(x_k+s_k\right)}{Pred\left(s_k\right)}=\text{1}.$ (46)

所以，必存在一个充分大的k，有 $r_k\ge u$ ，且存在 $c>0$ 使得

${\Delta }_k:=c^p\frac{\Vert s_{k-1}\Vert }{\Vert q_{k-1}\Vert }\Vert g_k\Vert \ge c^p\frac{\Vert g_k\Vert }{\Vert B_k\Vert }>c^p\frac{{\epsilon }_0}{M_1}>0,$

这与 $\underset{k\to \infty }{\lim }{\Delta }_k=0$ 矛盾，从而定理得证。

5. 数值结果

本节给出算法2 (non monotonic adaptive fractional trust region, NAFTR)的数值试验结果，并与分式模型信赖域算法(fractional trust region, FTR) (文献 [18] 中算法3)做比较。算法用Matlab R2020a编程实现，数值实验在PC机上Windows系统中进行。

本节选出的18个测试函数选自于文献 [20] [21] ，初始点的选取与文献 [18] 相同。同时在本文的算法2中取 $a_k=b_k=c_k=0$ ，得到二次模型信赖域子问题(non monotonic adaptive trust region, NATR)；取 $b_k=c_k=0$ ，得到锥模型信赖域子问题(non monotonic adaptive conic trust region, NACTR)，一起与分式模型子问题进行比较。算法2选取的迭代终止条件为最后一次迭代梯度的范数小于10⁻⁴。在表中， $\Vert g_k\Vert$ 是最后一次迭代梯度的欧式范数；CPU(s)表示算法总的迭代时间(单位秒)。如果计算不出结果或者时间超过200 s或者迭代次数超过1000次，则用“----”表示。在算法2中选择的参数为：

$\omega =0.33,{\Delta }_0=1,{\Delta }_{\max }=10,u=0.25,N=4,\rho =\mathrm{0.5.}$

另外，本文选择 ${\eta }_0=0.15$ 且 ${\eta }_k$ 按如下方式更新：

${\eta }_k=\{\begin{array}{l}{\eta }_0/2,\text{if}k=1,\\ \left({\eta }_{k-1}+{\eta }_{k-2}\right)/2,\text{if}k\ge 2.\end{array}$

以及半径相关参数c的更新方式如下：

$c=\{\begin{array}{l}0.3,\text{if}\frac{{\Delta }_{\max }}{10}<\Delta \le {\Delta }_{\max },\\ 0.45,\text{if}{10}^{-6}<\Delta \le \frac{{\Delta }_{\max }}{10},\\ 0.6,\text{o}\text{.w}.\end{array}$

测试函数如表1，数值结果如表2，表3。

Table 1. Testing issues

表1. 测试问题

Table 2. Numerical results

表2. 数值结果

Table 3. Numerical results of the improved algorithm under different level vectors

表3. 改进后算法在不同水平向量下的数值结果

表2为NAFTR和FTR在18个测试问题下的数值比较，其中维数最高为11。对于其中的15个测试问题，NAFTR算法的迭代次数或者是CPU运行时间是优于FTR算法的，3个问题的数值结果几乎和原算法一样。

与此同时，在NAFTR算法中使水平向量 $a_k=b_k=c_k=0$ 或者 $b_k=c_k=0$ ，分别得到二次模型以及锥模型信赖域子问题。数值结果如表3所示，可以看出，分式模型子问题的数值结果明显优于二次模型子问题和锥模型子问题。

6. 结论

本文从理论上证明了非单调自适应分式模型信赖域算法的全局收敛性。在数值实验中，新算法比文献 [18] 的算法3的数值结果更优。从一定程度上证明了引用非单调自适应技术能使信赖域算法的效率更高，尤其在维度较高的问题上。

另外，分式模型子问题拓宽了信赖域子问题的适用性，在大规模以及较复杂的问题上分式模型是比二次模型和锥模型子问题更为有效和稳健的。

因此，无论是从理论还是数值结果上看，非单调自适应分式模型信赖域算法都值得我们进一步探究。但是，本文对分式模型的水平向量的插值条件或者是子问题求解方法的研究比较单一，这些内容都需要我们深思研究。