考虑无约束最优化问题

$\begin{eqnarray*} \min\limits_{x\in\bf R^{n}}f(x), \end{eqnarray*} $

(1.1)

其中 $f(x):\bf R^{n}\longrightarrow R $是二次连续可微函数.信赖域算法^[1-3]是求解问题(1.1) 的一个重要方法.其基本思想如下：在每一个迭代点, 试探步 $s_{k}$一般是子问题：

$\begin{eqnarray*} \min\limits_{\|s\|\leq\Delta_k}q_{k}(s)=g_{k}^{T}s+\frac{1}{2}s^{T}B_{k}s\end{eqnarray*} $

(1.2)

的解.其中 $g_{k}=\nabla f(x_{k})$, $ B_{k}\in R^{n\times n}$是 $f$在 $x_{k}$处的Hessian矩阵 $G(x)$或其近似矩阵, $\Delta_{k}$是信赖域半径, $\|\cdot\|$是 $R^{n}$中的Euclid范数.

众所周知, BFGS方法是拟牛顿方法中解问题(1.1) 的重要方法之一, 其校正公式是：

$ B_{k+1}=B_{k}-\frac{B_{k}s_{k}s_{k}^{T}B_{k}}{s_{k}^{T}B_{k}s_{k}}+\frac{y_{k}y_{k}^{T}}{s_{k}^{T}y_{k}}, $

(1.3)

其中 $s_{k}=x_{k+1}-x_{k}$, $y_{k}=g_{k+1}-g_{k}$, $g_{k+1}$和 $g_{k}$分别是 $f(x)$在 $x_{k+1}$和 $x_{k}$处的梯度值.文献[4-8]给出了一些修改的BFGS方法, 并分析了其收敛性.韦等^{[4, 5]}给出了新的公式 $(M_{3}BFGS)$：

$ B_{k+1}=B_{k}-\frac{B_{k}s_{k}s_{k}^{T}B_{k}}{s_{k}^{T}B_{k}s_{k}}+\frac{y_{k}^{l}y_{k}^{lT}}{s_{k}^{T}y_{k}^{l}}, $

其中 $y_{k}^{l}=y_{k}+A_{k}(2)s_{k}$, $y_{k}=g_{k+1}-g_{k}$, $A_{k}(2)=\frac{[2(f_{k}-f_{k+1})+(g_{k+1}+g_{k})^{T}s_{k}]I}{\|s_{k}\|^{2}}$, $s_{k}=x_{k+1}-x_{k}$.

受到上面公示的启发, 我们做如下假设:

$ B_{k+1}=B_{k}-\frac{B_{k}s_{k}s_{k}^{T}B_{k}}{s_{k}^{T}B_{k}s_{k}}+\frac{y_{k}^{*}y_{k}^{*T}}{s_{k}^{T}y_{k}^{*}}, $

(1.4)

其中 $y_{k}^{*}=\frac{\delta_{k}^{T}s_{k}}{|\delta_{k}^{T}s_{k}|}\delta_{k}$, $\delta_{k}=\theta y_{k}+(1-\theta)A_{k}(2)s_{k}$, $A_{k}(2)=\frac{[2(f_{k}-f_{k+1})+(g_{k+1}+g_{k})^{T}s_{k}]I}{\|s_{k}\|^{2}}$, $\theta\in[0,1]$, $y_{k}=g_{k+1}-g_{k}$.当且仅当 $s_{k}^{T}y_{k}>0$时, $B_{k+1}$继承 $B_{k}$的正定性.由 $y_{k}^{*}$的定义, 有

$ s_{k}^{T}y_{k}^{*}=\frac{(\delta_{k}^{T}s_{k})^{2}}{|\delta_{k}^{T}s_{k}|}=|\delta_{k}^{T}s_{k}|=|s_{k}^{T}B_{k}s_{k}+o(\|s_{k}\|^{2})|, $

若 $B_{k}$正定, 当 $\|s_{k}\|$充分小时, 则有

$ |s_{k}^{T}B_{k}s_{k}+o(\|s_{k}\|^{2})|>0, $

(1.5)

因此由公式（1.4）所得的 $B_{k+1}$总具有正定性.

本文在文献[4-10]的基础上, 给出了一个改进的带线搜索的信赖域方法, 其中 $B_{k}$由公式（1.4）产生.在一定条件下证明了该方法的全局收敛性和超线性收敛性.

算法1(MBFGS信赖域算法)

步0：给定常数 $\eta\in(0, 1)$, $\beta\in(0, 1)$, $r_{1}\in(0, 1)$, $\rho\in(0, 1)$, $\varepsilon>0$, $0<\Delta_{\min}<\Delta_{0}$, $r_{2}>1$, $x_{0}\in R^{n}$, $B_{0}\in R^{n\times n}$是对称正定矩阵, $k:=0$;

步1:计算 $g_{k}$, 若 $\|g_{k}\|\leq\varepsilon$, 则停; 否则, 转步2;

步2:求子问题(1.2) 的解 $s_{k}$;

步3:计算 $r_{k}=\frac{f(x_{k})-f(x_{k}+s_{k})}{q_{k}(0)-q_{k}(s_{k})}$, 若 $r_{k}\geq\eta$, 令 $\alpha_{k}=1$, $\Delta_{k}=\max\{r_{2}\Delta_{k}, \Delta_{\min}\}$, 转步5:否则, 转步4;

步4:若 $r_{k}<\eta$, 取 $\alpha_{k}$为 $\{1, \beta, \beta^{2}, \cdots\}$中满足下式的最大数:

$ \begin{equation} f(x_{k}+\alpha s_{k})-f_{k}\leq\rho\alpha g_{k}^{T}s_{k}. \end{equation} $

(2.1)

令 $\Delta_{k}=\max\{r_{1}\Delta_{k}, \Delta_{\min}\}$, 转步5;

步5:计算下一个迭代点 $x_{k+1}=x_{k}+\alpha_{k}s_{k}$, 利用公式(1.4) 修正 $B_{k+1}$, 令 $k:=k+1$, 转步1.

由于 $MBFGS$方法保证 $y_{k}^{*T}s_{k}>0$, 所以 $B_{k}$总是对称正定的.因此子问题(1.2) 有唯一解 $s_{k}$.由约束条件的最优性条件知, 存在乘子 $\alpha_{k}\geq0$, 使得

$ \begin{equation} \begin{cases} B_{k}s_{k}+\alpha_{k}s_{k}=-g_{k}, \\ \alpha_{k}(\|s_{k}\|-\Delta_{k})=0. \end{cases} \end{equation} $

(2.2)

由此式可知,

$ \alpha_{k}=\frac{-g_{k}^{T}s_{k}-s_{k}^{T}B_{k}s_{k}}{\|s_{k}\|^{2}}, $

(2.3)

即 $g_{k}^{T}s_{k}+s_{k}^{T}B_{k}s_{k}=-\alpha_{k}\|s_{k}\|^{2}\leq0$, 故有

$ q_{k}(s_{k})=g_{k}^{T}s_{k}+\frac{1}{2}s_{k}^{T}B_{k}s_{k} \leq\frac{1}{2}g_{k}^{T}s_{k}\leq-\frac{1}{2}s_{k}^{T}B_{k}s_{k}\leq0. $

(2.4)

为了证明算法1的全局收敛性, 我们给出如下假设条件：

假设(ⅰ):

A)水平集 $L(x_{0})=\{x|f(x)\leq f(x_{0})\}$有界;

B) $f$在 $L(x_{0})$上连续可微, 其导数满足Lipschitz条件, 即存在一个常数 $L>0$, 使得

$ \|g(x)-g(y)\|\leq L\|x-y\|, \forall x, y\in L(x_{0}). $

(3.1)

由线搜索和公式(2.4) 知, 该算法为下降算法.因此由假设A)知, 存在一个常数 $f^{*}$, 满足 $\lim\limits_{k\rightarrow\infty}f(x_{k})=f^{*}$.根据 $\{x_{k}\}$有界这一事实, 利用假设B), 知存在一个常数 $M_{0}$, 使得当 $k$充分大时, 有 $\|g_{k}\|\leq M_{0}$.

引理3.1^[5]  令序列 $B_{k}$由标准的BFGS公式产生, 其中 $B_{0}$是对称正定矩阵.若存在常数 $M>m>0$, 使得对所有 $k\geq0$均满足

$ \frac{y_{k}^{T}s_{k}}{\|s_{k}\|^{2}}\geq m, \frac{\|y_{k}\|^{2}}{y_{k}^{T}s_{k}}\leq M, $

(3.2)

则存在常数 $\mu_{i}>0, (i=1, 2, 3)$, 使得对 $\forall k\geq0$, 至少存在 $[\frac{k}{2}]$个 $i$值(其中 $i\leq k$)满足不等式

$ \mu_{1}\|s_{i}\|^{2}\leq s_{i}^{T}B_{i}s_{i}\leq\mu_{2}\|s_{i}\|^{2}, \|B_{i}s_{i}\|\leq\mu_{3}\|s_{i}\|. $

(3.3)

将 $[1, k]$中满足不等式(3.3) 的下标从小到大依次记为： $K_{k}=\{i_{1} < i_{2} < \cdots < i_{k}\}$, $ K=\bigcup\limits_{k=1}^\infty K_{k}$, 由引理2.1, 有

$ \mu_{1}\|s_{k}\|^{2}\leq s_{k}^{T}y_{k}\leq s_{k}^{T}G(\xi^{*})s_{k}\leq\mu_{2}\|s_{i}\|^{2}, $

(3.4)

其中 $\xi^{*}=x_{k}+\tau(x_{k+1}-x_{k}), \tau\in(0, 1)$.

引理3.2^[5]  对所有的试探步 $\alpha_{k}$满足

$ \alpha_{k}\geq\min\{1, \frac{(1-\rho)\beta}{L}\cdot\frac{s_{k}^{T}B_{k}s_{k}}{\|s_{k}\|^{2}}\}, $

(3.5)

其中 $L>0$是 $g$的Lipschitz常数.

定理3.1  设 $\{x_{k}\}$是由标准BFGS信赖域线搜索方法产生的点列, $f$二次连续可微且一致凸, 则序列 $\{x_{k}\}$收敛到(1.1) 的唯一解.

证  因为算法保证了 $\{f(x_{k})\}$单调递减, 且 $f$一致凸.所以只需证明

$\begin{eqnarray*} \lim\limits_{k\rightarrow\infty}\inf\|g_{k}\|=0.\end{eqnarray*} $

(3.6)

因为 $f$是一个二次连续可微的凸函数, 则存在常数 $M>0, m>0$, 使得对所有 $k$不等式(3.2) 成立.因此, 上面定义的指标集 $K$是无限集, 另外由式(3.3) 和式(3.4) 可得, 对所有 $i\in K$有

$ \alpha_{i}\geq\min\{1, (1-\rho)\beta\mu_{1}L^{-1}\}\equiv\overline{\alpha}>0. $

分两种情况讨论:

如果 $r_{k}\geq\eta$, 则对所有 $i\in K$, 有 $f(x_{i})-f(x_{i+1})\geq\eta(q_{k}(0)-q_{k}(s_{i}))\geq\frac{\mu_{1}\eta\|s_{i}\|^{2}}{2}.$

如果 $r_{k}<\eta$, 则 $f(x_{i})-f(x_{i+1})\geq-\rho\alpha_{i}g_{i}^{T}s_{i}\geq\rho\alpha_{i}s_{i}^{T}B_{i}s_{i}\geq\rho\overline{\alpha}\mu_{1}\|s_{i}\|^{2}, $所以存在一个常数 $\mu>0$, 对所有 $i\in K$满足

$ f(x_{i})-f(x_{i+1})\geq\mu\|s_{i}\|^{2}. $

(3.7)

又因为序列 $\{f(x_{k})\}$单调递减且有界, 所以极限存在.因此

$\begin{eqnarray*} \lim\limits_{i\in K, i\rightarrow\infty}\|s_{k}\|=0.\end{eqnarray*} $

(3.8)

否则 $\Delta_{i}\geq\Delta_{\min}$对所有 $i$成立, 对 $\forall i\in K$, $\|s_{i}\|<\Delta_{i}$对充分大 $i$成立.由式(2.2) 可得 $\alpha_{i}=0$, 由式(3.3) 知 $\|g_{i}\|=\|B_{i}s_{i}\|\leq\mu_{3}\|s_{i}\|$, 结合式(3.8) 得 $\lim\limits_{k\rightarrow\infty}\inf\|g_{k}\|=0$.

引理3.3^[4]  假设 $(x_{k}, x_{k+1}, g_{k+1}, s_{k})$由算法1产生, 则 $\forall k$都有

$ f(x_{k})=f(x_{k+1})+g_{k+1}^{T}(x_{k}-x_{k+1})+\frac{(x_{k}-x_{k+1})^{T}B_{k+1}(x_{k}-x_{k+1})}{2}. $

引理3.4  设 $\{x_{k}\}$是由算法1产生的点列, $B_{0}$是对称正定矩阵.若存在常数 $M>m>0$和 $P\geq0$使得不等式

$ m\|s_{k}\|^{2}\leq y_{k}^{*T}s_{k}\leq M\|s_{k}\|^{2}, \|y_{k}^{*}\|\leq P\|s_{k}\|, $

(3.9)

对所有 $k\geq0$成立, 则存在常数 $\mu_{i}>0, i=1, 2, 3$, 使得 $\forall k\geq0$, 至少 $[\frac{k}{2}]$个 $i$值满足式(3.3), 其中 $i\leq k$.

证  由 $y_{k}^{*}$的定义可知

$ \begin{eqnarray*} y_{k}^{*T}s_{k}&= & \frac{\delta_{k}^{T}s_{k}\cdot\delta_{k}^{T}s_{k}}{|\delta_{k}^{T}s_{k}|}=|\delta_{k}^{T}s_{k}|= |[\theta y_{k}+(1-\theta)A_{k}(2)s_{k}]^{T}s_{k}]|\\ &=&|\theta y_{k}^{T}s_{k}+(1-\theta)[2(f_{k}-f_{k+1})+(g_{k+1}+g_{k})^{T}s_{k}]|\\ &=&|g_{k+1}^{T}s_{k}+(1-2\theta)g_{k}^{T}s_{k}+(2-2\theta)(f_{k}-f_{k+1})|\\ &=&|(g_{k+1}^{T}s_{k}+f_{k}-f_{k+1})+(1-2\theta)(g_{k}^{T}s_{k}+f_{k}-f_{k+1})|\\ &=&|\frac{s_{k}^{T}G(\xi_{1})s_{k}}{2}+(2\theta-1)\frac{s_{k}^{T}G(\xi_{2})s_{k}}{2}|\\ &\leq&|\frac{s_{k}^{T}G(\xi_{1})s_{k}}{2}|+|(2\theta-1)\frac{s_{k}^{T}G(\xi_{2})s_{k}}{2}|\\ &\leq&(\frac{1}{2}+\frac{|(2\theta-1)|}{2}))|s_{k}^{T}G(\xi_{3})s_{k}|\\ &\leq & (\frac{1}{2}+\frac{|(2\theta-1)|}{2})\mu_{2}\|s_{k}\|^{2}, \end{eqnarray*} $

其中 $s_{k}^{T}G(\xi_{3})s_{k}=\max\{s_{k}^{T}G(\xi_{1})s_{k}, s_{k}^{T}G(\xi_{2})s_{k}\}$, $\xi_{1}=x_{k}+\theta_{1}(x_{k+1}-x_{k})$, $\xi_{2}=x_{k}+\theta_{2}(x_{k+1}-x_{k})$, $\xi_{3}=x_{k}+\theta_{3}(x_{k+1}-x_{k})$, $\theta_{1}, \theta_{2}, \theta_{3}\in(0, 1)$, 令 $M=(\frac{1}{2}+\frac{|(2\theta-1)|}{2})\mu_{2}$, 则 $y_{k}^{*T}s_{k}\leq M\|s_{k}\|^{2}$.

用同样的方法可以得到 $m\|s_{k}\|^{2}\leq y_{k}^{*T}s_{k}$, 得到式(3.9) 的第一个不等式.下证式(3.9) 的第二个不等式.

$ \begin{eqnarray*} \|y_{k}^{*}\|& =&\|\theta y_{k}+(1-\theta)A_{k}(2)s_{k}\| =\|\theta y_{k}+(1-\theta)\frac{2(f_{k}-f_{k+1})+(g_{k+1}+g_{k})^{T}s_{k}}{\|s_{k}\|^{2}}Is_{k}\|\\ & =&\|\theta y_{k}+(1-\theta)\frac{-2g_{k+1}^{T}s_{k}+s_{k}^{T}G(\xi_{4})s_{k}+g_{k+1}^{T}s_{k}+g_{k}^{T}s_{k}}{\|s_{k}\|^{2}}Is_{k}\|\\ & \leq &\theta\|y_{k}\|+(1-\theta)\|y_{k}\|+\frac{(1-\theta)|s_{k}^{T}G(\xi_{4})s_{k}|}{\|s_{k}\|} \leq\|y_{k}\|+(1-\theta)\mu_{2}\|s_{k}\|\\ &\leq&[L+(1-\theta)\mu_{2}]\|s_{k}\|, \end{eqnarray*} $

其中 $\xi_{4}=x_{k}+\theta_{4}(x_{k+1}-x_{k})$, $\theta_{4}\in(0, 1)$, 最后一个不等式利用了假设B).令 $P=L+(1-\theta)\mu_{2}$, 得到式(3.9) 的第二个不等式.类似引理3.1的证明, 得出引理3.4成立.

定理3.2  假设(ⅰ)成立, 点列 $\{x_{k}\}$由MBFGS信赖域算法产生, 则

$\begin{eqnarray*} \lim\limits_{k\rightarrow\infty}\inf\|g_{k}\|=0.\end{eqnarray*} $

(3.10)

证  由 $f(x_{k})$的下降性, 得 $\{x_{k}\}\subset L(x_{0})$有界.如果式(3.10) 非真, 则存在一个正常数 $\delta$, 对所有 $k$使 $\|g_{k}\|\geq\delta$成立.根据引理3.1, 类似定理3.1的证明, 推出矛盾, 从而结论成立.

为了证明算法1的超线性收敛性, 给出如下假设:

假设(ⅱ):

C)算法1产生的序列 $\{x_{k}\}$收敛到 $x^{*}$且 $\nabla^{2}f(x^{*})$正定;

D)函数 $f$在 $x^{*}$的邻域内二次连续可微, 且 $\nabla f(x^{*})=0$;

E) Hessian矩阵 $G(x)$在 $x^{*}$处Hölder连续, 即存在正常数 $\upsilon, \Psi$使得不等式

$ \|G(x)-G(x^{*})\|\leq\Psi\|x-x^{*}\|^{\upsilon}, $

(4.1)

对所有的 $x\in U(x^{*})$成立.

引理4.1^[4]  设点列 $\{x_{k}\}$由算法1产生, 若假设(ⅱ)成立, 则有

$\begin{eqnarray*} \lim\limits_{k\rightarrow\infty}\|A_{k}(2)\|=0. \end{eqnarray*} $

(4.2)

引理4.2^[4]  设点列 $\{x_{k}\}$由算法1产生, 若假设(ⅰ)和假设(ⅱ)成立, 则有

$\begin{eqnarray*} \sum\limits_{k=0}^{\infty}\|x_{k}-x^{*}\|<\infty, \sum\limits_{k=0}^{\infty}\phi_{k}<\infty, \sum\limits_{k=0}^{\infty}A_{k}(2)<\infty, \end{eqnarray*} $

其中 $\phi_{k}=\max\{\|x_{k}-x^{*}\|^{\upsilon}, \|x_{k+1}-x^{*}\|^{\upsilon}\}.$

引理4.3  设 $\{x_{k}\}$是算法1产生的点列, 定义 $Q=G(x^{*})^{-\frac{1}{2}}$, $H_{k}=B_{k}^{-1}$, 则存在正常数 $b_{i}, i=1, 2, 3, \cdots, 7$, 及 $\gamma\in(0, 1)$, 使得对充分大 $k$,

$ \begin{eqnarray} && \|B_{k+1}-G(x^{*})\|_{Q, F}\leq(1+b_{1}\phi_{k})\|B_{k}-G(x^{*})\|_{Q, F}+b_{2}\phi_{k}+b_{3}\|A_{k}(2)\|, \\ && \|H_{k+1}-G(x^{*})^{-1}\|_{Q^{-1}, F}\end{eqnarray} $

(4.3)

$\begin{eqnarray} &\leq&(\sqrt{1-\gamma\omega_{k}^{2}}+b_{4}\phi_{k}+b_{5}\|A_{k}(2)\|)\|H_{k}-G(x^{*})^{-1}\|_{Q^{-1}, F} +b_{6}\phi_{k}+b_{7}\|A_{k}(2)\|, \end{eqnarray} $

(4.4)

其中 $\|A\|_{Q, F}=\|Q^{T}AQ\|_{F}$, $\|.\|_{F}$是Frobenius范数. $\omega_{k}$由下式定义

$ \omega_{k}=\frac{\|Q^{-1}(H_{k}-G(x^{*})^{-1})y_{k}^{*}\|}{\|H_{k}-G(x^{*})^{-1}\|_{Q^{-1}, F}\|Qy_{k}^{*}\|}, $

(4.5)

且 $\{\|B_{k}\|\}_{F}$和 $\{\|H_{k}\|\}_{F}$有界.

证  由式(1.4) 得

$ \begin{eqnarray*} \|B_{k+1}-G(x^{*})\|_{Q, F} &=&\|B_{k}-G(x^{*})+\frac{B_{k}s_{k}s_{k}^{T}B_{k}}{s_{k}^{T}B_{k}s_{k}}+\frac{y_{k}^{*}y_{k}^{*T}}{s_{k}^{T}y_{k}^{*}}\|_{Q, F}\\ &\leq&\|B_{k}-G(x^{*})+\frac{B_{k}s_{k}s_{k}^{T}B_{k}}{s_{k}^{T}B_{k}s_{k}}+\frac{y_{k}y_{k}^{T}}{s_{k}^{T}y_{k}}\|_{Q, F} +\|\frac{y_{k}^{*}y_{k}^{*T}}{s_{k}^{T}y_{k}^{*}}-\frac{y_{k}y_{k}^{T}}{s_{k}^{T}y_{k}}\|_{Q, F}\\ &\leq&(1+b_{1}\phi_{k})\|B_{k}-G(x^{*})\|_{Q, F}+b_{2}\phi_{k}+\|\frac{y_{k}^{*}y_{k}^{*T}}{s_{k}^{T}y_{k}^{*}}-\frac{y_{k}y_{k}^{T}}{s_{k}^{T}y_{k}}\|_{Q, F}. \end{eqnarray*} $

最后一个不等式由文献[6]得到

$ \begin{eqnarray*} &&\|\frac{y_{k}^{*}y_{k}^{*T}}{s_{k}^{T}y_{k}^{*}}-\frac{y_{k}y_{k}^{T}}{s_{k}^{T}y_{k}}\|_{Q, F} =\|\frac{\delta_{k}\delta_{k}^{T}}{|\delta_{k}^{T}s_{k}|}-\frac{y_{k}y_{k}^{T}}{s_{k}^{T}y_{k}}\|_{Q, F}\\ &=&\|\frac{[\theta y_{k}+(1-\theta)A_{k}(2)s_{k}][\theta y_{k}+(1-\theta)A_{k}(2)s_{k}]^{T}}{s_{k}^{T} [\theta y_{k}+(1-\theta)A_{k}(2)s_{k}]}-\frac{y_{k}y_{k}^{T}}{s_{k}^{T}y_{k}}\|_{Q, F}\\ &=&\|\frac{s_{k}^{T}y_{k}[\theta y_{k}+(1-\theta)A_{k}(2)s_{k}][\theta y_{k}+(1-\theta)A_{k}(2)s_{k}]^{T}-s_{k}^{T}[\theta y_{k}+\\ (1-\theta)A_{k}(2)s_{k}]y_{k}y_{k}^{T}}{s_{k}^{T}y_{k}s_{k}^{T}[\theta y_{k}+(1-\theta)A_{k}(2)s_{k}]}\|_{Q, F}\\ &\leq&(1-\theta)\|A_{k}(2)\|\frac{\|2\theta s_{k}^{T}y_{k}y_{k}s_{k}^{T}\|_{Q, F}+\|s_{k}^{T}s_{k}y_{k}y_{k}^{T}\|_{Q, F} +\|(1-\theta)s_{k}^{T}y_{k}A_{k}(2)s_{k}s_{k}^{T}\|_{Q, F}}{s_{k}^{T}y_{k}s_{k}^{T}\delta_{k}}\\ &\leq&(1-\theta)\|A_{k}(2)\|\frac{(2\theta+1)\| s_{k}\|^{2}\|y_{k}\|^{2}\|Q\|_{F}^{2}+(1-\theta)\| s_{k}\|^{3}\|y_{k}\|\|A_{k}(2)\| \|Q\|_{F}^{2}}{s_{k}^{T}y_{k}s_{k}^{T}\delta_{k}}\\ &\leq&\|A_{k}(2)\|\frac{(1-\theta)\|Q\|_{F}^{2}[(2\theta+1)\|y_{k}\|^{2}+(1-\theta)\| s_{k}\|\|y_{k}\|\|A_{k}(2)\|]} {m\mu_{1}\| s_{k}\|^{2}}. \end{eqnarray*} $

最后一个不等式利用了式(3.4) 和式(3.9).

由假设(ⅱ)可知, 存在常数 $b_{3}$, 使得式(4.3) 成立.下证式(4.4).易知式(1.4) 的逆

$ \begin{eqnarray*} H_{k+1}&=&H_{k}+\frac{(s_{k}-H_{k}y_{k}^{*})s_{k}^{T}+s_{k}(s_{k}-H_{k}y_{k}^{*})^{T}}{y_{k}^{*T}s_{k}} -\frac{y_{k}^{*T}(s_{k}-H_{k}y_{k}^{*})s_{k}s_{k}^{T}}{(y_{k}^{*T}s_{k})^{2}}\\ &=&(I-\frac{s_{k}y_{k}^{*T}}{y_{k}^{*T}s_{k}})H_{k}(I-\frac{y_{k}^{*}s_{k}^{T}}{y_{k}^{*T}s_{k}}) +\frac{s_{k}^{*}s_{k}^{T}}{y_{k}^{*T}s_{k}}. \end{eqnarray*} $

这是DFP校正公式的对偶形式, 对应关系 $H_{k}\rightarrow B_{k}, H_{k+1}\rightarrow B_{k+1}, s_{k}\rightarrow y_{k}$.由文献[7]中的引理4.1知, 存在常数 $b_{8}, b_{9}\geq0$, 使得

$ \begin{eqnarray} \|H_{k+1}-G(x^{*})^{-1}\|_{Q^{-1}, F}&\leq&(\sqrt{1-\gamma\omega_{k}^{2}}+b_{8}\frac{\|Q^{-1}s_{k}-Qy_{k}^{*}\|}{\|Qy_{k}^{*}\|})\|H_{k}-G(x^{*})^{-1}\|_{Q^{-1}, F} \nonumber\\ &&+b_{9}\frac{\|s_{k}-G(x^{*})^{-1}y_{k}^{*}\|}{\|Qy_{k}^{*}\|}, \end{eqnarray} $

(4.6)

其中 $\omega_{k}$由式(4.5) 产生.

$ \begin{eqnarray*} \|Qy_{k}^{*}-Q^{-1}s_{k}\|&\leq&\|Q\|\|y_{k}^{*}-Q^{-2}s_{k}\|=\|Q\|\|y_{k}^{*}-G(x^{*})s_{k}\|\\ &&=\|Q\|\|\frac{\delta_{k}^{T}s_{k}}{|\delta_{k}^{T}s_{k}|}\delta_{k}-G(x^{*})s_{k}\|\\ &=&\|Q\|\|\theta y_{k}+(1-\theta)A_{k}(2)s_{k}-G(x^{*})s_{k}\|\\ &\leq&\|Q\|(\|\theta\int_{0}^{1}G(x_{k}+\gamma s_{k})s_{k}d\gamma-\theta G(x^{*})s_{k}\|+\|(1-\theta)A_{k}(2)s_{k}\|)\\ &\leq&\|Q\|\|s_{k}\|[\theta\Psi\int_{0}^{1}\|x_{k}-x^{*}-\gamma s_{k}\|^{\upsilon}d\gamma+(1-\theta)\|A_{k}(2)\|]\\ &\leq&\|Q\|\|s_{k}\|[\theta\Psi\phi_{k}+(1-\theta)\|A_{k}(2)\|]. \end{eqnarray*} $

又因为 $\phi_{k}\rightarrow0$, $A_{k}(2)\rightarrow0$, 则 $k$充分大时, 有 $\|Qy_{k}^{*}-Q^{-1}s_{k}\|\leq q\|Q\|\|s_{k}\|$成立, 其中 $q\in(0, 1)$为常数.此外, 存在常数 $b_{10}$, 使得对充分大的 $k$, 下式成立.

$ \begin{eqnarray*} \|Qy_{k}^{*}\|&=&\|Q[\theta y_{k}+(1-\theta)A_{k}(2)s_{k}]\| \geq\|Q\theta(g_{k+1}-g_{k})\|-(1-\theta)\|A_{k}(2)\|\|Qs_{k}\|\\ &\geq&b_{10}\|x_{k+1}-x_{k}\|-(1-\theta)\|A_{k}(2)\|\|Q\|\|s_{k}\|\\ &\geq&[b_{10}-(1-\theta)\|A_{k}(2)\|\|Q\|]\cdot\|s_{k}\|. \end{eqnarray*} $

利用 $\|A_{k}(2)\|\rightarrow0$, 上述不等式隐含存在常数 $c$, 使得当 $k$充分大时, $\|Qy_{k}^{*}\|\geq c\|s_{k}\|$.因此得到

$ \begin{eqnarray} \frac{\|Qy_{k}^{*}-Q^{-1}s_{k}\|}{\|Qy_{k}^{*}\|}\leq c^{-1}\|Q\|[\theta\Psi\phi_{k}+(1-\theta)\|A_{k}(2)\|], \end{eqnarray} $

(4.7)

$\begin{eqnarray} &&\frac{\|s_{k}-G(x^{*})^{-1}y^{*}\|}{\|Qy_{k}^{*}\|}=\frac{\|s_{k}-Q^{2}y^{*}\|}{\|Qy_{k}^{*}\|} =\frac{\|Q(Qy^{*}-Q^{-1}s_{k})\|}{\|Qy_{k}^{*}\|}\leq\frac{\|Q\|\|Qy^{*}-Q^{-1}s_{k}\|}{\|Qy_{k}^{*}\|} \nonumber\\ & \leq &c^{-1}\|Q\|^{2}[\theta\Psi\phi_{k}+(1-\theta)\|A_{k}(2)\|].\end{eqnarray} $

(4.8)

由式(4.6), (4.7), (4.8) 得到式(4.4), 由 $\sum\limits_{k=0}^{\infty}\phi_{k}\leq0$, $\sum\limits_{k=0}^{\infty}A_{k}(2)\leq0$和式(4.3), (4.4), 得到 $\|B_{k}-G(x^{*})\|_{Q, F}$和 $\|H_{k}-G(x^{*})^{-1}\|_{Q^{-1}, F}$收敛, 且 $\{\|B_{k}\|\}_{F}$和 $\{\|H_{k}\|\}_{F}$有界.

定理4.1  设 $\{x_{k}\}$是算法1产生的序列, 若假设条件(ⅰ)和(ⅱ)成立, 则序列 $\{x_{k}\}$超线性收敛到 $x^{*}$.

证  由引理4.3知 $\{B_{k}\}$和 $\{B_{k}^{-1}\}$有界.与文献[8]中引理3.9的证明相似, 容易得到

$\begin{eqnarray*} \lim\limits_{k\rightarrow\infty}\frac{\|(B_{k}-G(x_{*}))s_{k}\|}{\|s_{k}\|}=0.\end{eqnarray*} $

(4.9)

因为函数 $f$在 $U(x^{*})$内强凸, 且 $\{B_{k}^{-1}\}$有界, 则当 $k\rightarrow\infty$时, $\|B_{k}^{-1}g_{k}\|\rightarrow0$.事实上, 对所有充分大的 $k$, $\|B_{k}^{-1}g_{k}\|\leq\Delta_{\min}$.因此, 当 $k$分大时, $s_{k}=-B_{k}^{-1}g_{k}$是式(1.2) 的唯一解.算法1同单位步长的BFGS一致.因而, 结合式(4.9) 得出点列 $\{x_{k}\}$的超线性收敛.