基于Armijo非单调线搜索的修正LM方法

A Modified Levenberg-Marquardt Method with an Armijo Nonmonotone Line Search

摘要: 近年来，非线性方程组问题越来越多地出现在科学与工程领域中。Levenberg-Marquardt (LM)方法是解决此问题的有效方法。为了避免信赖域步不可取的情况，文章提出一种基于非单调线搜索技术的修正LM方法，同样保证了算法在局部误差界的条件下达到全局收敛，并在文末附上了相应的数值结果，证明算法是有效的。

Abstract: Recently, systems of nonlinear equations have wide application in fields of science and engineering. The Levenberg-Marquardt method is an effective method to solve this problem. In this paper, we propose a modified Levenberg-Marquardt method by using a nonmonotone line search technique for the nonlinear equations system to avoid the situation where a trust step is not acceptable. The global and cubic convergence of this new method is also preserved under the local error bound con-dition. Finally, some numerical results are reported, which show that the algorithm is efficient.

1. 前言

考虑如下非线性方程组：

$F\left(x\right)=0$ (1)

其中 $F:R^n\to R^n$ 是连续可微的。文章中，假设(1)的解集X非空，符号 $\Vert ·\Vert$ 指2-范数。

Levenberg-Marquardt方法(LM)是解决问题(1)的一种经典有效的方法。

为了进一步提高算法的收敛速度，范在文 [1] 中提出一种修正的LM方法。该算法结合信赖域技术，采用两步走的方式，每一次迭代过程中通过求解以下方程组来计算两个步长 $d_k^{LM}$ 和 $d_k^{MLM}$ ：

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

其中 $J_k=F^{\prime }\left(x_k\right)$ 是F在 $x_k$ 处的雅克比矩阵， $F_k=F\left(x_k\right)$ ${\lambda }_k={\mu }_k{\Vert F_k\Vert }^{\delta },\delta \in \left[1,2\right]$， ${\mu }_k>0$ 由信赖域技术更新， $y_k=x_k+d_k^{LM}$。该算法具有全局收敛性和三次收敛速度。但是算法中的搜索方向可能不是问题(1)的优化函数 ${\Vert F\left(x\right)\Vert }^2$ 的下降方向。在范文章的基础上，郭和黄 [2] 提出了新的非单调修正L-M方法。新算法在每次迭代步都引入校正步，使新的试探步更靠近Moore-Penrose步。Chen、Ma [3] 还提出了多步走的LM方法。何和马在文 [4] 中利用非单调搜索准则提出求解非线性方程组的修正LM算法(L-M算法)，该算法中，当试探步未被接受时，执行非单调线搜索来获取下一个迭代点。

周在文 [5] 中提出了一种新的非单调二阶Armijo线搜索方式，通过下式更新算法的步长因子：

${\Vert F\left(x_k+\alpha d_k+{\alpha }^2{\hat{d}}_k\right)\Vert }^2-{\Vert F_k\Vert }^2\le -{\sigma }_1{\alpha }^2{\Vert d_k\Vert }^2-{\sigma }_2{\alpha }^2{\Vert {\hat{d}}_k\Vert }^2-{\sigma }_3{\alpha }^2{\Vert F_k\Vert }^2+{\epsilon }_k{\Vert F_k\Vert }^2$

其中 $\left\{{\epsilon }_k\right\}$ 是给定的正数列，满足 ${\displaystyle \underset{k=0}{\overset{\infty }{\sum }}{\epsilon }_k}<\infty$。周 [4] 结合上述非单调线搜索，进一步修正了LM算法，同样

确保了算法在局部误差界的条件下具有全局收敛性，且有三次收敛速度。He、Ma和Fan [6] 在周 [5] 的基础上，结合平均值型线搜索提出一种修正LM方法，该方法同样具有全局收敛性以及三次收敛速度。

目前，还有许多其他方法 [7] [8] [9] 都是解决问题(1)的有效方法。

文章在文 [1]、文 [5] 和文 [6] 的基础上，结合Grippo L在文 [10] 中提出的Max型Armijo非单调线搜索，构造一种基于Armijo非单调线搜索的修正LM方法。

2. 算法及其全局收敛性

定义(1)的优化函数为 $f\left(x\right)={\Vert F\left(x\right)\Vert }^2$

假设1

a) 水平集 ${\Omega }_1=\left\{x|f\left(x\right)\le f\left(x_0\right)\right\}\subset \Omega$ 是有界闭集

b) $F\left(x\right)$ 和其雅可比矩阵 $J\left(x\right)$ 在水平集 ${\Omega }_1$ 上Lipschitz连续，即存在正常数L使得

$\Vert F\left(x\right)-F\left(y\right)\Vert \le L\Vert x-y\Vert ,\forall x,y\in {\Omega }_1,$ (6)

$\Vert J\left(x\right)-J\left(y\right)\Vert \le L\Vert x-y\Vert ,\forall x,y\in {\Omega }_1,$ (7)

由(6)易知 $\Vert J\left(x\right)\Vert \le L,\forall x\in {\Omega }_1$。

取 $J_k$ 的SVD分解为 $J_k=U\Sigma V^{\text{T}}$，其中U和V正交矩阵， $\Sigma$ 是一对角矩阵，其对角元素为 ${\sigma }_i\ge 0,i=1,\cdots ,n$，且 ${\sigma }_1\ge {\sigma }_2\ge {\sigma }_3\ge \cdots \ge {\sigma }_n$。由(7)知 ${\sigma }_1\le L$。

引理 1 设假设1成立，若存在 ${\tau }_1>0$ 使得 $\Vert F\left(x\right)\Vert \ge {\tau }_1,\forall x\in {\Omega }_1$，则存在常数 $C_1,C_2>0$ 使得下式成立

$F_k^{\text{T}}{J}_k{d}_k\le C_1{\Vert J_k^{\text{T}}{F}_k\Vert }^2$ (8)

$F^{\text{T}}\left(y_k\right)J_k{d}_k\le C_1{\Vert J_k^{\text{T}}{F}_k\Vert }^2$ (9)

$\Vert d_k\Vert \le C_2\Vert J_k^{\text{T}}{F}_k\Vert$ (10)

$\Vert {\hat{d}}_k\Vert \le C_2\Vert J_k^{\text{T}}F\left(y_k\right)\Vert$ (11)

证明：由 $\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)d_k=-J_k^{\text{T}}{F}_k$，可以得到

$\begin{array}{c}{F}_k^{\text{T}}{J}_k{d}_k=-\Vert F_k^{\text{T}}{J}_k{\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)}^{-1}{J}_k^{\text{T}}{F}_k\Vert \\ =-\Vert F_k^{\text{T}}{J}_{k}V{\left({\Sigma }^2+{\lambda }_{k}I\right)}^{-1}{V}^{\text{T}}{J}_k^{\text{T}}{F}_k\Vert \\ =-\Vert A_k^{\text{T}}{\left({\Sigma }^2+{\lambda }_{k}I\right)}^{-1}{A}_k\Vert \le -{\left({\sigma }_1^2+{\lambda }_k\right)}^{-1}\Vert A_k^{\text{T}}{A}_k\Vert \\ \le -{\left(L^2+\mu M\right)}^{-1}\Vert F_k^{\text{T}}{J}_k{J}_k^{\text{T}}{F}_k\Vert \triangleq -C_1{\Vert J_k^{\text{T}}{F}_k\Vert }^2\end{array}$

$\begin{array}{c}\Vert d_k\Vert =\Vert {\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)}^{-1}{J}_k^{\text{T}}{F}_k\Vert \le \Vert {\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)}^{-1}\Vert \Vert J_k^{\text{T}}{F}_k\Vert \\ \le {\lambda }_k^{-1}\Vert J_k^{\text{T}}{F}_k\Vert ={\left(\mu \Vert F_k\Vert \right)}^{-1}\Vert J_k^{\text{T}}{F}_k\Vert \\ \le {\left(\mu {\tau }_1\right)}^{-1}\Vert J_k^{\text{T}}{F}_k\Vert \triangleq C_2\Vert J_k^{\text{T}}{F}_k\Vert \end{array}$

其中 $C_1={\left(L^2+\mu M\right)}^{-1}$， $C_2={\left(\mu {\tau }_1\right)}^{-1}$， $A_k=V^{\text{T}}{F}_k^{\text{T}}{J}_k$。

同理，可以得到(9)和(11)。

引理 2 设 $\left\{x_k\right\}$ 是由算法1产生的序列，则总存在正常数使得下式成立

${\Vert F\left(x_k+\alpha d_k+{\alpha }^2{\hat{d}}_k\right)\Vert }^2\le \underset{0\le j\le m\left(k\right)}{\max }\left\{{\Vert F\left(x_{k-j}\right)\Vert }^2\right\}+{\sigma }_1{\alpha }^2{F}_k^{\text{T}}{J}_k{d}_k+{\sigma }_2{\alpha }^2{F}^{\text{T}}\left(y_k\right)J_k{\hat{d}}_k$

其中 $m\left(0\right)=0$， $0\le m\left(k\right)\le \min \left[m\left(k-1\right)+1,M_0\right]$， $k\ge 1$。

证明：用反证法证明。假设对 $\forall \alpha$， $0<\alpha \le 1$ 都有

${\Vert F\left(x_k+\alpha d_k+{\alpha }^2{\hat{d}}_k\right)\Vert }^2>\underset{0\le j\le m\left(k\right)}{\max }\left\{{\Vert F\left(x_{k-j}\right)\Vert }^2\right\}+{\sigma }_1{\alpha }^2{F}_k^{\text{T}}{J}_k{d}_k+{\sigma }_2{\alpha }^2{F}^{\text{T}}\left(y_k\right)J_k{\hat{d}}_k$

则有

${\Vert F\left(x_k+\alpha d_k+{\alpha }^2{\hat{d}}_k\right)\Vert }^2-{\Vert F\left(x_k\right)\Vert }^2>{\sigma }_1{\alpha }^2{F}_k^{\text{T}}{J}_k{d}_k+{\sigma }_2{\alpha }^2{F}^{\text{T}}\left(y_k\right)J_k{\hat{d}}_k$

对上式两边同除α，有

$\frac{{\Vert F\left(x_k+\alpha d_k+{\alpha }^2{\hat{d}}_k\right)\Vert }^2-{\Vert F\left(x_k\right)\Vert }^2}{\alpha }>{\sigma }_1\alpha F_k^{\text{T}}{J}_k{d}_k+{\sigma }_2\alpha F^{\text{T}}\left(y_k\right)J_k{\hat{d}}_k$

令 $\alpha \to 0^{+}$，由极限的性质有

$2F_k^{\text{T}}{J}_k{d}_k\ge 0$

然而，由于 ${\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)}^{-1}$ 是正定的， $d_k=-{\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)}^{-1}{J}_k^{\text{T}}{F}_k$，则有 $F_k^{\text{T}}{J}_k{d}_k<0$

显然，这是矛盾的，则原命题成立。这也意味着算法中所使用的线搜索技术是可行的。

定理1 设假设1成立。则算法1将有限终止，或满足 $\underset{k\to \infty }{\lim \inf }\Vert J_k^{\text{T}}{F}_k\Vert =0$。

证明：用反证法证明。

假设 $\exists \bar{k}>0$， $\tau >0$，s.t. $\forall k\ge \bar{k}$， $\Vert J_k^{\text{T}}{F}_k\Vert \ge \tau$。则 $\exists {\tau }_1>0$，s.t. $\Vert F_k\Vert \ge {\tau }_1$。

设 $l\left(k\right)$ 是满足下式的整数

$\{\begin{array}{l}k-m\left(k\right)\le l\left(k\right)\le k\\ f\left(x_{l\left(k\right)}\right)={\Vert F\left(x_{l\left(k\right)}\right)\Vert }^2=\underset{0\le j\le m\left(k\right)}{\max }\left[f\left(x_{k-j}\right)\right]\end{array}$

由 $m\left(k+1\right)\le m\left(k\right)+1$，知

$\begin{array}{c}f\left(x_{l\left(k+1\right)}\right)=\underset{0\le j\le m\left(k+1\right)}{\max }\left[f\left(x_{k+1-j}\right)\right]\\ \le \underset{0\le j\le m\left(k\right)+1}{\max }\left[f\left(x_{k+1-j}\right)\right]\\ =\underset{0\le j\le m\left(k\right)+1}{\max }\underset{k}{\max }\left[f\left(x_{k+1}\right),f\left(x_{k-j}\right)\right]\\ =\underset{k}{\max }\left[f\left(x_{k+1}\right),f\left(x_{l\left(k\right)}\right)\right]=f\left(x_{l(\; k\; )}\right)\end{array}$

即 $\left\{f\left(x_{l\left(k\right)}\right)\right\}$ 非增。对 $\forall k>M$

$\begin{array}{c}f\left(x_{l\left(k\right)}\right)=f\left(x_{l\left(k\right)-1}+{\alpha }_{l\left(k\right)-1}{d}_{l\left(k\right)-1}+{\alpha }_{l\left(k\right)-1}^2{\hat{d}}_{l\left(k\right)-1}\right)\\ \le \underset{0\le j\le m\left(l\left(k\right)-1\right)}{\max }\left[f\left(x_{l\left(k\right)-1-j}\right)\right]+{\sigma }_1{\alpha }_{l\left(k\right)-1}^2{F}_{l\left(k\right)-1}^{\text{T}}{J}_{l\left(k\right)-1}{d}_{l\left(k\right)-1}\\ +{\sigma }_2{\alpha }_{l\left(k\right)-1}^2{F}^{\text{T}}\left(x_{l\left(k\right)-1}+d_{l\left(k\right)-1}\right)J_{l\left(k\right)-1}{\hat{d}}_{l\left(k\right)-1}\\ =f\left(x_{l\left(l\left(k\right)-1\right)}\right)+{\sigma }_1{\alpha }_{l\left(k\right)-1}^2{F}_{l\left(k\right)-1}^{\text{T}}{J}_{l\left(k\right)-1}{d}_{l\left(k\right)-1}+{\sigma }_2{\alpha }_{l\left(k\right)-1}^2{F}^{\text{T}}\left(x_{l\left(k\right)-1}+d_{l\left(k\right)-1}\right)J_{l\left(k\right)-1}{\hat{d}}_{l\left(k\right)-1}\end{array}$

定义上式为(12)。

因为 $F\left(x\right)$ 在 ${\Omega }_1$ 上Lipschitz连续，则 $F\left(x\right)$ 在 ${\Omega }_1$ 上一致连续，则有

$\underset{k\to \infty }{\lim }f\left(x_{l\left(k\right)}\right)=\underset{k\to \infty }{\lim }f\left(x_{l\left(l\left(k\right)-1\right)}\right)$ (13)

由(11)以及(12)，可知

$\underset{k\to \infty }{\lim }\left({\alpha }_{l\left(k\right)-1}^2{F}_{l\left(k\right)-1}^{\text{T}}{J}_{l\left(k\right)-1}{d}_{l\left(k\right)-1}+{\alpha }_{l\left(k\right)-1}^2{F}^{\text{T}}\left(x_{l\left(k\right)-1}+d_{l\left(k\right)-1}\right)J_{l\left(k\right)-1}{\hat{d}}_{l\left(k\right)-1}\right)=0$

由于上式的两加数都非正，则有

$\underset{k\to \infty }{\lim }{\alpha }_{l\left(k\right)-1}^2{F}_{l\left(k\right)-1}^{\text{T}}{J}_{l\left(k\right)-1}{d}_{l\left(k\right)-1}=0$

$\underset{k\to \infty }{\lim }{\alpha }_{l\left(k\right)-1}^2{F}^{\text{T}}\left(x_{l\left(k\right)-1}+d_{l\left(k\right)-1}\right)J_{l\left(k\right)-1}{\hat{d}}_{l\left(k\right)-1}=0$

由引理1知， ${\alpha }_k^2{F}_k^{\text{T}}{J}_k{d}_k\le -C_1{\alpha }_k^2{\Vert J_k^{\text{T}}{F}_k\Vert }^2\le -\frac{C_1}{C_2^2}{\alpha }_k^2{\Vert d_k\Vert }^2$，则有

$\underset{k\to \infty }{\lim }{\alpha }_{l\left(k\right)-1}^2{\Vert J_k^{\text{T}}{F}_k\Vert }^2=0$， $\underset{k\to \infty }{\lim }{\alpha }_{l\left(k\right)-1}^2{\Vert d_{l\left(k\right)-1}\Vert }^2=0$

又因为 ${\alpha }_k>0$， $\Vert d_k\Vert >0$，则有

$\underset{k\to \infty }{\lim }{\alpha }_{l\left(k\right)-1}\Vert J_k^{\text{T}}{F}_k\Vert =0$ (14)

$\underset{k\to \infty }{\lim }{\alpha }_{l\left(k\right)-1}\Vert d_{l\left(k\right)-1}\Vert =0$ (15)

同理，可以得到

$\underset{k\to \infty }{\lim }{\alpha }_{l\left(k\right)-1}\Vert {\hat{d}}_{l\left(k\right)-1}\Vert =0$ (16)

接下来证明 $\underset{k\to \infty }{\lim }{\alpha }_k\Vert d_k\Vert =0$

取 $\hat{l}\left(k\right)=l\left(k+M+2\right)$。

首先证明 $\forall j\ge 1$，下式都成立

$\underset{k\to \infty }{\lim }{\alpha }_{\hat{l}\left(k\right)-j}\Vert d_{\hat{l}\left(k\right)-j}\Vert =0$ (17)

$\underset{k\to \infty }{\lim }{\alpha }_{\hat{l}\left(k\right)-j}\Vert {\hat{d}}_{\hat{l}\left(k\right)-j}\Vert =0$ (18)

$\underset{k\to \infty }{\lim }{\alpha }_{\hat{l}\left(k\right)-j}\Vert J_{\hat{l}\left(k\right)-j}^{\text{T}}{F}_{\hat{l}\left(k\right)-j}\Vert =0$ (19)

$\underset{k\to \infty }{\lim }f\left(x_{\hat{l}\left(k\right)-j}\right)=\underset{k\to \infty }{\lim }f\left(x_{l\left(k\right)}\right)$ (20)

用数学归纳法证明这些等式。

当 $j=1$ 时，因为 $\left\{\hat{l}\left(k\right)\right\}\subset \left\{l\left(k\right)\right\}$，由(14)、(15)、(16)，易得到(17)、(18)以及(19)成立。等式

$\underset{k\to \infty }{\lim }{\alpha }_{\hat{l}\left(k\right)-1}\Vert d_{\hat{l}\left(k\right)-1}\Vert =0$ 也意味着 $\Vert x_{\hat{l}\left(k\right)}-x_{\hat{l}\left(x\right)-1}\Vert \to 0$。由 $F\left(x\right)$ 的一致连续性有(20)成立。

下面，假设对某一 $j\ge 1$，(17)至(20)成立。

则对 $j+1$，由(12)知

$\begin{array}{c}f\left(x_{\hat{l}\left(k\right)-j}\right)\le f\left(x_{l\left(\hat{l}\left(k\right)-j-1\right)}\right)+{\sigma }_1{\alpha }_{\hat{l}\left(k\right)-j-1}^2{F}_{\hat{l}\left(k\right)-j-1}^{\text{T}}{J}_{\hat{l}\left(k\right)-j-1}{d}_{\hat{l}\left(k\right)-j-1}\\ +{\sigma }_2{\alpha }_{\hat{l}\left(k\right)-j-1}^2{F}^{\text{T}}\left(x_{\hat{l}\left(k\right)-j-1}+d_{\hat{l}\left(k\right)-j-1}\right)J_{\hat{l}\left(k\right)-j-1}{\hat{d}}_{\hat{l}\left(k\right)-j-1}\end{array}$

由上述假设，对上式令 $k\to \infty$，则有

$\underset{k\to \infty }{\lim }{\alpha }_{\hat{l}\left(k\right)-j-1}^2{F}_{\hat{l}\left(k\right)-j-1}^{\text{T}}{J}_{\hat{l}\left(k\right)-j-1}{d}_{\hat{l}\left(k\right)-j-1}=0$

$\underset{k\to \infty }{\lim }{\alpha }_{\hat{l}\left(k\right)-j-1}^2{F}^{\text{T}}\left(x_{\hat{l}\left(k\right)-j-1}+d_{\hat{l}\left(k\right)-j-1}\right)J_{\hat{l}\left(k\right)-j-1}{\hat{d}}_{\hat{l}\left(k\right)-j}=0$

同(15)、(16)的证明，可得到

$\underset{k\to \infty }{\lim }{\alpha }_{\hat{l}\left(k\right)-j-1}\Vert J_{\hat{l}\left(k\right)-j-1}^{\text{T}}{F}_{\hat{l}\left(k\right)-j-1}\Vert =0$， $\underset{k\to \infty }{\lim }{\alpha }_{\hat{l}\left(k\right)-j-1}\Vert d_{\hat{l}\left(k\right)-j-1}\Vert =0$， $\underset{k\to \infty }{\lim }{\alpha }_{\hat{l}\left(k\right)-j-1}\Vert {\hat{d}}_{\hat{l}\left(k\right)-j-1}\Vert =0$

同样有

$\Vert x_{\hat{l}\left(k\right)-j}-x_{\hat{l}\left(x\right)-j-1}\Vert \to 0$， $\underset{k\to \infty }{\lim }f\left(x_{\hat{l}\left(k\right)-j-1}\right)=\underset{k\to \infty }{\lim }f\left(x_{\hat{l}\left(k\right)-j}\right)=\underset{k\to \infty }{\lim }f\left(x_{l(\; k\; )}\right)$

即(17)至(20)对 $j\ge 1$ 成立。

由 $l\left(k\right)$ 以及 $\hat{l}\left(k\right)$ 的定义知 $\hat{l}\left(k\right)-k-1\le M+1$，所以 ${\displaystyle \underset{j=1}{\overset{\hat{l}\left(k\right)-k-1}{\sum }}{\alpha }_{\hat{l}\left(k\right)-j}{d}_{\hat{l}\left(k\right)-j}}$ 是有限项和。

由(16)、(17) 以及

$x_{\hat{l}\left(k\right)}=x_{k+1}+{\displaystyle \underset{j=1}{\overset{\hat{l}\left(k\right)-k-1}{\sum }}{\alpha }_{\hat{l}\left(k\right)-j}{d}_{\hat{l}\left(k\right)-j}}$

有 $\underset{k\to \infty }{\lim }\Vert x_{k+1}-x_{\hat{l}\left(k\right)}\Vert =0$。

这也意味着

$\underset{k\to \infty }{\lim }f\left(x_{k+1}\right)=\underset{k\to \infty }{\lim }f\left(x_k\right)=\underset{k\to \infty }{\lim }f\left(x_{\hat{l}\left(k\right)}\right)=\underset{k\to \infty }{\lim }f\left(x_{l\left(k\right)}\right)$ (21)

由(11)知

$f\left(x_{k+1}\right)\le f\left(x_{l\left(k\right)}\right)+{\sigma }_1{\alpha }_k^2{F}_k^{\text{T}}{J}_k{d}_k+{\sigma }_2{\alpha }_k^2{F}^{\text{T}}\left(x_k+d_k\right)J_k{\hat{d}}_k$

不等式两边令 $k\to \infty$，由(21)有

$\underset{k\to \infty }{\lim }{\alpha }_k^2{F}_k^{\text{T}}{J}_k{d}_k=0$

$\underset{k\to \infty }{\lim }{\alpha }_k^2{F}^{\text{T}}\left(x_k+{\alpha }_k{d}_k\right)J_k{\hat{d}}_k=0$

同样的方法有

$\underset{k\to \infty }{\lim }{\alpha }_k\Vert d_k\Vert =0$， $\underset{k\to \infty }{\lim }{\alpha }_k\Vert J_k^{\text{T}}{F}_k\Vert =0$

又由于 $\Vert J_k^{\text{T}}{F}_k\Vert \ge \tau >0$，则有 $\underset{k\to \infty }{\lim }{\alpha }_k=0$

由 $J_k$ 的SVD分解，可得到

$\Vert {\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)}^{-1}\Vert =\Vert V{\left({\Sigma }^2+{\lambda }_{k}I\right)}^{-1}{V}^{\text{T}}\Vert =\underset{i}{\max }{\left({\sigma }_i^2+{\lambda }_k\right)}^{-1}\le {\lambda }_k^{-1}$

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

$\begin{array}{c}\Vert {\hat{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\right)\Vert +\Vert {\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)}^{-1}{J}_k^{\text{T}}{F}_k\Vert \\ \le L^2{\lambda }_k^{-1}\Vert d_k\Vert +\Vert d_k\Vert \le \left(1+L^2{\mu }^{-1}{\tau }_1^{-1}\right)\Vert d_k\Vert \end{array}$

若 $\underset{k\to \infty }{\lim }\Vert d_k\Vert =0$，由于 $0\le \Vert J_k^{\text{T}}{F}_k\Vert \le \Vert J_k^{\text{T}}{J}_k+{\lambda }_{k}I\Vert \Vert d_k\Vert \le \left(L^2+\mu M\right)\Vert d_k\Vert$

则有 $\underset{k\to \infty }{\lim }\inf \Vert J_k^{\text{T}}{F}_k\Vert =0$

这与假设矛盾，所以存在常数 ${\tau }_2>0$ 使得 $\underset{k\to \infty }{\lim }\inf \Vert d_k\Vert \ge {\tau }_2$

令 ${\bar{\alpha }}_k={\alpha }_k{r}^{-1}$，由 ${\alpha }_k$ 的定义知

$\begin{array}{c}{\Vert F\left(x_k+{\bar{\alpha }}_k{d}_k+{\bar{\alpha }}_k^2{\hat{d}}_k\right)\Vert }^2>\underset{j}{\max }{\Vert F\left(x_{k-j}\right)\Vert }^2+{\sigma }_1{\bar{\alpha }}_k^2{F}_k^{\text{T}}{J}_k{d}_k+{\sigma }_2{\bar{\alpha }}_k^2{F}^{\text{T}}\left(y_k\right)J_k{\hat{d}}_k\\ \ge {\Vert F_k\Vert }^2+{\sigma }_1{\bar{\alpha }}_k^2{F}_k^{\text{T}}{J}_k{d}_k+{\sigma }_2{\bar{\alpha }}_k^2{F}^{\text{T}}\left(y_k\right)J_k{\hat{d}}_k\end{array}$

即 ${\bar{\alpha }}_k^2\left({\sigma }_1{F}_k^{\text{T}}{J}_k{d}_k+{\sigma }_2{F}^{\text{T}}\left(y_k\right)J_k{\hat{d}}_k\right)<{\Vert F\left(x_k+{\bar{\alpha }}_k{d}_k+{\bar{\alpha }}_k^2{\hat{d}}_k\right)\Vert }^2-{\Vert F_k\Vert }^2$

$\begin{array}{l}\Vert F\left(x_k+{\bar{\alpha }}_k{d}_k+{\bar{\alpha }}_k^2{\hat{d}}_k\right)\Vert -{\Vert F_k\Vert }^2\\ =2F_k^{\text{T}}\left(F\left(x_k+{\bar{\alpha }}_k{d}_k+{\bar{\alpha }}_k^2{\hat{d}}_k\right)-F_k\right)+{\Vert F\left(x_k+{\bar{\alpha }}_k{d}_k+{\bar{\alpha }}_k^2{\hat{d}}_k\right)-F_k\Vert }^2\\ \le 2F_k^{\text{T}}\left(F\left(x_k+{\bar{\alpha }}_k{d}_k+{\bar{\alpha }}_k^2{\hat{d}}_k\right)-F_k\right)+L^2{\bar{\alpha }}_k^2{\left(\Vert d_k\Vert +\Vert {\hat{d}}_k\Vert \right)}^2\\ \le 2F_k^{\text{T}}\left(F\left(x_k+{\bar{\alpha }}_k{d}_k+{\bar{\alpha }}_k^2{\hat{d}}_k\right)-F_k\right)+L^2{\bar{\alpha }}_k^2\left(2+L^2{\mu }^{-1}{\tau }_1^{-1}\right){\Vert d_k\Vert }^2\end{array}$

此外，

$\begin{array}{l}{F}_k^{\text{T}}\left(F\left(x_k+{\bar{\alpha }}_k{d}_k+{\bar{\alpha }}_k^2{\hat{d}}_k\right)-F_k\right)\\ =F_k^{\text{T}}\left(F\left(x_k+{\bar{\alpha }}_k{d}_k+{\bar{\alpha }}_k^2{\hat{d}}_k\right)-F\left(x_k+{\bar{\alpha }}_k{d}_k\right)\right)+F_k^{\text{T}}\left(F\left(x_k+{\bar{\alpha }}_k{d}_k\right)-F_k\right)\\ \le \Vert F_k\Vert \Vert F\left(x_k+{\bar{\alpha }}_k{d}_k+{\bar{\alpha }}_k^2{\hat{d}}_k\right)-F\left(x_k+{\bar{\alpha }}_k{d}_k\right)\Vert +{\bar{\alpha }}_k{F}_k^{\text{T}}{J}_k{d}_k+F_k^{\text{T}}{\displaystyle {\int }_0^1\left(J\left(x_k+t{\bar{\alpha }}_k{d}_k\right)-J_k\right){\bar{\alpha }}_k{d}_k\text{d}t}\\ \le LM{\bar{\alpha }}_k^2\Vert {\hat{d}}_k\Vert -{\bar{\alpha }}_k{d}_k^{\text{T}}\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)d_k+LM{\bar{\alpha }}_k^2{\Vert d_k\Vert }^2\\ \le \left(2+L^2{\mu }^{-1}{\tau }_1^{-1}\right)LM{\bar{\alpha }}_k^2{\Vert d_k\Vert }^2-{\bar{\alpha }}_k{d}_k^{\text{T}}\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)d_k\end{array}$

综上所述，有

$\begin{array}{c}{\bar{\alpha }}_k>\frac{-d_k^{\text{T}}\left(J_k^{\text{T}}{J}_k+{\lambda }_{k}I\right)d_k}{{\sigma }_1{F}_k^{\text{T}}{J}_k{d}_k+{\sigma }_2{F}^{\text{T}}\left(y_k\right)J_k{\hat{d}}_k-\left(2+L^2{\mu }^{-1}{\tau }_1^{-1}\right)LM\Vert d_k\Vert }\\ \ge \frac{{\lambda }_k{d}_k^{\text{T}}{d}_k}{C_1{\sigma }_1{\Vert J_k^{\text{T}}{F}_k\Vert }^2+C_1{\sigma }_1{\Vert J_k^{\text{T}}F\left(y_k\right)\Vert }^2+\left(2+L^2{\mu }^{-1}{\tau }_1^{-1}\right)LM\Vert d_k\Vert }\\ \ge \frac{\mu {\tau }_1{\tau }_2^2}{L^2{M}^2\left(C_1{\sigma }_1+C_1{\sigma }_1\right)+\left(2+L^2{\mu }^{-1}{\tau }_1^{-1}\right)L^2}\end{array}$ (22)

又 ${\bar{\alpha }}_k\in \left\{{\alpha }_k\right\}$，(22)与 $\underset{k\to \infty }{\lim }{\alpha }_k=0$ 矛盾。

所以，假设不成立，原命题成立。即

$\underset{k\to \infty }{\lim }\inf \Vert J_k^{\text{T}}{F}_k\Vert =0$

3. 数值结果

为了验证算法１的有效性，该部分进行了数值试验，并与文 [5] [6] 的算法进行了比较，结果列于表1中。

· 文 [6] 中修正LM算法(表中记为LM1)的参数选为： $\mu ={10}^{-6}$， $\epsilon =0.01$， $\gamma =0.5$，

${\kappa }_1={\kappa }_2={\sigma }_1={\sigma }_2={\sigma }_3=0.005$， ${\eta }_k\equiv 0.5$。

· 文 [5] 中修正LM算法(表中记为LM2)的参数选为： ${\sigma }_1={\sigma }_2={\sigma }_3=0.05$， $\rho =0.8$， $r=0.5$， $\mu ={10}^{-6}$，

${\epsilon }_k=\frac{{0.5}^k}{10}$。

· 算法1的参数选为 ${\sigma }_1={\sigma }_2=0.02$， $\rho =0.8$， $r=0.2$， $\mu ={10}^{-6}$， $M_0=1$

如果 $\Vert J_k^{\text{T}}{F}_k\Vert \le {10}^{-4}$ 或者迭代次数 $k>500$，则终止算法。算法的测试问题是对文 [11] 中的问题改编得到的。选择不同长度得初始点 $x_0={\left(1,-1,1,-1,\cdots ,1,-1\right)}^{\text{T}}$，测试函数为

$\hat{F}\left(x\right)=F\left(x\right)-J\left(x^{\ast }\right)A{\left(A^{\text{T}}A\right)}^{-1}{A}^{\text{T}}\left(x-x^{\ast }\right)$

其中 $A\in R^{n\times 1}$， $A^{\text{T}}=\left(1,1,\cdots ,1\right)$， $F\left(x\right)$ 是文 [11] 中非奇异标准测试函数， $x^{\ast }$ 是其根， $J\left(x^{\ast }\right)$ 是 $F\left(x\right)$ 在 $x^{\ast }$ 处的雅可比函数。显然， $\hat{F}\left(x^{\ast }\right)=0$， $\hat{J}\left(x^{\ast }\right)=J\left(x^{\ast }\right)\left(1-A{\left(A^{\text{T}}A\right)}^{-1}{A}^{\text{T}}\right)$ 的秩为n − 1。

表1中，“NF”和“NJ”分别代表函数、其雅可比函数的计算量，“NF + NJ × n”表示总计算量。如果算法迭代100(n + 1)次仍然无法找到解，用符合“--”表示。

Table 1. The numerical results

表1. 数值实验结果

4. 结束语

论文提出了一个基于Armijo非单调线搜索的修正LM方法，避免了传统LM算法中信赖域步不可被接受的情况。在适当的假设条件下，证明了该算法的全局收敛性。通过数值试验可以看出这个算法对于奇异值问题的求解是可行并有效的。