考虑无约束最优化问题

$ \mathop {\min }\limits_{x \in {R^n}} f(x), $

(1.1)

其中$f(x):{R^n} \to {R^1}$是连续可微函数.本文采用如下记号：

$\cdot \parallel \cdot \parallel$表示Euclidean范数.

$\cdot g(x)\in R^{n}$是$f(x)$在点$x$的梯度.

$\cdot H(x)\in R^{n\times n}$是在点$f(x)$的Hessian矩阵.

$\cdot \{x_{k}\}$是某一算法产生的迭代点列, 并记$f_{k}=f(x_{k}), g_{k}=g(x_{k}), H_{k}=H(x_{k})$.

$\cdot B_{k}\in R^{n\times n}$是对称矩阵, 它是$f(x)$在点$x_{k}$的Hessian矩阵或其近似.

$\cdot \overline{B}_{k}$是安全正定矩阵且满足Schnabel和Eskow^[1]改进的Cholesky分解.$\overline{B}_{k}=B_{k}+E_{k}$, $E_{k}$是一个使得$\overline{B}_{k}$安全正定的对角矩阵; 当$B_{k}$正定时, 取$E_{k}=0$.

1970年, Powell^[2]首次提出求解(1.1) 的信赖域算法, 其思想是通过求解一系列二次函数在信赖域中的最优点的方法来求(1.1) 的解.信赖域算法的显著特点是其稳定的数值性能、强收敛性和强适性, 能有效地解决病态问题, 需要迭代的次数少, 因此信赖域算法在非线性优化界受到了特别的重视, 特别是最近几年一直是非线性优化界研究的一个热点.目前信赖域算法已经和线搜索方法并列为求解非线性优化问题的两类主要的数值方法.

信赖域算法是在每一步迭代，求解信赖域子问题

$ \min {q_k}(s) = {f_k} + g_k^Ts + \frac{1}{2}{s^T}{B_k}s\;\;\;\;\;s.t.\left\| s \right\| \le {\Delta _k}, $

(1.2)

其中$s=x-x_{k}, g_{k}=\nabla f(x_{k})$, $\Delta_{k}>0$是信赖域半径.

在当前迭代点$x_{k}$, 设子问题(1.2) 的解是$s_{k}$. $f(x)$在点$x_{k}$处的预估下降量是

$ {\rm{Pre}} s_{k}=-g_{k}^{T}s_{k}-\frac{1}{2}s_{k}^{T}B_{k}s_{k}; $

实际下降量是

$ {\rm{Are}} s_{k}=f(x_{k})-f(x_{k}+s_{k}). $

实际下降量${\rm{Are}} s_{k}$与预估下降量${\rm{Pre}} s_{k}$的比值

$ r_{k}=\frac{{\rm{Are}} s_{k}}{{\rm{Pre}} s_{k}}, $

它反映了子问题(1.2) 的解$s_{k}$令人满意的程度. $r_{k}$越接近于1, 表明$s_{k}$越令人满意.如果$s_{k}$令人满意, 就接受$s_{k}$, 得到新的迭代点$x_{k+1}$, 同时增大信赖域半径$\Delta_{k}$；反之，则拒绝$s_{k}$, 并需缩小信赖域半径$\Delta_{k}$, 重解子问题(1.2)，直至$s_{k}$被接受.即

$ {x_{k + 1}} = \left\{ \begin{array}{l} {x_k} + {s_k}, \;\;\;\;{r_k} \ge \mu, \\ {x_k}, \;\;\;\;\;\;\;\;\;\;{r_k} < \mu, \end{array} \right. $

其中$\mu\in (0, 1)$是一个常数，并修正信赖域半径

$ {\Delta _{k + 1}} = \left\{ \begin{array}{l} {c_1}{\Delta _k}, \;\;\;\;\;\;\;\;\;\;\;\;\;{r_k} < {\mu _1}, \\ {c_2}{\Delta _k}, \;\;\;\;\;\;\;\;\;\;\;\;{r_k} > {\mu _2}, \\ {\Delta _k}, \;\;\;\;\;\;\;\;{\mu _1} \le {r_k} \le {\mu _2}, \end{array} \right. $

(1.3)

其中$0 \le {\mu _1} < {\mu _2} < 1, 0 < {c_1} < 1 < {c_2}$是常数.

(1.3)式对$\Delta_{k}$的修正没有利用对算法有重大影响的$g_{k}$, $B_{k}$等这些当前迭代点的信息，而只是根据$r_{k}$按常数倍放大或缩小初始信赖域半径，这降低了算法的效率.基于此，许多自适应信赖域方法被提出. Zhang et al.^[3]给出一个自适应信赖域方法，信赖域半径取为$\Delta_{k}=c^{p}\parallel g_{k}\parallel \overline{M}_{k}$ (这里${\rm{0 < c < 1, p}}$是非负整数变量，$\overline{M}_{k}=\parallel \overline{B}_{k}^{-1}\parallel$)，如果上次迭代的试探步$s_{k-1}$被接受，则$p=0$；否则，$p=p+1$.姚升保等^[4]}提出信赖域半径取为$\Delta_{k+1}\in [r_{1}\|d_{k}\|, r_{2}\|d_{k}\|]$或$\Delta_{k+1}\in [\|d_{k}\|, r_{3}\|d_{k}\|]$（这里${\rm{0 < }}{{r}_1}{\rm{ < }}{{r}_2}{\rm{ < 1 < }}{{r}_3}$）的自适应信赖域方法.文[5]也给出了一个自适应信赖域算法，信赖域半径取为$\Delta_{k}=R_{\eta}(t)\|d_{k-1}\|$, 其中$R_{\eta}(t)$是一个关于$r_{k}$的$R-$函数.

定义1.1^[5]  $R_{\eta}(t)$定义在$(-\infty, +\infty)$上，参数$\eta\in (0, 1)$, $R_{\eta}(t)$是一个$R-$函数当且仅当满足：

(ⅰ)$R_{\eta}(t)$在$(-\infty, +\infty)$非减；

(ⅱ) $\lim \limits_{t\rightarrow -\infty} R_{\eta}(t)=\beta(\beta\in(0, 1)$是一个常数）；

(ⅲ) $R_{\eta}(t)\leq 1-\gamma_{1}(\forall t<\eta, \gamma_{1}\in(0, 1-\beta)$是一个常数）；

(ⅳ) $R_{\eta}(\eta)=1+\gamma_{2}(\gamma_{2}\in(0, \beta)$是一个常数）；

(ⅴ) $\lim \limits_{t\rightarrow +\infty} R_{\eta}(t)=M(M\in(1+\gamma_{2}, +\infty)$是一个常数.

由定义1.1，我们得到$R-$函数的一些性质：

定理 1.1^[5]  如果$R_{\eta}(t)(\eta\in(0, 1) )$是一个$R - $函数，则

$ 0<\beta\leq R_{\eta}(t)\leq1-\gamma_{1}<1, \forall t\in(-\infty, \eta), $

(1.4)

$ 1<1+\gamma_{2}\leq R_{\eta}(t)\leq M<+\infty, \forall t\in(\eta, +\infty), $

(1.5)

因此可以把$R_{\mu}(r_{k})$作为增大或缩小信赖域半径的尺度，使信赖域半径的调节依据于问题本身，更有客观性.

大多数信赖域算法采用二次模型逼近$f(x)$，但对一些非二次性态强，曲率变化剧烈的函数，用二次模型逼近$f(x)$效果较差，因而得到的最优点较差. 1980年，Davidon^[6]首次提出锥模型.锥模型比二次模型更一般，包含的信息和自由度更多，能更好地逼近$f(x)$，因此许多学者对它进行了研究.Sorensen^[7]，Ariyawansa ^[8]和Sheng^[9]研究了锥模型共线调比拟牛顿方法.鉴于锥模型和信赖域算法各具优点，许多学者将二者结合进行研究.1995年，诸梅芳，薛毅等^[10]提出求解问题(1.1) 的锥模型信赖域算法；2005年，Ni Q.等^[11]给出锥模型信赖域子问题的最优性条件，为锥模型信赖域子问题的求解提供了更充分且合理的理论基础.信赖域算法进一步发展.2005年，Fu J.H.等^[12]将自适应技术引入锥模型信赖域算法，提出锥模型自适应信赖域算法；2010年，王希云等^[13]也提出锥模型自适应信赖域算法.锥模型信赖域算法得到了广泛的发展，并且数值结果表明对一些函数，特别是对曲率变化剧烈的函数，锥模型信赖域算法比二次模型信赖域算法效果更好.

求解问题(1.1) 的一个典型的锥模型信赖域子问题是：

$ \mathop {\min }\limits_{{s_k} \in {R^n}} {q_k}({s_k}) = {f_k} + \frac{{g_k^T{s_k}}}{{1 + b_k^T{s_k}}} + \frac{1}{2}\frac{{s_k^T{B_K}{s_k}}}{{{{(1 + b_k^T{s_k})}^2}}}{\text{s}}{\text{.t}}.\left\| {{s_k}} \right\| \leqslant {\Delta _k}, $

(1.6)

其中$b_{k}\in R^{n}$是水平向量，$1+b_{k}^{T}s_{k}>0$.当$b_{k}=0$或$b_{k}^{T}s_{k}=0$时，锥模型转化为二次模型，因此锥模型是二次模型的推广.

鉴于文[3]和文[5]工作的基础上，基于锥模型信赖域子问题(1.6)，本文提出了一类新的锥模型自适应信赖域算法，信赖域半径取为

$ \Delta_{k}=R_{\mu}(r_{k})\frac{\|B_{k}^{-1}\|\|g_{k}\|}{|1+b_{k}^{T}B_{k}^{-1}g_{k}|}, $

(1.7)

使得在每步迭代中，信赖域半径的修正依据问题本身确定.

本文其他部分安排如下：第2节给出了锥模型自适应信赖域算法，第3，4节分别分析了算法的全局收敛性和$Q-$二阶收敛速度，最后一节给出了数值实验.

在本节中，基于锥模型信赖域子问题(1.6) 和信赖域半径(1.7)，我们提出一个求解(1.1) 的自适应信赖域算法.

设问题(1.6) 的解为$s_{k}$.目标函数$f(x)$在第$k$步的实际下降量为

$ {\rm{Are}} s_{k}=f_{k}-f(x_{k}+s_{k}), $

(2.1)

预估下降量为

$ {\rm{Pre}} s_{k}=q_{k}(0)-q_{k}(s_{k})=-\frac{g_{k}^{T}s_{k}}{1+b_{k}^{T}s_{k}}- \frac{1}{2}\frac{s_{k}^{T}B_{k}s_{k}}{(1+b_{k}^{T}s_{k})^{2}}, $

(2.2)

比值

$ r_{k}=\frac{{\rm{Are}} s_{k}}{{\rm{Pre}} s_{k}}. $

(2.3)

下面给出新的锥模型自适应信赖域算法(CSATR)的具体实现过程:

步0  给出初始点$x_{0}\in R^{n}$，$\Delta_{0}>0$，$b_{0}\in R^{n\times1}$，$B_{0}=I$ (单位阵)，$0<\beta<1$，$0<\gamma_{1}<1-\beta$，$\gamma_{2}>0$，$M>1+\gamma_{2}$，$\varepsilon>0$，$0<\mu<1$，$k:=0$.

步1  计算$g_{k}=g(x_{k})$.如果$\|g_{k}\|\leq\varepsilon$，则停止计算，$x^{\ast}=x_{k}$；否则，转步2.

步2  近似求解问题(1.6) 得到$s_{k}$.

步3  利用(2.1)，(2.2)，(2.3)式 分别计算${\rm{Are}} s_{k}$，${\rm{Pre}} s_{k}$，$r_{k}$.

步4  如果$r_{k}<\mu$，令$x_{k+1}=x_{k}$；否则，令$x_{k+1}=x_{k}+s_{k}$.

步5  修正$b_{k}$及$B_{k}$，产生$b_{k+1}$及$B_{k+1}$，利用(1.7)式计算$\Delta_{k+1}$.令$k:=k+1$，转步1.

注：（ⅰ）算法(CSATR)中，要求$\|b_{k}\|\Delta_{k}<1$；如果$\|b_{k}\|\Delta_{k}\geq1$，则令$\Delta_{k}=\frac{\alpha}{\|b_{k}\|}(0<\alpha<1)$使得$\|b_{k}\|\Delta_{k}<1$.

（ⅱ）算法(CSATR)步2中$s_{k}$的具体求解及步5中$b_{k}$和$B_{k}$的修正见文[12].

（ⅲ）若(1.6) 中及(1.7) 中的$b_{k}=0$，则算法(CSATR)转化为相应的二次模型自适应信赖域算法（QSATR）.

（ⅳ）算法(CSATR)中，利用(1.3) 更新信赖域半径，得到传统的锥模型信赖域算法（CTNTR）.

本文所需假设如下：

A1: $f(x)$在水平集$L(x_{0})=\{x|f(x)\leq f(x_{0})\}$上有下界.

A2:$\{B_{k}\}$，$\{B_{k}^{-1}\}$，$\{b_{k}\}$一致有界，即存在常数$\delta_{1}, \delta_{2}, \delta_{3}>0$，使得对$\forall k$, 有$\|B_{k}\|\leq\delta_{1}$，$\|B_{k}^{-1}\|\leq\delta_{2}$，$\|b_{k}\|\leq\delta_{3}$.

A3: $g(x)$在$L(x_{0})$上一致连续.

本文算法(CSATR)中的$B_{k}, \forall k$, 用文[12]中的方法修正时保持正定性.以下的$B_{k}, \forall k$均为对称正定矩阵.

为讨论方便，记$I=\{k:r_{k}\geq\mu\}$，$J=\{k:r_{k}<\mu\}$.

引理3.1  设$s_{k}$是子问题(1.6) 的解，$g_{k}\neq0$，则

$ q_{k}(0)-q_{k}(s_{k})>0. $

(3.1)

为得到算法的下降性条件，引入Cauchy点

$ S_{k}^{C}=-T_{k}\frac{\Delta_{k}}{\|g_{k}\|}g_{k}, $

其中

$ {T_k} = \left\{ \begin{array}{l} \min \{ 1, \frac{{{{\left\| {{g_k}} \right\|}^3}}}{{{\Delta _k}(g_k^T{B_k}{g_k} + g_k^T{g_k}b_k^T{g_k})}}\}, g_k^T{B_k}{g_k} + g_k^T{g_k}b_k^T{g_k} > 0, \\ 1, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;g_k^T{B_k}{g_k} + g_k^T{g_k}b_k^T{g_k} \le 0. \end{array} \right. $

引理3.2  对Cauchy点$S_{k}^{C}$满足

$ q_{k}(0)-q_{k}(S_{k}^{C})\geq\frac{1}{2}\|g_{k}\|\min\{\Delta_{k}, \frac{\|g_{k}\|}{\|B_{k}\|}\}. $

(3.2)

证  分三种情况证明.

(ⅰ)当$g_{k}^{T}B_{k}g_{k}+g_{k}^{T}g_{k}b_{k}^{T}g_{k}>0$且$1\geq\frac{\|g_{k}\|^{3}}{\Delta_{k}(g_{k}^{T}B_{k}g_{k}+g_{k}^{T}g_{k}b_{k}^{T}g_{k})}$时，$T_{k}=\frac{\|g_{k}\|^{3}}{\Delta_{k}(g_{k}^{T}B_{k}g_{k}+g_{k}^{T}g_{k}b_{k}^{T}g_{k})} $，$S_{k}^{C}=-\frac{\|g_{k}\|^{2}}{g_{k}^{T}B_{k}g_{k}+g_{k}^{T}g_{k}b_{k}^{T}g_{k}}$，则

$ \begin{array}{l} {q_k}(0) - {q_k}(S_k^C) = - \frac{{g_k^TS_k^C}}{{1 + b_k^TS_k^C}} - \frac{1}{2}\frac{{S_k^{CT}{B_k}S_k^C}}{{{{(1 + b_k^TS_k^C)}^2}}} = \frac{{{{\left\| {{g_k}} \right\|}^4}}}{{g_k^T{B_k}{g_k}}} - \frac{1}{2}\frac{{{{\left\| {{g_k}} \right\|}^4}}}{{g_k^T{B_k}{g_k}}}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{2}\frac{{{{\left\| {{g_k}} \right\|}^4}}}{{g_k^T{B_k}{g_k}}} \ge \frac{1}{2}\frac{{{{\left\| {{g_k}} \right\|}^2}}}{{\left\| {{B_k}} \right\|}} \ge \frac{1}{2}\left\| {{g_k}} \right\|\min \{ {\Delta _k}, \frac{{\left\| {{g_k}} \right\|}}{{\left\| {{B_k}} \right\|}}\} . \end{array} $

(ⅱ)当$g_{k}^{T}B_{k}g_{k}+g_{k}^{T}g_{k}b_{k}^{T}g_{k}>0$且$1<\frac{\|g_{k}\|^{3}}{\Delta_{k}(g_{k}^{T}B_{k}g_{k}+g_{k}^{T}g_{k}b_{k}^{T}g_{k})}$时，

$ \|g_{k}\|^{3}-\Delta_{k}g_{k}^{T}g_{k}b_{k}^{T}g_{k}-\Delta_{k}g_{k}^{T}B_{k}g_{k}>0, $

(3.3)

$ g_{k}^{T}B_{k}g_{k}+g_{k}^{T}g_{k}b_{k}^{T}g_{k}>0, $

(3.4)

$ S_{k}^{C}=-\frac{\Delta_{k}}{\|g_{k}\|}g_{k}. $

(3.5)

由$\|b_{k}\|\Delta_{k}<1$式知$\Delta_{k}b_{k}^{T}g_{k}\leq\Delta_{k}\|b_{k}\|\|g_{k}\|<\|g_{k}\|$，则

$ \|g_{k}\|-\Delta_{k}b_{k}^{T}g_{k}>0. $

(3.6)

由(3.3)-(3.6)式知

$ \begin{array}{l} {q_k}(0) - {q_k}(S_k^C) = - \frac{{g_k^TS_k^C}}{{1 + b_k^TS_k^C}} - \frac{1}{2}\frac{{S_k^{CT}{B_k}S_k^C}}{{{{(1 + b_k^TS_k^C)}^2}}} = \frac{{{\Delta _k}g_k^T{g_k}}}{{\left\| {{g_k}} \right\| - {\Delta _k}b_k^T{g_k}}} - \frac{{\Delta _k^2g_k^T{B_k}{g_k}}}{{2{{(\left\| {{g_k}} \right\| - {\Delta _k}b_k^T{g_k})}^2}}}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{{{\Delta _k}[{{\left\| {{g_k}} \right\|}^3}-{\Delta _k}g_k^T{g_k}b_k^T{g_k}-{\Delta _k}g_k^T{B_k}{g_k}] + {\Delta _k}g_k^T{g_k}(\left\| {{g_k}} \right\| - {\Delta _k}b_k^T{g_k})}}{{2{{(\left\| {{g_k}} \right\| - {\Delta _k}b_k^T{g_k})}^2}}}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge \frac{{{\Delta _k}g_k^T{g_k}}}{{2(\left\| {{g_k}} \right\| - {\Delta _k}b_k^T{g_k})}} \ge \frac{{{\Delta _k}g_k^T{g_k}}}{{2(\left\| {{g_k}} \right\| + {\Delta _k}\left\| {b_k^T} \right\|\left\| {{g_k}} \right\|)}} \ge \frac{1}{2}\frac{{{\Delta _k}{{\left\| {{g_k}} \right\|}^2}}}{{\left\| {{g_k}} \right\|}}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{2}{\Delta _k}\left\| {{g_k}} \right\| \ge \frac{1}{2}\left\| {{g_k}} \right\|\min \{ {\Delta _k}, \frac{{\left\| {{g_k}} \right\|}}{{\left\| {{B_k}} \right\|}}\} . \end{array} $

(ⅲ)当$g_{k}^{T}B_{k}g_{k}+g_{k}^{T}g_{k}b_{k}^{T}g_{k}\leq0$时，

$ g_{k}^{T}B_{k}g_{k}+g_{k}^{T}g_{k}b_{k}^{T}g_{k}\leq0. $

(3.7)

$ S_{k}^{C}=-\frac{\Delta_{k}}{\|g_{k}\|}g_{k}. $

(3.8)

由(3.7)式知$0 < g_k^T{B_k}{g_k} \le - g_k^T{g_k}b_k^T{g_k} = {\left\| {{g_k}} \right\|^2}b_k^T{g_k}$.于是

$ b_{k}^{T}g_{k}<0. $

(3.9)

从而

$ \|g_{k}\|-\Delta_{k}b_{k}^{T}g_{k}>0. $

(3.10)

由(3.7)式知

$ g_{k}^{T}B_{k}g_{k}+g_{k}^{T}g_{k}b_{k}^{T}g_{k}\leq\frac{g_{k}^{T}g_{k}\|g_{k}\|}{\Delta_{k}}. $

于是

$ g_{k}^{T}B_{k}g_{k}\leq\frac{g_{k}^{T}g_{k}\|g_{k}\|-\Delta_{k}g_{k}^{T}g_{k}b_{k}^{T}g_{k}}{\Delta_{k}}. $

(3.11)

又

$ \frac{g_{k}^{T}g_{k}\|g_{k}\|-\Delta_{k}g_{k}^{T}g_{k}b_{k}^{T}g_{k}}{\Delta_{k}}= \frac{g_{k}^{T}g_{k}(\|g_{k}\|-\Delta_{k}b_{k}^{T}g_{k})}{\Delta_{k}}, $

(3.12)

由(3.11) 和(3.12)式知:

$ 0<\frac{\Delta_{k}g_{k}^{T}B_{k}g_{k}}{(\|g_{k}\|-\Delta_{k}b_{k}^{T}g_{k})^{2}}\leq \frac{g_{k}^{T}g_{k}}{\|g_{k}\|-\Delta_{k}b_{k}^{T}g_{k}}. $

(3.13)

于是由(3.8)，(3.13)式，（ⅱ）的过程，(3.9) 和(3.10)式知

$ \begin{array}{l} {q_k}(0) - {q_k}(S_k^C) = \frac{{{\Delta _k}g_k^T{g_k}}}{{\left\| {{g_k}} \right\| - {\Delta _k}b_k^T{g_k}}} - \frac{{\Delta _k^2g_k^T{B_k}{g_k}}}{{2{{(\left\| {{g_k}} \right\| - {\Delta _k}b_k^T{g_k})}^2}}}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge \frac{{{\Delta _k}g_k^T{g_k}}}{{\left\| {{g_k}} \right\| - {\Delta _k}b_k^T{g_k}}} - \frac{{{\Delta _k}g_k^T{g_k}}}{{2\left\| {{g_k}} \right\| - {\Delta _k}b_k^T{g_k}}}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{2}\frac{{{\Delta _k}g_k^T{g_k}}}{{\left\| {{g_k}} \right\| - {\Delta _k}b_k^T{g_k}}} \ge \frac{1}{2}\frac{{{\Delta _k}{{\left\| {{g_k}} \right\|}^2}}}{{\left\| {{g_k}} \right\|}}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{2}{\Delta _k}\left\| {{g_k}} \right\| \ge \frac{1}{2}\left\| {{g_k}} \right\|\min \{ {\Delta _k}, \frac{{\left\| {{g_k}} \right\|}}{{\left\| {{B_k}} \right\|}}\} . \end{array} $

证毕.

下面的引理说明子问题(1.6) 的解$s_{k}$满足充分下降条件.

引理3.3  设$s_{k}$是子问题(1.6) 的解，则

$ {\rm{Pre}} s_{k}\geq\frac{1}{2}\|g_{k}\|\min\{\Delta_{k}, \frac{\|g_{k}\|}{\|B_{k}\|}\}. $

(3.14)

证  由(3.2)式知

$ {\rm{Pre}} s_{k}=q_{k}(0)-q_{k}(s_{k})\geq q_{k}(0)-q_{k}(S_{k}^{C})\geq\frac{1}{2}\|g_{k}\|\min\{\Delta_{k}, \frac{\|g_{k}\|}{\|B_{k}\|}\}. $

引理3.4  如果假设A1-A3成立，则存在常数$c_{0}>0$，使得

$ \|s_{k}\|\leq c_{0}\|g_{k}\|. $

(3.15)

证  由假设A3知存在$0<\varepsilon<\lambda$，使得$\varepsilon\leq\|g_{k}\|\leq\lambda$.于是由假设A2知

$ \mid 1+b_{k}^{T}B_{k}^{-1}g_{k}\mid\geq1-\mid b_{k}B_{k}^{-1}g_{k}\mid\geq1-\| b_{k}^{T}\|\| B_{k}^{-1}\|\| g_{k}\|\geq1-\delta_{3}\delta_{2}\lambda>0. $

(3.16)

于是由(1.5)式，假设A2和(3.16)式知

$ \Delta_{k}=R_{\mu}(r_{k})\frac{\|B_{k}^{-1}\|\|g_{k}\|}{|1+b_{k}^{T}B_{k}^{-1}g_{k}|}\leq \frac{M\|B_{k}^{-1}\|\|g_{k}\|}{|1+b_{k}^{T}B_{k}^{-1}g_{k}|}\leq\frac{M\delta_{2}}{1-\delta_{3}\delta_{2}\lambda}\|g_{k}\|, $

令$c_{0}=\frac{M\delta_{2}}{1-\delta_{3}\delta_{2}\lambda}$，则$\Delta_{k}\leq c_{0}\|g_{k}\|$.从而$\|s_{k}\|\leq c_{0}\|g_{k}\|.$

引理3.5  如果$\{x_{k}\}$是由算法(CSATR)产生的点列，则$\{x_{k}\}\subset L(x_{0})$.

证  用数学归纳法证明.

当$k=0$时，$f(x_{0})\leq f(x_{0})$，则$x_{k}\in L(x_{0})$，命题成立.

下证假设$x_{k}\in L(x_{0})$时，则有$x_{k+1}\in L(x_{0})$.当$x_{k}\in L(x_{0})$时，有$f(x_{k})\leq f(x_{0})$.

(ⅰ)如果$k\in I$，则$r_{k}\geq\mu$.

于是由(3.1)式知$f(x_{k})-f(x_{k+1})\geq\mu( q_{k}(0)-q_{k}(s_{k}))>0$.因而$f(x_{k+1})\leq f(x_{k})$.所以$f(x_{k+1})\leq f(x_{0})$.

（ⅱ）如果$k\in J$，则$r_{k}<\mu$.

由算法(CSATR)步4知$x_{k+1}=x_{k}$，于是$f(x_{k+1})= f(x_{k})$.所以$f(x_{k+1})\leq f(x_{0})$.

由（ⅰ）和（ⅱ）知当$x_{k}\in L(x_{0})$时，$x_{k+1}\in L(x_{0})$.

由以上知结论成立.

算法(CSATR)中，如果$x_{k+1}=x_{k}+s_{k}$，则$x_{k+1}$是一个成功的迭代点；如果$x_{k+1}=x_{k}$，则$x_{k+1}$是一个非成功的迭代点.

引理3.6  假设A1，A3成立，$\{x_{k}\}$是由算法(CSATR)产生的无穷点列，且对$\forall k$，有$\|g_{k}\|>\varepsilon, \varepsilon\in(0, 1)$是常数，则对$\forall k$，存在非负整数$p$使得$x_{k+p+1}$是一个成功的迭代点.

证  假设存在$k_{0}$使得$\forall p$都有$x_{k_{0}+p+1}$是一个非成功的迭代点.即

$ r_{k_{0}+p}<\mu, p=0, 1, 2, \cdots. $

(3.17)

由算法(CSATR)步4知

$ x_{k_{0}+p+1}=x_{k}, p=0, 1, 2, \cdots. $

(3.18)

由(1.7) 和(1.4) 知

$ \Delta_{k_{0}+p+1}\rightarrow0, p\rightarrow\infty. $

(3.19)

于是

$ \|s_{k_{0}+p+1}\|\rightarrow0, p\rightarrow\infty. $

因而对充分大的$p$，有

$ \frac{1}{1+b_{k_{0}+p}^{T}s_{k_{0}+p}}=1+O(\|s_{k_{0}+p}\|), $

于是

$ \frac{g_{k_{0}+p}^{T}s_{k_{0}+p}}{1+b_{k_{0}+p}^{T}s_{k_{0}+p}}=g_{k_{0}+p}^{T}s_{k_{0}+p}+O(\|s_{k_{0}+p}\|^{2}), $

(3.20)

$ \frac{s_{k_{0}+p}^{T}B_{k_{0}+p}s_{k_{0}+p}}{(1+b_{k_{0}+p}^{T}s_{k_{0}+p})^{2}}=s_{k_{0}+p}^{T}B_{k_{0}+p} s_{k_{0}+p}+o(\|s_{k_{0}+p}\|^{2}). $

(3.21)

由(3.20)式和(3.21)式知

$ \begin{array}{l} {q_{{k_0} + p}}(0) - {q_{{k_0} + p}}({s_{{k_0} + p}}) = - \frac{{g_{{k_0} + p}^T{s_{{k_0} + p}}}}{{1 + b_{{k_0} + p}^T{s_{{k_0} + p}}}} - \frac{1}{2}\frac{{s_{{k_0} + p}^T{B_{{k_0} + p}}{s_{{k_0} + p}}}}{{{{(1 + b_{{k_0} + p}^T{s_{{k_0} + p}})}^2}}}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = - g_{{k_0} + p}^T{s_{{k_0} + p}} - \frac{1}{2}s_{{k_0} + p}^T{B_{{k_0} + p}}{s_{{k_0} + p}} + o({\left\| {{s_{{k_0} + p}}} \right\|^2}). \end{array} $

(3.22)

由(3.14)式和(3.19)式知

$ \begin{array}{l} {q_{{k_0} + p}}(0) - {q_{{k_0} + p}}({s_{{k_0} + p}}) \ge \frac{1}{2}\left\| {{g_{{k_0} + p}}} \right\|\min \{ {\Delta _{{k_0} + p}}, \frac{{\left\| {{g_{{k_0} + p}}} \right\|}}{{\left\| {{B_{{k_0} + p}}} \right\|}}\} \ge \frac{1}{2}\left\| {{g_{{k_0} + p}}} \right\|{\Delta _{{k_0} + p}}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge \frac{1}{2}\left\| {{g_{{k_0} + p}}} \right\|\left\| {{s_{{k_0} + p}}} \right\| \ge \frac{1}{2}\varepsilon \left\| {{s_{{k_0} + p}}} \right\|. \end{array} $

(3.23)

由$f(x)$是连续可微函数及Taylor展开式知

$ f_{k_{0}+p}-f(x_{k_{0}+p}+s_{k_{0}+p})=-g_{k_{0}+p}^{T}s_{k_{0}+p}-\frac{1}{2} s_{k_{0}+p}^{T}B_{k_{0}+p}s_{k_{0}+p}+o(\|s_{k_{0}+p}\|^{2}). $

(3.24)

由(3.22)-(3.24)式知

$ \frac{f_{k_{0}+p}-f(x_{k_{0}+p}+s_{k_{0}+p})}{q_{k_{0}+p}(0)-q_{k_{0}+p}(s_{k_{0}+p})}-1|\leq \frac{o(\|s_{k_{0}+p}\|^{2})}{\frac{1}{2}\varepsilon\|s_{k_{0}+p}\|}\rightarrow 0. $

(3.25)

因此当$p$充分大时，由(3.25) 及$0<\mu<1$式知$r_{k_{0}+p}\geq\mu$，这与(3.17) 矛盾.

定理3.1  如果假设A1成立，$\{x_{k}\}$是由算法(CSATR)产生的点列，则

$ \lim \limits_{k\rightarrow \infty}\|g_{k}\|=0. $

(3.26)

证(反证法)   假设结论不成立，则存在常数$\varepsilon>0, \varepsilon\in(0, 1)$，使得$\|g_{k}\|\geq\varepsilon, \forall k$.

下证

$ \lim \limits_{k\in J, k\rightarrow \infty} R_{\mu}(r_{k})=0. $

(3.27)

由引理3.6知当$k$充分大时，则$k\in I$，此时有

$ f_{k}-f(x_{k}+s_{k})>\mu( q_{k}(0)-q_{k}(s_{k})), $

由于$\{f_{k}\}$单调递减有下界，因此$\{f_{k}\}$收敛.

于是当$k$充分大时，有

$ q_{k}(0)-q_{k}(s_{k})\rightarrow 0. $

(3.28)

由(3.14)，(1.7)，(3.16)式和假设A2知

$ \begin{array}{l} {q_k}(0) - {q_k}({s_k}) \ge \frac{1}{2}\left\| {{g_k}} \right\|\min \{ {\Delta _k}, \frac{{\left\| {{g_k}} \right\|}}{{\left\| {{B_k}} \right\|}}\} \ge \frac{1}{2}\varepsilon \min \{ {R_\mu }({r_k})\frac{{\left\| {B_k^{ - 1}} \right\|\left\| {{g_k}} \right\|}}{{|1 + b_k^TB_k^{ - 1}{g_k}|}}, \frac{\varepsilon }{{{\delta _1}}}\} \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge \frac{1}{2}\varepsilon \min \{ {R_\mu }({r_k})\frac{{\left\| {{g_k}} \right\|}}{{|1 + b_k^TB_k^{ - 1}{g_k}|\left\| {{B_k}} \right\|}}, \frac{\varepsilon }{{{\delta _1}}}\} \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge \frac{1}{2}\varepsilon \min \{ {R_\mu }({r_k})\frac{\varepsilon }{{(1 - {\delta _3}{\delta _2}\lambda ){\delta _1}}}, \frac{\varepsilon }{{{\delta _1}}}\} . \end{array} $

(3.29)

由(3.28) 和(3.29)式知

$ \lim \limits_{k\rightarrow \infty} R_{\mu}(r_{k})=0. $

又$k\in I$时，有$r_{k}\geq\mu$，由定义1.1和定理1.1知$R_{\mu}(r_{k})\geq1+\gamma_{2}>1, \forall k\in I$，这与(3.27) 矛盾.因此定理成立.

首先给出三个假设：

A4:算法(CSATR)产生的点列$\{x_{k}\}$满足$\lim \limits_{k\rightarrow \infty} x_{k}=x^{\ast}$，$\lim \limits_{k\rightarrow \infty} \|g_{k}\|=\|g^{\ast}\|=0$，且$\nabla^{2}f(x^{\ast})$正定.

A5:如果$\frac{\|B_{k}^{-1}g_{k}\|}{|1+b_{k}^{T}B_{k}^{-1}g_{k}|}\leq\Delta_{k}$，则$s_{k}=-\frac{B_{k}^{-1}g_{k}}{1+b_{k}^{T}B_{k}^{-1}g_{k}}$.

A6:算法(CSATR)产生的点列$\{x_{k}\}$及$\{B_{k}\}$满足

$ \lim \limits_{k\rightarrow \infty} \frac{\|(B_{k}-\nabla^{2}f(x_{k})S_{s}\|}{\|S_{s}\|}=0. $

定理4.1  设$\{x_{k}\}$是由算法(CSATR)产生的点列且满足假设A1-A5，则点列$\{x_{k}\}$超线性收敛于$x^{\ast}$.

证  由假设A4知$\exists W>w>0$使得$\forall x\in D =\{x|\|x-x^{\ast}\|\leq\triangle\}$ (其中$\triangle$为一个很小的常数)时，有

$ w\|y\|^{2}\leq y^{T}\nabla^{2}f(x)y\leq W\|y\|^{2}, \forall y\in R^{n}. $

且存在充分大的正整数$k_{0}$，使得$\forall k\geq k_{0}$时，有$x_{k}\in D$.

由Taylor展开式和假设A4知，当$\forall k\geq k_{0}$时，有

$ \frac{1}{2}w\|x_{k}-x^{\ast}\|^{2}\leq f_{k}-f(x^{\ast})\leq \frac{1}{2}W\|x_{k}-x^{\ast}\|^{2}, $

(4.1)

且

$ w\|x_{k}-x^{\ast}\|\leq \|g_{k}\|\leq W\|x_{k}-x^{\ast}\|. $

(4.2)

下证对充分大的$k\geq k_{0}$，存在常数$c_{1}$使得

$ q_{k}(0)-q_{k}(s_{k})\geq c_{1}\|s_{k}\|^{2}. $

(4.3)

由(3.14)，(3.15)式和假设A2知对充分大的$k$，有

$ \begin{array}{l} {q_k}(0) - {q_k}({s_k}) \ge \frac{1}{2}\left\| {{g_k}} \right\|\min \{ {\Delta _k}, \frac{{\left\| {{g_k}} \right\|}}{{\left\| {{B_k}} \right\|}}\} \ge \frac{1}{2}\frac{{\left\| {{s_k}} \right\|}}{{{c_0}}}\min \{ \left\| {{s_k}} \right\|, \frac{{\left\| {{s_k}} \right\|}}{{{c_0}{\delta _1}}}\} \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge \frac{1}{{2{c_0}}}{\left\| {{s_k}} \right\|^2}\min \{ 1, \frac{1}{{{c_0}{\delta _1}}}\} . \end{array} $

取$c_{1}=\frac{1}{2 c_{0}}\min\{1, \frac{1}{c_{0}\delta_{1}}\}$，于是(4.2) 成立.

下证当$k$充分大时，有$r_{k}\geq\mu$.

由Taylor展开式和假设A6知

$ \begin{array}{l} \;\;\;f({x_k}) - f({x_k} + {s_k}) - {q_k}(0) - {q_k}({s_k})\\ = f({x_k}) - f({x_k} + {s_k}) + \frac{{g_k^T{s_k}}}{{1 + b_k^T{s_k}}} + \frac{1}{2}\frac{{s_k^T{B_k}{s_k}}}{{{{(1 + b_k^T{s_k})}^2}}}\\ = - g_k^T{s_k} - \frac{1}{2}s_k^T{\nabla ^2}f({x_k}){s_k} + o{(\left\| {{s_k}} \right\|)^2} + g_k^T{s_k}[1 + O{(\left\| {{s_k}} \right\|)^2}] + \frac{1}{2}s_k^T{B_k}{s_k}[1 + o{(\left\| {{s_k}} \right\|)^2}]\\ = \frac{1}{2}s_k^T[{B_k}-{\nabla ^2}f({x_k})]{s_k} + o({\left\| {{s_k}} \right\|^2}). \end{array} $

(4.4)

由(4.3)和(4.4)式知

$ |\frac{f(x_{k})-f(x_{k}+s_{k})}{q_{k}(0)-q_{k}(s_{k})}-1|=|\frac{f(x_{k})-f(x_{k}+s_{k})-(q_{k}(0)-q_{k}(s_{k})}{q_{k}(0)-q_{k}(s_{k})}-1|\leq\frac{o(\|s_{k}\|^{2})}{c_{1}\|s_{k}\|^{2}} $

因此

$ \frac{f(x_{k})-f(x_{k}+s_{k})}{q_{k}(0)-q_{k}(s_{k})}\rightarrow1, k\rightarrow\infty. $

于是当$k$充分大时，有$r_{k}\geq\mu$.当$r_{k}\geq\mu$时，由(1.5)式知$R_{\mu}(r_{k})>1.$于是

$ \Delta_{k}=R_{\mu}(r_{k})\frac{\|B_{k}^{-1}\|\|g_{k}\|}{|1+b_{k}^{T}B_{k}^{-1}g_{k}|}> \frac{\|B_{k}^{-1}\|\|g_{k}\|}{|1+b_{k}^{T}B_{k}^{-1}g_{k}|}\geq\frac{\|B_{k}^{-1}g_{k}\|}{|1+b_{k}^{T}B_{k}^{-1}g_{k}|} $

则由假设A5知

$ s_{k}=-\frac{B_{k}^{-1}g_{k}}{1+b_{k}^{T}B_{k}^{-1}g_{k}} $

于是有

$ g_{k}+B_{k}s_{k}-b_{k}^{T}B_{k}^{-1}g_{k}B_{k}s_{k}=0. $

(4.5)

由算法(CSATR)步4及引理3.6知当$k$充分大时，有

$ s_{k}=x_{k+1}-x_{k}. $

(4.6)

由(4.6)，(4.1)，(4.2) 及$\{f_{k}\}$单调递减知

$ \begin{array}{l} \left\| {{s_k}} \right\| \le \left\| {{x_k} - {x^ * }} \right\| + \left\| {{x_{k + 1}} - {x^ * }} \right\| \le \left\| {{x_k} - {x^ * }} \right\| + \sqrt {\frac{{2({f_{k + 1}} - f({x^ * }))}}{w}} \\ \;\;\;\;\;\;\; \le \left\| {{x_k} - {x^ * }} \right\| + \sqrt {\frac{{2({f_k} - f({x^ * }))}}{w}} \le (1 + \sqrt {\frac{W}{w}} )\frac{{\left\| {g({x_k})} \right\|}}{w}. \end{array} $

(4.7)

由Taylor展开式知

$ g_{k+1}=g_{k}+\nabla^{2}f(x_{k})s_{k}+O(\|s_{k}\|^{2}). $

(4.8)

由(4.5) 和(4.8)式知

$ \begin{array}{l} \frac{{\left\| {{g_{k + 1}}} \right\|}}{{\left\| {{s_k}} \right\|}} = \frac{{\left\| {{g_{k + 1}} - {g_k} - {B_k}{s_k} + b_k^TB_k^{ - 1}{g_k}{B_k}{s_k}} \right\|}}{{\left\| {{s_k}} \right\|}}\\ \;\;\;\;\;\;\;\;\;\;\; \le \frac{{\left\| {{g_{k + 1}} - {g_k} - {B_k}{s_k}} \right\| + \left\| {b_k^T} \right\|\left\| {B_k^{ - 1}} \right\|\left\| {{g_k}} \right\|\left\| {{B_k}} \right\|\left\| {{s_k}} \right\|}}{{\left\| {{s_k}} \right\|}}\\ \;\;\;\;\;\;\;\;\;\;\; = \frac{{\left\| {{g_{k + 1}} - {g_k} - {B_k}{s_k}} \right\|}}{{\left\| {{s_k}} \right\|}} + \left\| {b_k^T} \right\|\left\| {B_k^{ - 1}} \right\|\left\| {{g_k}} \right\|\left\| {{B_k}} \right\|\\ \;\;\;\;\;\;\;\;\;\;\; \le \frac{{\left\| {{\nabla ^2}f({x_k}) - {B_k}){s_k}} \right\|}}{{\left\| {{s_k}} \right\|}} + \frac{{O({{\left\| {{s_k}} \right\|}^2})}}{{\left\| {{s_k}} \right\|}} + {\delta _3}{\delta _2}{\delta _1}\left\| {{g_k}} \right\|. \end{array} $

(4.9)

由(4.9)式, 假设A6和假设A4知

$ \frac{\|g_{k+1}\|}{\|s_{k}\|}\rightarrow 0, k\rightarrow\infty. $

(4.10)

由(4.7)式知

$ \frac{\|g_{k+1}\|}{\|g_{k}\|}=\frac{\|g_{k+1}\|}{\|s_{k}\|}\cdot\frac{\|s_{k}\|}{\|g_{k}\|} \leq\frac{1}{w}(1+\sqrt{\frac{W}{w}})\cdot\frac{\|g_{k+1}\|}{\|s_{k}\|}. $

(4.11)

由(4.11) 和(4.10)式知

$ \lim \limits_{k\rightarrow \infty}\frac{\|g_{k+1}\|}{\|g_{k}\|}=0. $

(4.12)

由(4.2)式和假设A4知

$ w\|x_{k+1}-x^{\ast}\|\leq\|g_{k+1}\|, $

(4.13)

$ \|g_{k}\|\leq W\|x_{k}-x^{\ast}\|. $

(4.14)

由(4.13) 和(4.14)式知

$ 0\leq\frac{w\|x_{k+1}-x^{\ast}\|}{W\|x_{k}-x^{\ast}\|}\leq\frac{\|g_{k+1}\|}{\|g_{k}\|}. $

(4.15)

由(4.15) 和(4.12)式知

$ \lim \limits_{k\rightarrow \infty}\frac{\|x_{k+1}-x^{\ast}\|}{\|x_{k}-x^{\ast}\|}=0. $

故$\{x_{k}\}$超线性收敛于$x^{\ast}$.

这一部分对算法(CSATR)进行了数值试验.求解信赖域子问题(1.6) 采用文[12]中的算法3.1.$B_{k}$和$b_{k}$的修正用文[12]公式进行修正. $R-$函数取为

$ {R_\mu }({r_k}) = \left\{ \begin{array}{l} \frac{2}{\pi }(M - 1 - {\gamma _2})\arctan ({r_k} - \mu ) + (1 + {\gamma _2}), {r_k} \ge \mu ;\\ (1 - {\gamma _1} - \beta )({e^{{r_k} - \mu }} + \frac{\beta }{{1 - {\gamma _1} - \beta }}), \;\;\;\;\;\;\;\;\;\;\;\;{r_k} < \mu . \end{array} \right. $

算法(CSATR)中的参数选取如下: $\mu=0.25, \gamma_{1}=\gamma_{2}=0.15, \beta=0.1, M=5, \alpha=0.5, \Delta_{0}=1, b_{0}=0, B_{0}=I$ (单位矩阵).测试问题取自文献[14]和文献[15]>，选取的初始点$x_{0}$均与原文献相同.算法在Matlab7.0环境下编制程序运行.实验结果如表 1.在表 1中$k, k_{f}, k_{g}$分别表示迭代次数，函数值计算次数和梯度值计算次数.终止准则为$\varepsilon=10^{-4}$.

从由表 1可以看出：对一些函数，迭代次数，函数值计算次数及梯度值计算次数都是比较少的，因此算法(CSATR)是一种有效的算法.