考虑下面的非线性互补问题:求向量$x\in R^n$, 使得

$\begin{equation}\label{1} x\ge 0, \quad F(x)\ge 0, \quad x^TF(x)=0, \end{equation}$

(1.1)

其中连续可微函数$F:R^{n}\to R^n$.

非线性互补问题在许多实际部门有着广泛的应用, 如力学、工程、经济、交通等.正因为非线性互补问题的重要性, 因此当前已有不少关于求解互补问题的数值算法, 如信赖域法, 内点与非内点法, 连续化方法, 投影收缩法, 优化方法等.而Levenberg-Marquardt是求解互补问题的重要算法之一, 在实际中有着重要应用。本文将采用Levenberg-Marquardt方法求解$P_0$非线性互补问题.首先利用FB函数$\phi(a, b)=a+b-\sqrt{(a^2+b^2)}$将非线性互补问题(1.1) 转化为下面的方程组:

$\begin{equation}\label{2} \Phi(x)=\left(\begin{array}{c} \phi(x_1, F_1(x)) \\ \vdots \\ \phi(x_n, F_n(x)) \end{array}\right). \end{equation}$

(1.2)

引入参数$\tau$对FB函数进行光滑逼近:

$\begin{equation}\label{3} \phi_{\tau}(a, b)=a+b-\sqrt{a^2+b^2+2\tau^2}. \end{equation}$

(1.3)

从而有如下方程组:

$\begin{equation}\label{4} \Phi_{\tau}(x)=\left(\begin{array}{c} \phi_{\tau}(x_1, F_1(x)) \\ \vdots \\ \phi_{\tau}(x_n, F_n(x)) \end{array}\right). \end{equation}$

(1.4)

定义价值函数:

$\begin{equation}\label{5} \theta(x)=\|\Phi(x)\|^2, \quad \theta_{\tau}(x)=\|\Phi_{\tau}(x)\|^2.\end{equation}$

(1.5)

目前有大量关于Levenberg-Marquardt方法的文章, 如文献[2]通过引入两个NCP函数(FB函数和minimum函数)将广义线性互补问题转化为非线性方程组$\Phi$, 同时引入一个参数$\tau$得到$\Phi$的一个光滑逼近$\Phi_{\tau}$, 提出了一个求解该方程组的光滑算法.算法具有全局性和在严格互补条件下获得该算法的超线性.文献[3]基于FB函数, 引入一个参数将非线性互补问题转化为光滑方程组, 在这个方程组中参数被视为一个独立的变量, 提出了一个解$P_0$非线性互补问题的光滑Levenberg-Marquardt方法, 该算法是全局收敛的, 在严格互补条件或者非奇异条件满足情况下利用局部误差界都可得到算法的超线性; 文献[4]针对非线性方程组将文献[5]中关于信赖域半径选择的技巧与文献[6]中关于LM方法的参数更新技巧结合起来获得一个结合信赖域技术的修正Levenberg-Marquardt方法, 所提算法有全局性, 同时在局部误差界条件下获得该算法的局部收敛性.本文基文献[1]的算法思想提出一个解$P_0$非线性互补问题的光滑Levenberg-Marquardt方法, 采用新的LM参数$\mu_k=\alpha_k\|\nabla\Phi_{\tau_k}^T\Phi_{\tau_k} \|^\delta$, 而$\alpha_k$的更新则采用文献[6]所给信赖域技术.所提算法具有全局性, 不需要严格互补条件的假设, 而是采用较弱的局部误差界条件来获得该算法的局部收敛性.

本节提出一个解$P_0$-NCP的光滑Levenberg-Marquardt方法.首先设

$ Q_k(d_k)=\frac{1}{2}\|\Phi_{\tau_k}(x_k)+\nabla\Phi_{\tau_k}^Td_k\|^2, \quad \hbox{pred}=Q_k(0)-Q_k(d_k), \\[3pt] \hbox{ared}=\frac{1}{2}\|\Phi_{\tau_k}(x_k)\|^2-\frac{1}{2}\|\Phi_{\tau_k}(x_{k+1})\|^2. $

算法1 (光滑Levenberg-Marquardt方法)

步0 给定$x_0\in R^n$, $b_0\in(0, \frac{1}{2})$, $a>0$, $b_0<b_1\le1$, $\eta<1, \mu<1$, $\alpha_0>m>0$, $\delta\in(0, 2)$, $\delta_2<1\le\delta_1$, $\beta_0=\|\Phi(x_0)\|$, $\tau_0=\dfrac{\mu}{2\sqrt{2n}}\beta_0$, $k:=0$.

步1 求解下面的方程组

$\begin{equation}\label{6} \left(\nabla\Phi_{\tau_k}^T\nabla\Phi_{\tau_k}+\alpha_k \|\nabla\Phi_{\tau_k}^T\Phi_{\tau_k}\|^\delta I\right)d= -\nabla\Phi_{\tau_k}^T\Phi_{\tau_k} \end{equation}$

(2.1)

获得$d_k$满足

$\hbox{pred}\geq a\|\Phi_{\tau_k}\|\|d_k\|.$

步2  计算$r_k=\dfrac{\mathrm{ared}}{\mbox{pred}}$.若$r_k\geq b_0$, 那么$x_{k+1}=x_k+d_k$, 否则$x_{k+1}=x_k$.更新$\alpha_{k+1}$,

$\alpha_{k+1}=\left\{\begin{array}{ll} \delta_1\alpha_k, \hbox{若} rk<b_0, \\ \alpha_k, \hbox{若} rk\in[b_0, b_1], \\ \max\{\delta_2\alpha_k, m\}, \hbox{若} rk>b_1. \end{array} \right.$

步3 若$\|\nabla\theta(x_{k+1})\|=0$, 停算.

步4若

$ \|\Phi(x_{k+1})\|\le\max\{\eta\beta_k, \mu^{-1}\|\Phi(x_{k+1})-\Phi_{\tau_k}(x_{k+1})\|\}. $

令$\beta_{k+1}=\|\Phi(x^{k+1})\|$, 并选取$\tau_{k+1}$满足

$ 0<\tau_{k+1}<\min\Big\{\frac{\mu}{4\sqrt{n}}\beta_{k+1}, \frac{\tau_k}{2}\Big\}. $

否则置$\beta_{k+1}:=\beta_{k}$, $\tau_{k+1}:=\tau_{k}$, 转步5.

步5  令$k:=k+1$, 转步1.

注1  定义集合$S$ :

$ S=\{0\}\cup\{k|\|\Phi(x_k)\|\le\max\{\eta\beta_{k-1}, \mu^{-1}\|\Phi(x_k)-\Phi_{\tau_{k-1}}(x^k)\|\}\}. $

本节将对算法1的全局收敛性进行分析.

定义1  设函数$F:R^{n}\to R^n$对$\forall x, y\in R^n, x\neq y$, 有$ \max \limits_{x_i\neq y_i}(x_i-y_i)(F(x_i)-F(y_i))\geq0, $则称$F$为$P_0$函数.

引理1  对$\forall x\in R^n$, 以及$\tau\geq0$, 都有$\|\Phi(x_k)-\Phi_{\tau}(x_k)\|\leq\sqrt{2n}\tau$.

证由题意有

$ \|\Phi(x_k)-\Phi_{\tau}(x_k)\| =\Bigg(\sum\limits^{n}_{i=1}\Big[\varphi(x_i, F_i(x))-\varphi_\tau(x_i, F_i(x))\Big]^2\Bigg)^{1/2}\\[6pt] =\Bigg(\sum\limits^{n}_{i=1}\Big[x_i+F_i(x)-\sqrt{x_i^2+(F_i(x))^2}-\Big(x_i+F_i(x)-\sqrt{x_i^2+(F_i(x))^2+2\tau^2}\Big)\Big]^2\Bigg)^{1/2}\\[6pt] =\Bigg(\sum\limits^{n}_{i=1}\Big[\sqrt{x_i^2+(F_i(x))^2+2\tau^2}-\sqrt{x_i^2+(F_i(x))^2} )\Big]^2\Bigg)^{1/2}\\[6pt] = \Bigg(\sum\limits^{n}_{i=1} \Big[\frac{2\tau^2}{\sqrt{x_i^2+(F_i(x))^2+2\tau^2}-\sqrt{x_i^2+(F_i(x))^2}}\Big]^2\Bigg)^{1/2}\\[6pt] \leq \Bigg(\sum\limits^{n}_{i=1} \Big(\frac{2\tau^2}{\sqrt{2\tau^2}}\Big)^2\Bigg)^{1/2}=\sqrt{2n}\tau. $

引理2 ^[7]  对$\forall k\in S$, 都有$\|\Phi(x_k)-\Phi_{\tau_k}(x_k)\|\leq\mu\|\Phi(x_k)\|$.

注2  引理2意味着$\forall k\in S$, 有$\|\Phi_{\tau_k}(x_k)\|\neq0$.并且当$\nabla\Phi_{\tau_k}(x_k)\neq0$时有$d_k\neq0$.

引理3^[7] 如果$F$为$P_0$函数, 那么对$\forall k \in S, \tau>0, $有$\nabla\Phi_{\tau_k}(x_k)$是非奇异的.

引理4  记水平集$L_0=\{x\in R^n\mid \theta(x_k)\leq(1+\mu)\theta(x_0)\}, $序列$\{x_k\}$由算法1产生, 若$F$为$P_0$函数, 那么$\{ x_k\}\subseteq L_0$.

证 类似于文献[1]命题4.1的证明过程, 立即可得引理4的结论.

定理1 如果$F$为$P_0$函数, 那么算法1是适定的.

证 由算法步2知, 要证明算法1的适定性, 只需证明$Q_k(0)-Q_k(d_k)>0$.

反证法:假定对于$j\in S$, 使得$Q_j(0)-Q_j(d_j)=0$, 即

$\begin{equation*} -\nabla\theta_{\tau_j}(x_j)^Td_j-\frac{1}{2}d_j^T\nabla\Phi_{\tau_j}^T(x_j) \nabla\Phi_{\tau_j}(x_j)d_j=0. \end{equation*}$

这就意味着$d_j=0$是以上方程的一个解, 从而由(2.1) 式有$-\nabla\Phi_{\tau_j}^T(x_j)\Phi_{\tau_j}(x_j)=0$, 但这与由引理2的注2和由引理3所得的$-\nabla\Phi_{\tau_j}^T(x_j)\Phi_{\tau_j}(x_j)\neq0$相矛盾.故命题成立.

引理5 ^[8]  对$\forall k$, 假设$d_k \in R^n$是(2.1) 式的解.那么

$\begin{equation}\label{7} \hbox{pred}\geq \frac{1}{2}\parallel \nabla\theta_{\tau_k}(x_k)\parallel \min\{ \|d_k\|, \frac{\|\nabla\theta_{\tau_k}\|}{\|\nabla\Phi_{\tau_k}^T\nabla\Phi_{\tau_k}\|} \}. \end{equation}$

(3.1)

定理2  设序列$\{x_k\}$由算法1产生, 如果$F$为$P_0$函数并且由算法1所产生的序列存在聚点, 那么集合是无限的且$ \lim\limits_{k\rightarrow \infty }\tau_k=0, $ $ \lim\limits_{k\rightarrow \infty}\Phi_{\tau_k}(x_k)=0, $ $\lim\limits_{k\rightarrow \infty}\Phi(x_k)=0 . $

证 首先利用反证法证明集合$S$无限的.假定集合$S$有限的, 设集合$S$中最大的数记为$\bar{k}$, 那么$\forall k\geq\bar{k}$, 有$\tau_k=\tau_{\bar{k}}$以及$\beta_k=\beta_{\bar{k}}$.记$ \bar{\tau}=\tau_{\bar{k}}$, $ \bar{\beta}=\beta_{\bar{k}}$以及$q(x)=\Phi(x)-\Phi_{\bar{\tau}}(x), $那么$\forall k\geq\bar{k}$, 有

$\begin{equation}\label{8} \parallel\Phi(x_k)\parallel>\max\{\eta\bar{\beta}, \mu^{-1} \|q(x_k)\|\} \end{equation}$

(3.2)

和

$\begin{equation}\label{9} \Phi(x_k)=q(x_k)+\Phi_{\bar{\tau}}(x_k). \end{equation}$

(3.3)

下面用反证法证明:序列$\{x_k\}$至少存在一个聚点$\bar{x}\subseteq L_0$使得

$\begin{equation}\label{10} \nabla\theta_{\bar{\tau}}({\bar{x}})=0. \end{equation}$

(3.4)

若(3.4) 式不成立, 记$K:=\{k\in S|r_k\geq b_0\}$, 那么由$\theta(x)$是连续可微的, 那么存在$ \varepsilon_1, \varepsilon_2>0, $有

$\begin{equation}\label{11} \|\nabla \theta_{\bar{\tau}}(x_k)\|>\varepsilon_1, \parallel \nabla \Phi_{\bar{\tau}}^T\nabla\Phi_{\bar{\tau}} \parallel ＜ \varepsilon_2, \forall k\in K. \end{equation}$

(3.5)

由$r_k\geq b_0, \forall k\in K, $有

$\begin{eqnarray} \nonumber \theta_{\bar{\tau}}(x_{k})-\theta_{\bar{\tau}}(x_{k+1}) \geq b_0 \hbox{pred} \nonumber\\[4pt] \geq \dfrac{1}{2}b_0\|\nabla \theta_{\bar{\tau}}(x_k)\| \min\Big\{\|d_k\|, \frac{\|\nabla\theta_{\bar{\tau}}(x_k)\|} {\|\nabla\Phi_{\bar{\tau}}^T(x_k)\Phi_{\bar{\tau}}(x_k)\|}\Big\} \nonumber\\[4pt] \geq \frac{1}{2}b_0 \varepsilon_1 \min\Big\{ \|d_k\|, \frac{\varepsilon_1}{\varepsilon_2} \Big\}. \label{12} \end{eqnarray}$

(3.6)

由于$\{\theta_{\bar{\tau}}(x_k)\}$是减的, 以及由引理4知其是有界的, 故$\{\theta_{\bar{\tau}}(x_k)\}$是收敛的.那么由(3.6) 式有

$\begin{eqnarray} \nonumber \frac{1}{2}b_0\varepsilon_1 \min\{ \|d_k\|, \frac{\varepsilon_1}{\varepsilon_2} \} \leq \sum \limits_{k\in K} \Big[\theta_{\bar{\tau}}(x_k)-\theta_{\bar{\tau}}(x_{k+1})\Big]\nonumber \\ \leq\sum \limits^{\infty}_{k=1} \Big[\theta_{\bar{\tau}}(x_k)-\theta_{\bar{\tau}}(x_{k+1})\Big]\nonumber \\ ＜ \infty. \label{13} \end{eqnarray}$

(3.7)

那么由引理2, 引理3和(3.7) 式知$\{d\}_{k\in K}\rightarrow0$, 由于(2.1) 式有$d=-\dfrac{\nabla\Phi_{\bar{\tau}}^T\Phi_{\bar{\tau}}} {\nabla\Phi_{\bar{\tau}}^T\nabla\Phi_{\bar{\tau}}+\alpha_k \| \nabla\Phi_{\bar{\tau}}^T\Phi_{\bar{\tau}} \|^\delta I}, $从而

$\begin{equation}\label{14} \{ \alpha_k\}_{k\in K} \rightarrow \infty \end{equation}$

(3.8)

另一方面, 由于$\theta_{\bar{\tau}}(x_k)$是连续可微的, 那么

$\begin{equation}\label{15} \theta_{\bar{\tau}}(x_k+d_k) =\theta_{\bar{\tau}}(x_k)+\nabla \theta_{\bar{\tau}} (\omega_k)^Td_k, (\omega_k=x_k+\lambda_kd_k, \lambda_k\in (0, 1)). \end{equation}$

(3.9)

由引理5, (3.5), (3.6), (3.9) 式以及$\hbox{Cauchy-Schwarz}$不等式有

$\begin{eqnarray} \nonumber \Big| r_k-1 \Big| = \Big|\dfrac{ \theta_{\bar{\tau}}(x_k)- \theta_{\bar{\tau}}(x_{k+1})+Q_k(x_k)-Q_k(0)} {Q_k(0)-Q_k(x_k)} \Big|\nonumber\\ = \Big|\dfrac{ \theta_{\bar{\tau}}(x_k)- \theta_{\bar{\tau}}(x_{k+1})+\nabla\theta_{\bar{\tau}}(x_k)^Td_k +\frac{1}{2}d_k^T\nabla\Phi_{\bar{\tau}}^T(x_k)\Phi_{\bar{\tau}}(x_k)d_k } {Q_k(0)-Q_k(x_k)}\Big|\nonumber\\ \leq \Big| \dfrac{ \theta_{\bar{\tau}}(x_k)- \theta_{\bar{\tau}}(x_{k})-\nabla\theta_{\bar{\tau}}(\omega_k)^Td_k +\nabla\theta_{\bar{\tau}}(x_k)^Td_k +\dfrac{1}{2}d_k^T\nabla\Phi_{\bar{\tau}}^T(x_k)\Phi_{\bar{\tau}}(x_k)d_k } {\dfrac{1}{2}\varepsilon_1\min\{ \| d_k\|, \dfrac{\varepsilon_1}{\varepsilon_2} \}} \Big| \nonumber\\ \leq \dfrac{2}{\varepsilon_1\|d_k\|}\Big(\Big| \nabla\theta_{\bar{\tau}}(x_k)^Td_k-\nabla\theta_{\bar{\tau}}(\omega_k)^Td_k +\frac{1}{2}d_k^T\nabla\Phi_{\bar{\tau}}^T(x_k)\Phi_{\bar{\tau}}(x_k)d_k \Big|\Big)\nonumber\\ \leq \dfrac{2}{\varepsilon_1\|d_k\|}\Big(\Big| \nabla\theta_{\bar{\tau}}(x_k)^Td_k-\nabla\theta_{\bar{\tau}}(\omega_k)^Td_k \Big| + \Big| \dfrac{1}{2}d_k^T\nabla\Phi_{\bar{\tau}}^T(x_k)\Phi_{\bar{\tau}}(x_k)d_k \Big|\Big)\nonumber\\ \leq \frac{2}{\varepsilon_1\|d_k\|}\Big(\| \nabla\theta_{\bar{\tau}}(x_k)-\nabla\theta_{\bar{\tau}}(\omega_k) \| \|d_k\| + \frac{1}{2}\|d_k\|^2 \varepsilon_2\Big) \nonumber\\ \leq \dfrac{2}{\varepsilon_1}\Big(\| \nabla\theta_{\bar{\tau}}(x_k)-\nabla\theta_{\bar{\tau}}(\omega_k) \|+\dfrac{1}{2}\|d_k\| \varepsilon_2\Big).\label{16} \end{eqnarray}$

(3.10)

由于$ \{ \omega_k \}_{k\in K}\rightarrow \bar{x}$, 当$k\in K$充分大式(3.10) 式是趋向于零的.即$r_k\rightarrow 1(k\in K)$.因此由算法1步2中$\alpha_k$的取值知存在常数$N>m$, 使对充分大$k\in K$有

$\begin{equation}\label{17} \alpha_k ＜N . \end{equation}$

(3.11)

而(3.8) 与(3.11) 式矛盾.从而(3.4) 式是成立的.

因此由引理1和(3.4) 式有$\{ \theta_{\bar{\tau}}(x_k)\}\rightarrow \theta_{\bar{\tau}}(\bar{x})=0, $那么存在$\hat{k}\geq\bar{k}$, 有$k\geq\hat{k}, k\in K$,

$ \| \Phi_{\bar{\tau}} \| \leq (1-\mu)\eta\bar{\beta}.$

对于$k\geq \hat{k}, k\in K$, 由(3.2), (3.3) 式有

$\begin{equation}\label{18} \| \Phi_{\bar{\tau}}(x_k)\|\leq (1-\mu)\|\Phi(x_k)\|\leq (1-\mu) (\|q(x_k)\|+\|\Phi_{\bar{\tau}}(x_k)\|), \end{equation}$

(3.12)

由(3.12) 式得到

$\begin{equation}\label{19} \| \Phi_{\bar{\tau}}(x_k)\|\leq(\mu^{-1}-1)\|q(x_k)\|, \end{equation}$

(3.13)

而由(3.3), (3.13) 式有

$\begin{eqnarray} \nonumber \|\Phi(x_k)\|=\| q(x_k)+\Phi_{\bar{\tau}}(x_k)\|\nonumber\\ \leq\|q(x_k)\|+\|\Phi_{\bar{\tau}}(x_k)\|\nonumber\\ \leq\|q(x_k)\|+(\mu^{-1}-1)\|q(x_k)\|\nonumber\\ \leq\mu^{-1}\|q(x_k)\|.\label{20} \end{eqnarray}$

(3.14)

故(3.2) 与(3.14) 式矛盾, 所以集合$S$是无限的.

由算法1的步4关于$\tau_k$的更新准则知$\{ \tau_k\} \rightarrow 0, k\in \infty$.由引理4可推得

$\begin{equation}\label{21} \|\Phi(x_k)\|\leq p_j(1+\mu )\|\Phi(x_0)\|, k_j\leq k\leq k_{j+1}, \end{equation}$

(3.15)

其中$p_j=\max\{\frac{1}{2}, \eta\}$.

由于集合$S$是无限的, 那么由引理2和(3.15) 式有$\lim\limits_{k\rightarrow \infty}\Phi(x_k)=0, \lim\limits_{k\rightarrow \infty} \Phi_{\tau_k}(x_k)=0.$

定理3 ^[1]  如果$F$为$P_0$函数, 序列$\{x_k\}$由算法1生成的, 那么其全部聚点都为$NCP(F)$的解.

求解$(\nabla\Phi_{\tau_k}^T\nabla\Phi_{\tau_k} +\alpha\|\nabla\Phi_{\tau_k}^T\nabla\Phi_{\tau_k}\|^\delta I) d=-\nabla\Phi_{\tau_k}^T\nabla\Phi_{\tau_k}$等价于求解以下最小问题的最优解

$\begin{equation}\label{22} \min\limits_{d\in R^n}\Psi(d), \end{equation}$

(4.1)

其中

$\begin{equation}\label{23} \Psi(d) =\frac{1}{2}\|\Phi_{\tau_k}(x_k)+\nabla\Phi_{\tau_k}^Td\|^2 +\frac{1}{2}\alpha_k\|\nabla\Phi_{\tau_k}^T\Phi_{\tau_k}\|^\delta \|d\|^2. \end{equation}$

(4.2)

定义2 ^[4]  设$M$是$R^n$上的子集, 并且满足$M\cap X \neq \emptyset$, 其中$X$是(1.4) 式的非空解集, 若存在常数$c>0$, 使得$\|\Phi_\tau(x)\|\geq c\hbox{dist}(x, X), \forall x\in M, $那么$ \Phi_\tau(x)$在$ M$内局部误差有界.

首先给出一些有用的假设.

假设A

(1) $\nabla\Phi_\tau(x_\ast)$是非奇异的, 如果$x_\ast$是由算法1产生的序列$\{x_k\}$的聚点.

(2) 问题(1.4) 的任意解$x_\ast\in X$, 存在$b>0, c>0$, 有

$\begin{equation}\label{24} \|\Phi_\tau(x)\|\geq c\hbox{dist}(x, X), \forall x\in M(x_\ast, b)\{x|\|x-x_\ast \| \leq b\}, \end{equation}$

(4.3)

则$\|\Phi_\tau(x)\|$在$M(x_\ast, b)$内有局部误差界.下面将给出算法1的局部收敛性分析, 首先以$\bar{x}_k$记为$x_k$到$X$距离最短的点, 也就是

$\begin{equation}\label{25} \|x_k-\bar{x}_k\|=\hbox{dist}(x_k, X), \bar{x}_k\in X. \end{equation}$

(4.4)

引理6 ^[3]   $\Phi _\tau(x)$是局部Lipschitz连续, 且是强半光滑的, 那么存在常数$L_1>0, L_2>0, x_1, x_2\in R^n$

$\begin{equation}\label{26} \|\Phi_\tau(x_1)-\Phi_\tau(x_2)\| \leq L_1\|x_1-x_2\|, \end{equation}$

(4.5)

$ \begin{equation}\label{27} \|\Phi_\tau(x_1)-\Phi_\tau(x_2)-V^T(x_1-x_2)\| \leq L_2\|x_1-x_2\|^2, \end{equation}$

(4.6)

其中$V\in\partial\Phi_\tau(x), \partial\Phi_\tau(x)$为Clarke通常意义下的Jacobian矩阵.

引理7 若假设A成立, 对充分大$k$, 存在常数$N, $有

$\begin{equation}\label{28} \alpha_k＜N. \end{equation}$

(4.7)

证 由算法1的步1有$\hbox{pred}\geq a\|\Phi_\tau\|\|d_k\|$, 从而由

$ \nonumber \Big| r_k-1 \Big| =\Big|\frac{\hbox{ared}}{\hbox{pred}}-1\Big|\nonumber\\ =\Big|\frac{\frac{1}{2}\|\Phi_{\tau_k}(x_k)+\nabla\Phi_{\tau_k}^T(x_k)d_k\|^2 -\frac{1}{2}\|\Phi_{\tau_k}(x_{k+1})\|^2}{\hbox{pred}}\Big|\nonumber\\ =\frac{\|\Phi_{\tau_k}(x_k)+\nabla\Phi_{\tau_k}^Td_k\|O(\|d_k\|^2)+O(\|d_k\|^4)}{\hbox{pred}}\nonumber\\ \leq\frac{\|\Phi_{\tau_k}\|O(\|d_k\|^2)+O(\|d_k\|^4)}{O(\|\Phi_{\tau_k}\|\|d_k\|)}\nonumber\\ =O(\|d_k\|)\rightarrow0. $

即有$r_k\rightarrow 1$.因此对充分大$k$, 由算法1步2中$\alpha_k$的取值知存在常数$N>m$, 有$\alpha_k <N.$

引理8 设假设A成立, 如果$x_k\in M(x_\ast, b)$, 那么存在常数$c_1>0$使得

$ c_1\|\bar{x}_k-x_k\|^\delta \leq \alpha_k \|\nabla \Phi_{\tau_k}^T\Phi_{\tau_k}\|^\delta\leq c_2\|\bar{x}_k-x_k\|^\delta. $

证 由引理6, 假设A的(2), (4.7) 式有

$ \begin{array}{rcl} \alpha_k \|\nabla \Phi_{\tau_k}^T(x_k)\Phi_{\tau_k}(x_k)\|^\delta \leq\alpha_k \|\nabla \Phi_{\tau_k}(x_k)\|^\delta \| \Phi_{\tau_k}(x_k)\|^\delta\\ \leq\alpha_k \|\nabla \Phi_{\tau_k}(x_k)\|^\delta \| \Phi_{\tau_k}(\bar{x}_k)-\Phi_{\tau_k}(x_k)\|^\delta\\ \leq\alpha_k \|\nabla \Phi_{\tau_k}(x_k)\|^\delta \|L_1(\bar{x}_k-x_k)\|^\delta\\ \leq_2\|\bar{x}_k-x_k\|^\delta, \end{array}$

其中$c_2=NL_1^{2\delta}.$右边的不等式得证.

下面证明左边的不等式成立.由

$ \nonumber \| \Phi_{\tau_k}(x_k)\|^2 = \Phi_{\tau_k}(x_k)^T \Phi_{\tau_k}(x_k)\\ = \Phi_{\tau_k}(x_k)^T (\Phi_{\tau_k}(\bar{x}_k)+\nabla\Phi_{\tau_k}(x_k)(x_k-\bar{x}_k))\\ + \Phi_{\tau_k}(x_k)^T ( \Phi_{\tau_k}(x_k)- \Phi_{\tau_k}(\bar{x}_k)-\nabla \Phi_{\tau_k}(x_k)(x_k-\bar{x}_k)), $

有

$ \Phi_{\tau_k}(x_k)^T\nabla \Phi_{\tau_k} (x_k)(x_k-\bar{x}_k)\\ =\|\Phi_{\tau_k}(x_k)\|^2- \Phi_{\tau_k}(x_k)^T( \Phi_{\tau_k}(x_k)- \Phi_{\tau_k}(\bar{x}_k)-\nabla \Phi_{\tau_k}(x_k)(x_k-\bar{x}_k)). $

由假设A和引理6, 有

$\|\nabla\Phi_{\tau_k}(x_k)^T\Phi_{\tau_k} (x_k)\| \|x_k-\bar{x}_k\|\geq c^2\|x_k-\bar{x}_k\|^2 -L_1L_2\|x_k-\bar{x}_k\|^3, $

从而有

$\|\nabla\Phi_{\tau_k}(x_k)^T\Phi_{\tau_k} (x_k)\| ^\delta \geq (c^2\|x_k-\bar{x}_k\| -L_1L_2\|x_k-\bar{x}_k\|^2)^\delta.$

由算法1步2中$\alpha_k$的取值知$\alpha_k\geq m, $于是

$\alpha_k\|\nabla\Phi_{\tau_k}(x_k)^T\Phi_{\tau_k} (x_k)\| ^\delta \geq m(c^2\|x_k-\bar{x}_k\| -L_1L_2\|x_k-\bar{x}_k\|^2)^\delta, $

即有

$\alpha_k\|\nabla\Phi_{\tau_k}(x_k)^T\Phi_{\tau_k} (x_k)\| ^\delta \geq m\|x_k-\bar{x}_k\|^\delta(c^2 -L_1L_2\|x_k-\bar{x}_k\|)^\delta.$

因此若$\|x_k-\bar{x}_k\|$充分小, 那么存在常数$c_1>0$, 使得

$\alpha_k\|\nabla\Phi_{\tau_k}(x_k)^T\Phi_{\tau_k} (x_k)\| ^\delta \geq c_1\|x_k-\bar{x}_k\|^\delta. $

引理9 若假设A成立, 设$x_{k+1}, x_k\in M(x_\ast, \frac{1}{2}b), $那么有

$\begin{equation}\label{29} \hbox{dist}(x_{k+1}, X)\leq c_3\hbox{dist}(x_k, X)^{\frac{2+\delta}{2}}. \end{equation}$

(4.8)

证 要证(4.8) 式成立, 首先要证明$\forall x_k\in M(x_\ast, \frac{1}{2}b), $存在$c_4>0, c_5>0$, 使以下不等式成立

$\begin{equation}\label{30} \|d_k\|\leq c_4 \hbox{dist}(x_k, X) \end{equation}$

(4.9)

及

$\begin{equation}\label{31} \| \Phi_{\tau_k}(x_k)d_k+\nabla \Phi_{\tau_k}(x_k)^Td_k\|\leq c_5 \hbox{dist}(x_k, X)^{\frac{2+\delta}{2}}. \end{equation}$

(4.10)

首先证明(4.9) 式成立.

$ \begin{equation}\label{32} \|\bar{x}_k-x_\ast\|\leq\|\bar{x}_k-x_k\|+\|x_\ast-x_k\| \leq\|x_\ast-x_k\|+\|x_\ast-x_k\|\leq b. \end{equation}$

(4.11)

由(4.11) 式以及$x_k\in M(x_\ast, \frac{1}{2}b)$得$\bar{x}_k\in M(x_\ast, b).$由(4.2) 式的凸性质知$d_k$是(4.1) 式全局最优解, 于是有

$\begin{equation}\label{33} \Psi(d_k)\leq\Psi(\bar{x}_k-x_k). \end{equation}$

(4.12)

那么由假设A的(2), 引理6, 引理8, (4.2), (4.9) 式有

$\begin{eqnarray} \nonumber \|d_k\|^2 \leq \frac{1}{\alpha_k\|\nabla \Phi_{\tau_k}^T\Phi_{\tau_k}\|^\delta}\Psi(d_k)\nonumber\\ \leq \frac{1}{\alpha_k\|\nabla \Phi_{\tau_k}^T\Phi_{\tau_k}\|^\delta}\Psi(\bar{x}_k-x_k)\nonumber\\ = \frac{1}{\alpha_k\|\nabla \Phi_{\tau_k}^T\Phi_{\tau_k}\|^\delta} \Big[\frac{1}{2}\|\Phi_{\tau_k}(x_k)+\nabla \Phi_{\tau_k}^T(\bar{x}_k-x_k)\|^2+ \frac{1}{2} \alpha_k\| \nabla\Phi_{\tau_k}^T\Phi_{\tau_k}\|^\delta \|\bar{x}_k-x_k\|^2\Big]\nonumber\\ \leq \frac{L_2^2}{2c_1\|\bar{x}_k-x_k\|^\delta}\|\bar{x}_k-x_k\|^4 +\frac{1}{2}\|\bar{x}_k-x_k\|^2\nonumber\\ \leq \frac{L_2^2}{2c_1} \|\bar{x}_k-x_k\|^{4-\delta}+\frac{1}{2}\|\bar{x}_k-x_k\|^2\nonumber\\ \leq \Big( \frac{L_2^2}{2c_1}+\frac{1}{2}\Big) \| \bar{x}_k-x_k \|^2, \label{34} \end{eqnarray}$

(4.13)

从而令

$c_4=\sqrt{\dfrac{L_2^2}{2c_1}+\dfrac{1}{2}}, $

即得(4.9) 式.

下面再证明(4.10) 式成立.事实上, 由(4.2) 式, 引理6, 引理8, 有

$\begin{eqnarray} \nonumber \|\Phi_{\tau_k}(x_k)+\nabla \Phi_{\tau_k}^T d_k\|^2 \leq \Psi(d_k)\leq\Psi(\bar{x}_k-x_k)\nonumber\\ \leq \frac{1}{2}\|\Phi_{\tau_k}(x_k)+\nabla \Phi_{\tau_k}^T(\bar{x}_k-x_k)\|^2+\frac{1}{2}\alpha_k \|\nabla\Phi_{\tau_k}^T\Phi_{\tau_k}\|^\delta\|\bar{x}_k-x_k\|^2\nonumber\\ \leq\frac{1}{2}L_2^2\|\bar{x}_k-x_k\|^4+\frac{1}{2}c_2\|\bar{x}_k-x_k\|^{2+\delta}\nonumber\\ \leq(\frac{1}{2}L_2^2+\frac{1}{2}c_2)\|\bar{x}_k-x_k\|^{2+\delta}, \label{35} \end{eqnarray}$

(4.14)

在上式中只需令

$c_5=\sqrt{\dfrac{1}{2}L_2^2+\dfrac{1}{2}c_2}, $

即得(4.10) 式成立.

以下证明本引理的结论.由假设A的(2), 引理6, (4.9), (4.10) 式有

$\begin{eqnarray} \nonumber \hbox{dist}(x_{k+1}, X) \leq \frac{1}{c}\| \Phi_\tau(x_{k+1}) \| =\frac{1}{c}\| \Phi_\tau(x_k+d_k)\|\nonumber\\ \leq \frac{1}{c}\| \Phi_{\tau_k}(x_k+d_k)-\Phi_{\tau_k}(x_k) -\nabla \Phi_{\tau_k}^Td_k\|+\frac{1}{c}\| \Phi_{\tau_k}(x_k)+ \nabla \Phi_{\tau_k}^Td_k\|\nonumber\\ \leq \frac{L_2}{c}\|d_k\|^2+\frac{c_5}{c}\hbox{dist}(x_k, X)^{\frac{2+\delta}{2}}\nonumber\\ \leq \frac{L_2c_4^2}{c}\hbox{dist}(x_k, X)^2+\frac{c_5}{c} \hbox{dist}(x_k, X)^{\frac{2+\delta}{2}}\nonumber\\ \leq\frac{L_2c_4^2(\frac{b}{2})^{\frac{2-\delta}{2}}}{c} \hbox{dist}(x_k, X)^{\frac{2+\delta}{2}}+\frac{c_5}{c} \hbox{dist}(x_k, X)^{\frac{2+\delta}{2}}\nonumber\\ \leq\frac{L_2c_4^2(\frac{b}{2})^{\frac{2-\delta}{2}}+c_5}{c} \hbox{dist}(x_k, X)^{\frac{2+\delta}{2}}\nonumber\\ :=c_3\hbox{dist}(x_k, X)^{\frac{2+\delta}{2}}, \nonumber \end{eqnarray}$

其中

$c_3=\dfrac{L_2c_4^2(\dfrac{b}{2})^{\frac{2-\delta}{2}}+c_5}{c}. $

定理4 在假设A成立的条件下,

(a)由算法1产生的序列$\{x_k\}$收敛于$x_\ast$.

(b)当$\delta\in (0, 2)$时, $\hbox{dist}(x_k, X)$收敛到0是超线性的, 当$\delta =2, \hbox{dist}(x_k, X)$收敛到0是二次的.

证   (a)由定理3和假设A的(1) 可知

$\begin{equation}\label{36} \{x_k\}\rightarrow x_\ast, x_\ast\in X. \end{equation}$

(4.15)

(b)不等式

$\begin{equation}\label{37} \hbox{dist}(x_k, X)\leq \hbox{dist}(x_k+d_k, X)+\|d_k\|. \end{equation}$

(4.16)

由(4.8) 和(4.16) 式有

$\begin{equation}\label{38} \hbox{dist}(x_k, X)\leq 2\|d_k\|. \end{equation}$

(4.17)

由(4.8), (4.9), (4.17) 式有

$\|d_{k+1}\|=O(\|d_k\|^{\frac{2+\delta}{2}}), $

那么

$\begin{equation*} \lim\limits_{k\rightarrow \infty}\frac{\|x_{k+1}-x_\ast\|} {\|x_{k}-x_\ast\|^{\frac{2+\delta}{2}}}= \lim\limits_{k\rightarrow \infty} \frac{\|\sum\limits_{l={k+1}}^\infty d_l\|} {\|\sum\limits_{l={k}}^\infty d_l\|^{\frac{2+\delta}{2}}} =\lim\limits_{k\rightarrow \infty}\frac{\|d_{k+1}\|} {\|d_{k}\|^{\frac{2+\delta}{2}}} \leq p \end{equation*}$

($p\geq0$是一个常数).

当$\delta \in(0, 2)$时, $\hbox{dist}(x_k, X)$收敛到0是超线性的.当$\delta=2$时, $\hbox{dist}(x_k, X)$收敛到0是二次的.

为了验证该算法的有效性, 本节将选取一些测试问题进行实验, 并与一般Levenberg-Marquart方法进行比较.这里的一般Levenberg-Marquart方法由文献[9]的算法3.6.4改进获得.记为ULM.程序的设计采用的是Matlab 7.0进行编译, 其中参数的选取为: $b_0=0.05, b_1=0.75, \alpha =0.01, m=10^{-3}, \delta=1, \delta_1=4, \delta_2=0.25, \eta=0.3, \mu=0.99.$

例1   (Kojima-Shindo问题)测试函数为

$ F(x)=\left\{\begin{array}{l} 3x_1^2+2x_1x_2+2x_2^2+x_3+3x_4-6, \\ 2x_1^2+x_1+x_2^2+3x_3+2x_4-2, \\ 3x_1^2+x_1x_2+2x_2^2+2x_3+3x_4-1, \\ x_1^2+3x_2^2+2x_3+3x_4-3, \end{array} \right. $

该问题有唯一解$(\frac{\sqrt{6}}{2}, 0, 0, 0.5)^T$.选取不同的初始点, 数值结果如下表.

例2

$ F(x)=\left\{\begin{array}{l} x_1-8, \\ x_2^3+x_2-x_3-3, \\ x_2+2x_3^3+x_3-3, \\ \end{array} \right. $

选取不同的初始点, 数值结果如下表.

上述数值结果表明, 采用新的LM参数并结合信赖域技术的光滑Levenberg-Marquart方法比一般的Levenberg-Marquart方法的计算效率更高.