一种改进的非单调信赖域两步Levenberg-Marquardt方法

An Improved Non-Monotonic Trust Region Two-Step Levenberg-Marquardt Method

摘要: 本文提出了一种求解非线性方程组的改进型非单调信赖域两步Levenberg-Marquardt方法，证明了该方法在适当条件下具有全局收敛性。数值试验表明该方法比单步Levenberg-Marquardt方法具有更好的数值效果。

Abstract: In this paper, an improved nonmonotonic trust region two-step Levenberg-Marquardt method for solving nonlinear equations is proposed, and it is proved that the method has global convergence under appropriate conditions. Numerical experiments show that the method has better numerical results than the one-step Levenberg-Marquardt method.

1. 引言

本文考虑求解如下非线性方程组的数值方法：

$F\left(x\right)=0,$ (1.1)

其中$F$ 是$R^n$ 到$R^n$ 的连续可微函数，其Jacobian阵记为$J\left(x\right)\triangleq F\prime \left(x\right)$ 。非线性方程组在物理学、经济学和产品管理等许多领域都具有广泛的应用，例如非线性优化问题的KKT系统、非线性微分方程的离散形式都是非线性方程组[1] [2]。因此设计高效求解非线性方程组的算法是计算数学领域的一个重要研究课题。

有许多实用的算法可以求解非线性方程组，其中Levenberg-Marquardt (LM)方法是一种经典方法。在每次迭代中，它都会计算LM方向

$d_k=-{\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)}^{-1}{J}_k^{\text{T}}{F}_k,$

其中$F_k=F\left(x_k\right),J_k=F\prime \left(x_k\right)$ ，以及LM参数${\lambda }_k>0$ 在每次迭代中更新。

LM参数${\lambda }_k$ 的选择对LM方法的计算效率至关重要。为了提高计算效率，许多学者对LM参数进行研究。Yamashita和Fukushima [3]证明，当${\lambda }_k={\Vert F_k\Vert }^2$ 时，LM方法在局部误差界这一较弱的条件下具有二次收敛速度。然而，当序列$\left\{x_k\right\}$ 远离解集$X$ 时，$\Vert F_k\Vert$ 可能非常大，会导致${\lambda }_k$ 也很大，这将使得$d_k$ 变得很小，从而降低算法的效率。于是Fan和Yuan [4]使用了${\lambda }_k={\mu }_k{\Vert F_k\Vert }^{\delta }$ ，其中$\delta \in \left(1,2\right]$ ，${\mu }_k$ 在每次迭代中都使用信赖域方法更新，此时LM方法在一些合适的条件下也具有二次收敛速度。进一步，Ma和Jiang [5]将$\Vert J_k^{\text{T}}{F}_k\Vert$ 引入LM方法用于求解奇异非线性方程组，使用了$\Vert F_k\Vert$ 和$\Vert J_k^{\text{T}}{F}_k\Vert$ 的凸组合作为新的LM参数${\lambda }_k=\theta \Vert F_k\Vert +\left(1-\theta \right)\Vert J_k^{\text{T}}{F}_k\Vert$ ，其中$\theta \in \left[0,1\right]$ 。随后，Fan和Pan [6]提出了${\lambda }_k={\mu }_k\left[\theta \Vert F_k\Vert +\left(1-\theta \right)\Vert J_k^{\text{T}}{F}_k\Vert \right]$ ，并证明了在弱于非奇异性的局部误差条件下仍然保持二次收敛。

为了提高算法的收敛速度和效率，Fan [7]提出了一种两步LM方法。在每次迭代中，首先通过求解

$\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)d=-J_k^{\text{T}}{F}_k,其中{\lambda }_k={\mu }_k{\Vert F_k\Vert }^{\delta },\delta \in \left[1,2\right],$ (1.2)

来获得LM方向$d_k^{LM}=-{\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)}^{-1}{J}_k^{\text{T}}{F}_k$ ，其中${\mu }_k$ 由信赖域方法更新。再通过求解

$\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)d=-J_k^{\text{T}}F\left(y_k\right),其中y_k=x_k+d_k^{LM},$ (1.3)

来获得近似的LM方向$d_k^{MLM}$ ，并设置迭代方向为$d_k=d_k^{LM}+d_k^{MLM}$ 。Fan证明了该两步LM方法具有全局收敛性和在局部误差界下具有三次收敛速度。

近年来，非单调方法被应用于多种优化算法中，显著提升了算法的收敛性能。1986年，Grippo等[8]提出了非单调Armijo线搜索，该方法是非线性优化的非单调算法的新突破。随后，Deng等[9]首次将非单调思想与信赖域方法相结合，提出了一种具有强收敛性的非单调信赖域方法。研究表明，使用非单调技术可以提高找到全局最优值的可能性和算法的收敛率[8] [10]。由于非单调信赖域方法的良好数值效果，越来越多的学者致力于对非单调方法的研究。最近，Zhao等[11]在LM方法中采用非单调信赖域方法来确保全局收敛。传统的信赖域方法要求目标函数值${\Vert F_k\Vert }^2$ 严格单调下降，这有可能会陷入局部最优，而文献[11]通过引入$W_{k+1}$ ：

$W_{k+1}=\left(1-\tau \right)W_k+\tau {\Vert F_{k+1}\Vert }^2,其中\tau \in \left(0,1\right],$

来允许${\Vert F_{k+1}\Vert }^2$ 偶尔上升，只要$W_{k+1}$ 整体下降即可，从而提升算法的全局收敛性。并通过与Fan [12]的单调信赖域LM方法进行数值实验比较，表明引入的非单调信赖域方法提高了LM方法的数值性能。

Zhao在文献[11]中还利用$\Vert F_k\Vert$ 和$\Vert J_k^{\text{T}}{F}_k\Vert$ 的凸组合，提出了一种新的LM参数 ${\lambda }_k={\mu }_k\left[\theta {\Vert F_k\Vert }^{\delta }+\left(1-\theta \right){\Vert J_k^{\text{T}}{F}_k\Vert }^{\delta }\right]$ ，其中$\theta \in \left[0,1\right]$ 和$\delta \in \left(0,3\right)$ 。这是LM参数的更通用选择，它不仅包括上述所提到的所有LM选择，而且在局部误差界下，证明了新的LM方法至少具有阶数为$\min \left\{1+\delta ,4-\delta ,2\right\}$ 的超线性收敛率。

受上述文献的启发，在本文中，我们旨在提出一种新的LM方法，该方法采用文献[11]中的LM参数以及采用非单调信赖域，将其改进为两步LM方法。在文献[7]中两步LM方法已证明具有三次收敛速度，通过与[7]同样的分析，可以证明本文改进的两步LM方法在$\delta \in \left[1,2\right]$ 时也具有三次收敛速度。

本文的组织结构如下。在第2节中，我们详细介绍改进型非单调信赖域的两步LM方法。在第3节中，建立了所提方法的全局收敛性。在第4节中，我们应用新的两步LM方法求解一些非线性方程并报告数值结果。最后，我们在第5节进行总结。在整篇论文中，假设$X$ 表示的解集是非空的，且在所有情况下$\Vert \cdot \Vert$ 是指2-范数。

2. 算法的提出

我们取

$\Phi \left(x\right)={\Vert F\left(x\right)\Vert }^2$

作为(1.1)的评价函数。两步LM方法在每一次迭代中不仅要通过(1.2)计算LM方向$d_k$ ，还要通过(1.3)计算近似LM方向${\widehat{d}}_k$ 。

在标准的信赖域方法中，通常我们会将$\Phi \left(x\right)$ 在第$k$ 次迭代时的实际下降量$Are{d}_k$ 、预测下降量为$Pre{d}_k$ 和下降比$r_k$ 分别定义为

$Are{d}_k={\Vert F_k\Vert }^2-{\Vert F\left(x_k+d_k+{\widehat{d}}_k\right)\Vert }^2,$ (2.1)

$Pre{d}_k={\Vert F_k\Vert }^2-{\Vert F_k+J_k\left(d_k+{\widehat{d}}_k\right)\Vert }^2,$ (2.2)

$r_k=\frac{Are{d}_k}{Pre{d}_k}.$ (2.3)

但是在两步LM方法中，因为不能证明(2.2)是非负的，所以我们不能像往常一样将预测下降量定义为(2.2)，因此需要开发一种新的预测下降量。

注意到LM方向$d_k$ 是下列最小化关于$d$ 的优化问题的解：

$\underset{d\in R^n}{\min }{\phi }_{k,1}\left(d\right)\triangleq {\Vert F_k+J_{k}d\Vert }^2+{\lambda }_k{\Vert d\Vert }^2.$ (2.4)

如果我们令

${\Delta }_{k,1}=\Vert d_k\Vert =\Vert -{\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)}^{-1}{J}_k^{\text{T}}{F}_k\Vert ,$

那么可以验证$d_k$ 也是下列信赖域问题的解：

$\underset{d\in R^n}{\min }{\Vert F_k+J_{k}d\Vert }^2\text{s}\text{.t}.\Vert d\Vert \le {\Delta }_{k,1}.$

根据Powell [13]给出的著名结果，我们知道

${\Vert F_k\Vert }^2-{\Vert F_k+J_k{d}_k\Vert }^2\ge \Vert J_k^{\text{T}}{F}_k\Vert \min \left\{\Vert d_k\Vert ,\frac{\Vert J_k^{\text{T}}{F}_k\Vert }{\Vert J_k^{\text{T}}{J}_k\Vert }\right\}.$ (2.5)

同理，近似LM方向${\widehat{d}}_k$ 不仅是下列最小化关于$d$ 的优化问题的解：

$\underset{d\in R^n}{\min }{\phi }_{k,2}\left(d\right)\triangleq {\Vert F\left(y_k\right)+J_{k}d\Vert }^2+{\lambda }_k{\Vert d\Vert }^2.$ (2.6)

也是下列信赖域问题的解：

$\underset{d\in R^n}{\min }{\Vert F\left(y_k\right)+J_{k}d\Vert }^2\text{s}\text{.t}.\Vert d\Vert \le {\Delta }_{k,2}.$

其中${\Delta }_{k,2}=\Vert {\widehat{d}}_k\Vert =\Vert -{\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)}^{-1}{J}_k^{\text{T}}F\left(y_k\right)\Vert$。同样可以得到

${\Vert F\left(y_k\right)\Vert }^2-{\Vert F\left(y_k\right)+J_k{\widehat{d}}_k\Vert }^2\ge \Vert J_k^{\text{T}}F\left(y_k\right)\Vert \min \left\{\Vert {\widehat{d}}_k\Vert ,\frac{\Vert J_k^{\text{T}}F\left(y_k\right)\Vert }{\Vert J_k^{\text{T}}{J}_k\Vert }\right\}.$ (2.7)

现在，根据不等式(2.5)和(2.7)，我们可以合理地将新的预测下降量定义为

$\stackrel{⌢}{Pre{d}_k}={\Vert F_k\Vert }^2-{\Vert F_k+J_k{d}_k\Vert }^2+{\Vert F\left(y_k\right)\Vert }^2-{\Vert F\left(y_k\right)+J_k{\widehat{d}}_k\Vert }^2.$ (2.8)

并且它总是非负的，满足以下不等式

$\stackrel{⌢}{Pre{d}_k}\ge \Vert J_k^{\text{T}}{F}_k\Vert \min \left\{\Vert d_k\Vert ,\frac{\Vert J_k^{\text{T}}{F}_k\Vert }{\Vert J_k^{\text{T}}{J}_k\Vert }\right\}+\Vert J_k^{\text{T}}F\left(y_k\right)\Vert \min \left\{\Vert {\widehat{d}}_k\Vert ,\frac{\Vert J_k^{\text{T}}F\left(y_k\right)\Vert }{\Vert J_k^{\text{T}}{J}_k\Vert }\right\}.$ (2.9)

受文献[11]的非单调信赖域方法的启发，我们定义新的实际下降量为

$\stackrel{⌢}{Are{d}_k}=W_k-{\Vert F\left(x_k+d_k+{\widehat{d}}_k\right)\Vert }^2$ (2.10)

其中$W_{k+1}=\left(1-\tau \right)W_k+\tau {\Vert F_{k+1}\Vert }^2,\tau \in \left(0,1\right]$ 。值得注意的是，$W_k$ 是$W_{k-1}$ 和${\Vert F_k\Vert }^2$ 的凸组合。由于我们设定$W_0={\Vert F_0\Vert }^2$ ，因此$W_k$ 是${\Vert F_0\Vert }^2,{\Vert F_1\Vert }^2,\cdots ,{\Vert F_k\Vert }^2$ 的凸组合。从而可以定义新的下降比为${\stackrel{⌢}{r}}_k=\frac{\stackrel{⌢}{Are{d}_k}}{\stackrel{⌢}{Pre{d}_k}}$ ，用于决定是否接受试探步以及如何调整LM参数。

接下来，我们将详细地描述新的两步LM方法。

算法1

步1. 选择一个初始点$x_0\in R^n$ ，令$W_0={\Vert F_0\Vert }^2$ ，给定参数${\mu }_0\ge m_0>0$ ，$0<p_0\le p_1\le p_2<1$ ，$\theta \in \left[0,1\right]$ ，$\tau \in \left(0,1\right]$ 和$\delta \in \left(0,3\right)$ 。置$k:=0$ 。

步2. 如果$\Vert J_k^{\text{T}}{F}_k\Vert =0$ ，则停止计算。否则，令

${\lambda }_k={\mu }_k\left[\left(1-\theta \right){\Vert F_k\Vert }^{\delta }+\theta {\Vert J_k^{\text{T}}{F}_k\Vert }^{\delta }\right],$ (2.11)

通过求解以下线性方程组，得到$d_k$ ：

$\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)d=-J_k^{\text{T}}{F}_k,$ (2.12)

令$y_k=x_k+d_k$ ；再求解以下方程组，得到${\widehat{d}}_k$ ：

$\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)d=-J_k^{\text{T}}F\left(y_k\right),$ (2.13)

再令$s_k=d_k+{\widehat{d}}_k$ 。

步3. 通过(2.8)和(2.10)计算下降比

${\stackrel{⌢}{r}}_k=\frac{\stackrel{⌢}{Are{d}_k}}{\stackrel{⌢}{Pre{d}_k}}$ (2.14)

步4. 令

$x_{k+1}=\{\begin{array}{l}{x}_k+s_k,若{\stackrel{⌢}{r}}_k\ge p_0,\\ x_k,若{\stackrel{⌢}{r}}_k<p_0.\end{array}$ (2.15)

令

$W_{k+1}=\left(1-\tau \right)W_k+\tau {\Vert F_{k+1}\Vert }^2.$ (2.16)

步5. 选择${\mu }_{k+1}$ 为

${\mu }_{k+1}=\{\begin{array}{l}4{\mu }_k,若\stackrel{⌢}{r}<p_1,\\ {\mu }_k,若\stackrel{⌢}{r}\in \left[p_1,p_2\right],\\ \max \left\{\frac{{\mu }_k}{4},m_0\right\}\text{,}若\stackrel{⌢}{r}>p_2.\end{array}$ (2.17)

置$k:=k+1$ ，转步2。

注：

两步LM方法的计算成本与单步LM方法的计算成本几乎相同，因为(2.13)只涉及$F\left(y_k\right)$ ，并且在求解(2.12)之后，可以利用$J_k^{\text{T}}{J}_k+{\lambda }_{k}I$ 的可用分解。

3. 全局收敛性

为了证明算法1的全局收敛性，我们做出如下假设。

假设A

(1) $F\left(x\right)$ 在$R^n$ 上是连续可微的。

(2) $F\left(x\right)$ 和$J\left(x\right)$ 在$R^n$ 上是Lipschitz连续的，即对$\forall x,y\in R^n$ ，存在正的常数$L$ ，使得

$\Vert J\left(x\right)-J\left(y\right)\Vert \le L\Vert x-y\Vert ,$ (3.1)

$\Vert F\left(x\right)-F\left(y\right)\Vert \le L\Vert x-y\Vert .$ (3.2)

假设A也意味着，对$\forall x,y\in R^n$ ，

$\Vert F\left(y\right)-F\left(x\right)-J\left(x\right)\left(y-x\right)\Vert \le L{\Vert y-x\Vert }^2.$ (3.3)

$\Vert J\left(x\right)\Vert \le L.$ (3.4)

引理3.1 设$\left\{x_k\right\}$ 是由算法1产生的序列，则对所有的$k\ge 0$ ，都有

${\Vert F_k\Vert }^2\le W_k,W_{k+1}\le W_k和\Vert F_k\Vert \le \Vert F_0\Vert .$

证明. 首先，我们假设对某些$k$ ，有${\Vert F_k\Vert }^2\le W_k$ 。如果${\stackrel{⌢}{r}}_k<p_0$ ，那么由(2.15)可得$x_{k+1}=x_k$ ，则

$W_k\ge {\Vert F_k\Vert }^2={\Vert F_{k+1}\Vert }^2.$ (3.5)

如果${\stackrel{⌢}{r}}_k\ge p_0$ ，那么由(2.15)可得$x_{k+1}=x_k+s_k$ ，再由(2.14)得

${\stackrel{⌢}{r}}_k=\frac{W_k-{\Vert F\left(x_k+s_k\right)\Vert }^2}{\stackrel{⌢}{Pre{d}_k}}=\frac{W_k-{\Vert F_{k+1}\Vert }^2}{\stackrel{⌢}{Pre{d}_k}}\ge p_0$ ,

上式结合(2.9)，意味着

$W_k\ge {\Vert F_{k+1}\Vert }^2+p_0\stackrel{⌢}{Pre{d}_k}\ge {\Vert F_{k+1}\Vert }^2.$ (3.6)

于是由(2.16)可知

$W_{k+1}=\left(1-\tau \right)W_k+\tau {\Vert F_{k+1}\Vert }^2\ge {\Vert F_{k+1}\Vert }^2.$

因为$W_0={\Vert F_0\Vert }^2$ ，所以通过对$k$ 进行归纳，我们可以得到对所有的$k\ge 0$ ，都有

${\Vert F_k\Vert }^2\le W_k,$

这就证得了引理的第一个结果。

然后，结合(3.5)和(3.6)可知对所有的$k\ge 0$ ，${\Vert F_{k\text{+}1}\Vert }^2\le W_k$ ，再由(2.16)可得 $W_{k+1}=\left(1-\tau \right)W_k+\tau {\Vert F_{k+1}\Vert }^2\le \left(1-\tau \right)W_k+\tau W_k=W_k$ ，即对所有的$k\ge 0$ ，都有

$W_{k+1}\le W_k,$

这就证得了引理的第二个结果。

此外，对所有的$k\ge 0$ ，我们有

${\Vert F_k\Vert }^2\le W_k\le W_0={\Vert F_0\Vert }^2.$

这就证得了引理的第三个结果。 □

定理3.1 设$\left\{x_k\right\}$ 是由算法1产生的序列，若假设A成立，则有

$\underset{k\to \infty }{\lim \inf }\Vert J_k^{\text{T}}{F}_k\left(x_k\right)\Vert =0.$ (3.7)

证明. 用反证法。假设$\underset{k\to \infty }{\lim \inf }\Vert J_k^{\text{T}}{F}_k\Vert \ne 0$ ，则存在常数$\overline{k}>0,\eta >0$，使得对$\forall k>\overline{k}$ ，有

$\Vert J_k^{\text{T}}{F}_k\Vert \ge \eta ,$ (3.8)

定义包含所有成功迭代点的指标集为

$S=\left\{k|{\stackrel{⌢}{r}}_k\ge p_0\right\}$

我们考虑以下两种情况，并得出矛盾。

情形1. $S$ 是无限的。在这种情形下，由(2.9)，(2.15)，(2.16)，(3.4)和(3.8)可得，对所有的$k\in S$ 以及$k>\overline{k}$ ，有

$\begin{array}{c}{W}_k-{\Vert F_{k+1}\Vert }^2=W_k-{\Vert F\left(x_k+s_k\right)\Vert }^2=\stackrel{⌢}{Are{d}_k}\\ \ge p_0\stackrel{⌢}{Pre{d}_k}\\ \ge p_0\Vert J_k^{\text{T}}{F}_k\Vert \min \left\{\Vert d_k\Vert ,\frac{\Vert J_k^{\text{T}}{F}_k\Vert }{\Vert J_k^{\text{T}}{J}_k\Vert }\right\}+p_0\Vert J_k^{\text{T}}F\left(y_k\right)\Vert \min \left\{\Vert {\widehat{d}}_k\Vert ,\frac{\Vert J_k^{\text{T}}F\left(y_k\right)\Vert }{\Vert J_k^{\text{T}}{J}_k\Vert }\right\},\\ \ge p_0\eta \min \left\{\Vert d_k\Vert ,\frac{\eta }{L^2}\right\}.\end{array}$

根据引理3.1的第二个结果，序列$\left\{W_k\right\}$ 单调递减且下有界，即存在一个常数$W^{*}\ge 0$ ，使得$\underset{k\to \infty }{\lim }{W}_k=W^{*}$ 。再由(2.16)，我们有

$\underset{k\to \infty }{\lim }{\Vert F_k\Vert }^2=\underset{k\to \infty }{\lim }\frac{W_k-\left(1-\tau \right)W_{k-1}}{\tau }=W^{*}.$

于是根据$\underset{k\to \infty }{\lim }\Vert F_k\Vert =\underset{k\to \infty }{\lim }{W}_k=W^{*}$ ，可知$\underset{k\in S,k\to \infty }{\lim }{d}_k=0$ 。

然而当$k\notin S$ 时，有$x_{k+1}-x_k=0$ 。因此可以得到

$\underset{k\to \infty }{\lim }{d}_k=0.$

上式结合(2.12)和(3.8)可得

$\underset{k\to \infty }{\lim }{\lambda }_k=+\infty .$ (3.9)

根据引理3。1的第三个结果以及(3.4)，有

$\left(1-\theta \right){\Vert F_k\Vert }^{\delta }+\theta {\Vert J_k^T{F}_k\Vert }^{\delta }\le \left(1-\theta \right){\Vert F_0\Vert }^{\delta }+\theta L^{\delta }{\Vert F_0\Vert }^{\delta }.$

上式结合(2.11)和(3.9)可得

$\underset{k\to \infty }{\lim }{\mu }_k=+\infty .$ (3.10)

此外，由$\widehat{d}$ 的定义和(3.3)，对所有充分大的$k$ 有

$\begin{array}{c}\Vert {\widehat{d}}_k\Vert =\Vert -{\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)}^{-1}{J}_k^{\text{T}}F\left(y_k\right)\Vert \\ \le \Vert {\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)}^{-1}{J}_k^{\text{T}}\left(F\left(y_k\right)-F_k-J_k{d}_k\right)\Vert \\ +\Vert {\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)}^{-1}{J}_k^{\text{T}}{F}_k\Vert +\Vert {\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)}^{-1}{J}_k^{\text{T}}{J}_k{d}_k\Vert \\ \le \Vert {\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)}^{-1}\Vert \Vert J_k\Vert \Vert F\left(y_k\right)-F_k-J_k{d}_k\Vert +\Vert d_k\Vert +\Vert d_k\Vert \\ \le {\lambda }_k^{-1}{L}^2{\Vert d_k\Vert }^2+2\Vert d_k\Vert \\ \le \overline{c}\Vert d_k\Vert .\end{array}$ (3.11)

其中$\overline{c}$ 是某个正的常数。于是

$\Vert s_k\Vert =\Vert d_k+{\widehat{d}}_k\Vert \le \left(1+\overline{c}\right)\Vert d_k\Vert .$

故由(2.1)，(2.8)，(2.9)，(3.4)，(3.8)和上式，对$\forall k>\overline{k}$ ，

$\begin{array}{c}\left|\frac{Are{d}_k-\stackrel{⌢}{Pre{d}_k}}{\stackrel{⌢}{Pre{d}_k}}\right|\le \left|\frac{{\Vert F\left(x_k+s_k\right)\Vert }^2-{\Vert F_k+J_k{d}_k\Vert }^2+{\Vert F\left(y_k\right)\Vert }^2-{\Vert F\left(y_k\right)+J_k{\widehat{d}}_k\Vert }^2}{\Vert J_k^{\text{T}}{F}_k\Vert \min \left\{\Vert d_k\Vert ,\frac{\Vert J_k^{\text{T}}{F}_k\Vert }{\Vert J_k^{\text{T}}{J}_k\Vert }\right\}+\Vert J_k^{\text{T}}F\left(y_k\right)\Vert \min \left\{\Vert {\widehat{d}}_k\Vert ,\frac{\Vert J_k^{\text{T}}F\left(y_k\right)\Vert }{\Vert J_k^{\text{T}}{J}_k\Vert }\right\}}\right|\\ \le \frac{\Vert F_k+J_k{s}_k\Vert O\left({\Vert s_k\Vert }^2+{\Vert d_k\Vert }^2\right)+O\left({\Vert s_k\Vert }^4+{\Vert d_k\Vert }^4\right)+\Vert F_k+J_k{d}_k\Vert O\left({\Vert d_k\Vert }^2\right)}{\eta \min \left\{\Vert d_k\Vert ,\frac{\eta }{L^2}\right\}}\\ \le \frac{\Vert F_k\Vert O\left({\Vert d_k\Vert }^2\right)+\Vert J_k{\widehat{d}}_k\Vert O\left({\Vert d_k\Vert }^2\right)}{\Vert d_k\Vert }\\ \to 0.\end{array}$

即得$k\to \infty$ ，有$\frac{Are{d}_k}{\stackrel{⌢}{Pre{d}_k}}\to 1$ 。根据引理3.1的第一个结果，对$\forall k\ge 0$ ，都有$W_k\ge {\Vert F_k\Vert }^2$ ，于是

$\stackrel{⌢}{Are{d}_k}\ge Are{d}_k$ 。故有

${\stackrel{⌢}{r}}_k=\frac{\stackrel{⌢}{Are{d}_k}}{\stackrel{⌢}{Pre{d}_k}}\ge \frac{Are{d}_k}{\stackrel{⌢}{Pre{d}_k}}\to 1.$

鉴于${\mu }_k$ 的更新规则，存在一个正的常数$\overline{m}>m$ ，使得${\mu }_k<\overline{m}$ 对所有充分大的$k$ 都成立，这与(3.10)相矛盾，即当$S$ 为无限集时，假设(3.8)不真。

情形2. $S$ 是有限的。在这种情形下，存在一个索引$\widehat{k}$ ，使得对所有的$k>\widehat{k}$ ，有${\stackrel{⌢}{r}}_k<p_0<p_1$ 。于是，通过算法1的第5步，对所有的$k>\widehat{k}$ ，都有${\mu }_{k+1}=4{\mu }_k$ ，因此

$\underset{k\to \infty }{\lim }{\mu }_k=+\infty .$ (3.12)

由(3.4)和(3.8)，我们有

$\Vert F_k\Vert \ge \frac{\Vert J_k^{\text{T}}{F}_k\Vert }{L}\ge \frac{\eta }{L},\forall k>\overline{k}.$

从而

$\left(1-\theta \right){\Vert F_k\Vert }^{\delta }+\theta {\Vert J_k^{\text{T}}{F}_k\Vert }^{\delta }\ge \frac{\left(1-\theta \right){\eta }^{\delta }}{L^{\delta }}+\theta {\eta }^{\delta }>0,\forall k>\overline{k}.$

再由(2.11)和(3.12)可得

$\underset{k\to \infty }{\lim }{\lambda }_k=+\infty .$

上式结合(2.12)和(3.8)可得

$\underset{k\to \infty }{\lim }{d}_k=0.$

类似于(3.11)，存在一个正的常数$\tilde{c}$ ，使得对所有充分大的$k\in S$ ，都有

$\Vert {\widehat{d}}_k\Vert \le \tilde{c}\Vert d_k\Vert .$

因此对所有充分大的$k\in S$ ，有

$\Vert s_k\Vert =\Vert d_k+{\widehat{d}}_k\Vert \le \left(1+\tilde{c}\right)\Vert d_k\Vert .$

通过与情形1相同的分析，我们可以得到${\stackrel{⌢}{r}}_k\to 1$ 。故存在一个正的常数$\tilde{m}>m$ ，使得${\mu }_k<\tilde{m}$ 对所有充分大的$k$ 都成立，这与(3.12)相矛盾，即当$S$ 为有限集时，假设(3.8)不真。

总结情形1和情形2，我们得到(3.7)并完成了证明。 □

4. 数值实验

为了验证算法的有效性，我们将文献[11]中的单步LM算法2.1 (记作算法SLM)与本文提出的两步LM算法1 (记作算法TLM)进行数值实验比较。所有程序均在MATLAB R2016a平台上编写，数值结果均在个人电脑上实现。算法所涉及的参数具体如下：

${\mu }_0\text{=}{10}^{-3},m_0={10}^{-8},\tau =0.5,p_0={10}^{-4},p_1=0.25,p_2=\mathrm{0.75.}$

我们选取算法终止条件为$\Vert J_k^{\text{T}}{F}_k\Vert \le {10}^{-6}$ ，计算以下两个具有不同初始点和不同大小的问题，测试函数均选自[14]：

(i) 扩展的Rosenbrock函数：$F\left(x\right)={\left(F_1\left(x\right),\cdots ,F_n\left(x\right)\right)}^{\text{T}}$ ，其中$n$ 是偶数，$i=1,\cdots ,\frac{n}{2}$ ，

$\begin{array}{l}{F}_{2i-1}\left(x\right)=10\left(x_{2i}-x_{2i-1}^2\right),\\ F_{2i}\left(x\right)=1-x_{2i-1}.\end{array}$

(ii) 扩展的Powell Singular函数：$F\left(x\right)={\left(F_1\left(x\right),\cdots ,F_n\left(x\right)\right)}^{\text{T}}$ ，其中$n$ 是正整数的四倍，$i=1,\cdots ,\frac{n}{4}$ ，

$\begin{array}{l}{F}_{4i-3}\left(x\right)=x_{4i-3}+10x_{4i-2},\\ F_{4i-2}\left(x\right)=\sqrt{5}\left(x_{4i-1}-x_{4i}\right),\\ F_{4i-1}\left(x\right)={\left(x_{4i-2}-2x_{4i-1}\right)}^2,\\ F_{4i}\left(x\right)=\sqrt{10}{\left(x_{4i-3}-x_{4i}\right)}^2.\end{array}$

表1~3列出了两种算法在两个测试问题上的迭代次数，测试$\theta =0,0.5,1$ 和$\delta =0.5,1.0,1.5,2.0,2.5$ 时的LM参数。我们选择$x_0=\left(-1,1,-1,1,\cdots ,-1,1\right)$ ，表1~3中的第三列表示不同的初始点，对于问题(i)，取初始点为$-10x_0$ ，$-x_0$ ，$0x_0$ ，$x_0$ ，$10x_0$ ，$100x_0$ ；对于问题(ii)，取初始点为$x_0$ ，$5x_0$ ，$10x_0$ ，$50x_0$ ，$100x_0$ ，$150x_0$ 。如果算法的迭代次数超过1000，则用符号“--”表示。

从表1~3中，我们可以看到，无论在测试问题(i)还是(ii)上，算法TLM的迭代次数几乎都比算法SLM的迭代次数少，说明本文提出的两步LM算法比单步LM算法的收敛速度更快。因此可以认为算法1在实际问题中可行且有效。

Table 1. Number of iterations at $\theta =0$

表1. $\theta =0$ 时的迭代次数

Problem	n	x0	δ = 0.5	δ = 1.0	δ = 1.5	δ = 2.0	δ = 2.5
			SLM/TLM	SLM/TLM	SLM/TLM	SLM/TLM	SLM/TLM
Rosenbrock	2	−10	4/3	4/3	6/4	6/5	8/10
		−1	2/1	2/1	3/2	3/2	4/2
		0	15/1	17/1	17/1	17/1	17/1
		1	22/2	25/2	26/18	24/22	27/22
		10	4/3	5/3	6/4	7/4	7/5
		100	6/5	8/5	8/6	11/8	15/10
	10	−10	4/3	5/4	6/5	8/11	9/11
		−1	2/1	3/2	4/2	4/2	4/3
		0	17/1	16/1	16/1	18/1	20/1
		1	27/2	22/22	26/17	18/21	22/15
		10	5/3	5/4	6/5	8/7	9/7
		100	7/5	8/6	9/7	12/9	20/13
	100	−10	4/3	6/4	7/6	8/6	11/12
		−1	2/1	3/2	4/3	5/3	6/3
		0	16/2	17/2	16/2	11/2	19/10
		1	27/19	22/22	24/18	23/14	21/16
		10	5/3	6/4	7/6	10/16	11/20
		100	7/5	8/6	10/10	16/14	28/25
Powell Singular	4	1	10/7	10/7	10/7	10/7	10/7
		5	12/9	12/9	12/9	12/9	13/9
		10	13/9	13/9	13/9	13/10	15/11
		50	15/11	15/11	15/11	17/12	20/15
		100	16/12	16/12	16/12	19/14	23/18
		150	17/12	17/12	17/12	20/14	24/19
	100	1	11/8	11/8	11/8	11/8	11/8
		5	13/9	13/9	13/9	13/10	16/12
		10	14/10	14/10	14/10	15/11	18/14
		50	16/12	16/12	16/12	20/15	24/19
		100	17/12	17/12	18/13	22/16	27/21
		150	18/13	18/13	18/13	23/17	32/24
	200	1	11/8	11/8	11/8	11/8	11/8
		5	13/9	13/9	13/9	14/10	16/12
		10	14/10	14/10	14/10	16/11	19/14
		50	16/12	16/12	17/12	20/15	25/20
		100	17/12	17/12	18/13	22/17	30/23
		150	18/13	18/13	19/13	23/18	39/28

Table 2. Number of iterations at $\theta =0.5$

表2. $\theta =0.5$ 时的迭代次数

Problem	n	x0	δ = 0.5	δ = 1.0	δ = 1.5	δ = 2.0	δ = 2.5
			SLM/TLM	SLM/TLM	SLM/TLM	SLM/TLM	SLM/TLM
Rosenbrock	2	−10	4/3	6/5	8/7	11/9	16/16
		−1	2/1	4/2	4/3	5/3	7/4
		0	17/1	16/1	21/1	18/1	23/1
		1	18/2	23/2	27/22	26/23	30/17
	10	10	5/3	6/5	8/5	11/8	34/13
		100	7/5	9/7	14/10	140/29	--/--
		−10	4/3	6/5	8/7	12/12	25/19
		−1	3/2	4/2	4/3	6/3	8/6
		0	19/1	15/2	16/2	18/2	29/2
		1	24/2	20/22	26/18	27/17	27/26
		10	5/3	6/5	9/7	12/10	24/16
		100	7/5	9/7	16/12	224/78	--/--
	100	−10	5/3	7/6	9/7	14/11	158/92
		−1	3/2	4/3	6/4	7/5	11/7
		0	16/2	14/2	16/3	20/3	12/12
		1	30/19	30/20	19/18	25/16	33/15
		10	5/4	7/5	9/8	16/15	108/59
		100	8/6	10/7	23/17	--/686	--/--
Powell Singular	4	1	10/7	10/7	10/7	10/7	11/8
		5	12/9	12/9	13/9	15/12	19/15
		10	13/9	13/9	14/10	18/14	24/19
		50	15/11	15/11	19/15	28/22	--/--
		100	16/12	17/12	22/17	87/52	--/--
		150	17/12	17/12	23/18	334/176	--/--
	100	1	11/8	11/8	11/8	12/9	14/11
		5	13/9	13/9	14/11	19/15	25/20
		10	14/10	14/10	17/12	22/17	148/82
		50	16/12	16/12	22/17	121/69	--/--
		100	17/12	18/13	24/19	--/777	--/--
		150	18/13	18/13	25/20	--/--	--/--
	200	1	11/8	11/8	11/8	12/9	15/12
		5	13/9	13/9	15/11	19/15	29/22
		10	14/10	14/10	17/13	22/18	318/168
		50	16/12	17/12	22/17	216/117	--/--
		100	17/12	18/13	25/19	--/--	--/--
		150	18/13	19/13	26/21	--/--	--/--

Table 3. Number of iterations at $\theta =1$

表3. $\theta =1$ 时的迭代次数

Problem	n	x0	δ = 0.5	δ = 1.0	δ = 1.5	δ = 2.0	δ = 2.5
			SLM/TLM	SLM/TLM	SLM/TLM	SLM/TLM	SLM/TLM
Rosenbrock	2	−10	4/3	6/5	9/6	11/10	20/17
		−1	2/2	4/2	4/3	6/4	7/4
		0	16/1	18/1	18/1	22/1	33/1
		1	22/2	26/2	21/22	39/17	36/26
		10	5/3	6/5	8/6	13/9	18/15
		100	7/5	9/7	16/12	109/41	--/--
	10	−10	4/3	6/5	9/8	12/11	37/27
		−1	3/2	4/2	5/3	6/4	8/6
		0	15/2	19/2	23/2	23/2	19/2
		1	25/2	29/17	27/18	27/15	39/23
		10	5/4	7/5	9/7	13/10	29/19
		100	8/6	10/7	18/14	382/166	--/--
	100	−10	5/4	7/6	11/9	18/14	295/156
		−1	3/2	4/3	7/4	9/6	11/8
		0	16/2	20/2	16/3	16/3	25/11
		1	25/21	29/18	26/21	23/19	38/22
		10	6/4	7/6	10/8	16/13	192/100
		100	8/6	10/8	20/77	--/--	--/--
Powell Singular	4	1	10/7	10/7	10/7	10/7	11/8
		5	12/9	12/9	13/9	16/12	20/16
		10	13/9	13/9	15/11	19/15	27/21
		50	15/11	16/11	20/15	33/24	--/--
		100	16/12	17/12	22/17	148/83	--/--
		150	17/12	17/12	23/18	639/329	--/--
	100	1	11/8	11/8	11/8	12/9	15/11
		5	13/9	13/9	15/11	19/15	28/21
		10	14/10	14/10	17/13	22/18	272/144
		50	16/12	17/12	22/17	216/117	--/--
		100	17/12	18/13	25/19	--/--	--/--
		150	18/13	18/13	26/21	--/--	--/--
	200	1	11/8	11/8	11/8	13/10	16/12
		5	13/9	13/9	15/11	20/16	36/26
		10	14/10	14/10	18/13	23/18	612/315
		50	16/12	17/12	23/18	405/211	--/--
		100	17/12	18/13	25/20	--/--	--/--
		150	18/13	19/14	27/21	--/--	--/--

5. 总结

本文通过采用一种较为通用的LM参数并结合非单调信赖域方法，提出了改进型的两步Levenberg-Marquardt方法。我们已经证明，新的两步LM方法具有全局收敛性，并通过与单步LM方法的数值实验进行对比，得出新的两步LM方法在解决实际问题上高效且有前途。