考虑无约束优化问题

$\begin{equation}\min\limits _{x\in R^{n}}f(x), \end{equation}$

(1.1)

其中$f(x):R^{n}\longrightarrow R$是连续可微函数.信赖域方法是一类数值计算方法, 其具有较好的可靠性和强收敛性, 因此, 受到了许多研究者的关注.信赖域方法是一种迭代的方法, 其基本思想是, 每次迭代需求解信赖域子问题

$\begin{equation}\min\varphi_{k}(d)=g_{k}^{T}d+\frac{1}{2}d^{T}B_{k}d {\hbox{s.t.}} \|d\|\leq\Delta_{k}, \end{equation}$

(1.2)

其中$g_{k}=\nabla f(x_{k})$; $B_{k}\in R^{n\times n}$是函数$f(x)$在$x_{k}$处的Hessian矩阵或其近似矩阵; $\Delta_{k}>0$是信赖域半径, $\|.\|$是$R^{n}$中Euclid范数.目前BFGS方法是拟牛顿方法中求解无约束最优化问题(1.1) 的重要方法之一^[4].

针对著名的BFGS校正公式:

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

(1.3)

其中$s_{k}=x_{k+1}-x_{k}$, $y_{k}=g_{k+1}-g_{k}$, $g_{k}$和$g_{k+1}$分别是$f(x)$在$x_{k}$和$x_{k+1}$出的梯度值.文献[1-3]给出一些修改的BFGS方法及其收敛性分析.

文献[3]中Li和Fukashima给出一个修改的BFGS校正公式

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

(1.4)

其中$y_{k}^{*}=y_{k}+t_{k}\|\nabla f(x_{k})\|s_{k}$, $y_{k}=\nabla f(x_{k+1})-\nabla f(x_{k})$, ${t_k} = C + \max \{ {0, - \frac{{{y_k}^T{s_k}}}{{{{\| {{s_k}} \|}^2}}}} \}{\| {\nabla f({x_k})} \|^{ - 1}},$ $C>0$是一个常数.

文献[5]在式$(1.3)$基础上引入可调整的参数$\theta$:给出了一个修改的BFGS公式

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

(1.5)

其中$y_{k}^{*}=\theta y_{k}+(1-\theta)t_{k}\|\nabla f(x_{k})\|s_{k},\theta\in[0,1]$, $y_{k}=\nabla f(x_{k+1})-\nabla f(x_{k})$,

${t_k} = C + \max \{ {0, - \frac{{{y_k}^T{s_k}}}{{{{\| {{s_k}}\|}^2}}}}\}{\| {\nabla f({x_k})} \|^{ - 1}},$

$C>0$是一个常数.

受上面公式启发.本文作如下修改:

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

(1.6)

这里$y_{k}^{*}=\alpha y_{k}+\beta t_{k}\|\nabla f(x_{k})\|s_{k}$, $\alpha,\beta\in[0,1]$, $y_{k}=\nabla f(x_{k+1})-\nabla f(x_{k})$, ${t_k} = C + \max \{ {0, - \frac{{{y_k}^T{s_k}}}{{{{\| {{s_k}} \|}^2}}}} \}{\| {\nabla f({x_k})} \|^{ - 1}},$ $C>0$是一个常数.

显然, 当$\alpha=1,\beta=0$时, 式$(1.6)$退化为式$(1.3)$; 当$\alpha=1,\beta=1$时, 式$(1.6)$退化为式$(1.4)$; 当$\alpha+\beta=1$时, 式$(1.6)$退化为式$(1.5)$.

众所周知, 在式(1.3) 中当$y_{k}^{T}s_{k}>0$时, $B_{k+1}$继承$B_{k}$的正定性.所以当${y_{k}^{*}}^{T}s_{k}>0$时, 利用$(1.6)$式更新$B_{k+1}$, 反之不更新.本文借鉴文献[5-8]的思想, 将$(1.6)$式与信赖域算法相结合, 给出一个新的BFGS信赖域算法, 该算法能够保证修正矩阵的正定性, 同时在一定条件下证明了算法的全局收敛性.

通过求解信赖域子问题$(1.2)$得$d_{k}$, 同时定义实际下降量$Ared_{k}=f(x_{k})-f(x_{k}+d_{k}); $预估计下降量$Pred_{k}=\varphi_{k}(0)-\varphi_{k}(d_{k}); $定义比值$r_{k}=\frac{Ared_{k}}{Pred_{k}}.$

算法$1$ 

步骤0 取$\Delta_{m}>0$为迭代过程中最大的信赖域半径, $x_{0}\in R^{n}$, $B_{0}\in R^{n\times n}$为对称正定矩阵, $\varepsilon\geq0$, $0<\Delta_{0}<\Delta_{m}$, $0<\eta<1$, $\lambda_{2}>1>\lambda_{1}>0$, $k=0$;

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

步骤2 求解子问题$(1.2)$得$d_{k}$;

步骤3 计算$r_{k}=\frac{Ared_{k}}{Pred_{k}}.$更新

$\begin{eqnarray}&& {x_{k + 1}} = \left\{ \begin{array}{l} {x_k} + {d_k},{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {r_k} > 0, \\ {x_k},\quad \quad {\kern 1pt} {\kern 1pt} {r_k} \le 0, \end{array} \right. {\Delta _{k + 1}} = \left\{ \begin{array}{l} \min \left\{ {{\lambda _2}{\Delta _k},{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\Delta _m}} \right\}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} ,{r_k} \ge \eta, \\ {\lambda _1}{\Delta _k}{\kern 1pt} ,{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {r_k} < \eta; \\ \end{array} \right.\end{eqnarray}$

(2.1)

步骤4 如果$r_{k}>0$, 利用式$(1.6)$修正$B_{k}$产生$B_{k+1}$, 令$k:=k+1$, 转步$1$.

为证明算法的全局收敛性, 现给出如下假设H

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

H$_{2} $函数$f(x)$在水平集$L(x_{0})$上二阶连续可微有下界;

H$_{3}$ $\{B_{k}\}$一致有界, 即存在$M>0$使得对任意的$k$有$\|B_{k}\|\leq M$.

引理3.1 ^[4]设$d_{k}$是信赖域子问题$(1.2)$的解, 则有

$Pred_{k}=\varphi_{k}(0)-\varphi_{k}(d_{k}) \geq\frac{1}{2}\|g_{k}\|\min\{\Delta_{k},\frac{\|g_{k}\|}{\|B{k}\|}\}.$

引理3.2 ${y_{k}^{*}}^{T}s_{k} > 0.$

证 由$(1.6)$式得到

$\begin{eqnarray*}{y_{k}^{*}}^{T}s_{k}&=&(\alpha y_{k}+\beta t_{k}\|\nabla f(x_{k})\|s_{k})^{T}s_{k} =\alpha y_{k}^{T}s_{k}+\beta t_{k}\|\nabla f(x_{k})\|{s_{k}}^{T}s_{k}\\ &=&\alpha{y_{k}}^{T}s_{k}+\beta t_{k}\|\nabla f(x_{k})\|\|s_{k}\|^{2} \geq\beta C\|\nabla f(x_{k})\|\|s_{k}\|^{2}>0.\end{eqnarray*}$

显然, 当$B_{k}$正定时, $B_{k+1}$也正定.

定理3.3 (收敛性定理)若假设H$_{1}$, H$_{2}$, H$_{3}$均成立, 由算法$1$产生的点列为${x_{k}}$, 则

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

(3.1)

证 由$r_{k}$定义知

$\begin{equation} |r_{k}-1| =|\frac{f_{k}-f(x_{k}+d_{k})}{\varphi_{k}(0)-\varphi_{k}(d_{k})}-1| =|\frac{\varphi_{k}(d_{k})-f(x_{k}+d_{k})+f_{k}}{\varphi_{k}(d_{k})}|, \end{equation}$

(3.2)

利用Taylor展开式$f(x_{k}+d_{k})=f_{k}+g_{k}^{T}d_{k}+\displaystyle\int_{0}^{1}d_{k}^{T}(g(x_{k}+\tau d_{k})-g_{k})d_{\tau}.$所以在$\Delta_{k}>0$充分小时, 有

$\begin{eqnarray} |\varphi_{k}(d_{k})-f(x_{k}+d_{k})+f_{k}| &=&|\frac{1}{2}d_{k}^{T}B_{k}d_{k}-\int_{0}^{1}d_{k}^{T}(g(x_{k}+\tau d_{k})-g_{k})d\tau\nonumber\\ &\leq& \frac{M}{2}\|d_{k}\|^{2}+o(\|d_{k}\|) \leq\frac{M}{2}\Delta_{k}^{2}+o(\Delta_{k}). \end{eqnarray}$

(3.3)

假若式$(3.1)$不成立, 则存在$\varepsilon_{0}>0$和$k_{0}$使得$\forall k\geq k_{0}$, 有$\|g_{k}\|\geq\varepsilon_{0}$, 由引理$3.1$, 对$k\geq k_{0}$, 有

$\begin{equation}{\varphi _k}(0) - {\varphi _k}({d_k}) = - {\varphi _k}({d_k}) \ge \frac{1}{2}\left\| {{g_k}} \right\|\min \left\{ {{\Delta _k},\frac{{\left\| {{g_k}} \right\|}}{{\left\| {{B_k}} \right\|}}} \right\} \ge \frac{1}{2}{\varepsilon _0}\min \left\{ {{\Delta _k},\frac{{{\varepsilon _0}}}{M}} \right\}, \end{equation}$

(3.4)

利用(3.2)--(3.4) 式得

$\begin{equation}\left| {{r_k} - 1} \right| \le \frac{{2(\frac{M}{2}{\Delta _k}^2 + \circ ({\Delta _k}))}}{{{\varepsilon _0}\min \left\{ {{\Delta _k},\frac{{{\varepsilon _0}}}{M}} \right\}}} = \frac{{{M_0}{\Delta _k}^2 + 2 \circ ({\Delta _k})}}{{\varepsilon 0\min \left\{ {{\Delta _k},\frac{{{\varepsilon _0}}}{M}} \right\}}} = \frac{{{M_0}{\Delta _k}^2 + \circ (2{\Delta _k})}}{{\varepsilon 0\min \left\{ {{\Delta _k},\frac{{{\varepsilon _0}}}{M}} \right\}}}.\end{equation}$

(3.5)

假若存在自然数列$N$的一个无穷子列$N_{0}$, 使得对$\forall k\in N_{0}$, 有$r_{k}\geq\eta$, 则对$k\in N_{0},k\geq k_{0}$, 由$(3.4)$及算法$1$步$3$中的(2.1) 式得

$\begin{equation}f_{k}-f_{k+1}\geq\eta[\varphi_{k}(0)-\varphi_{k}(d_{k})] \geq\frac{1}{2}\eta\varepsilon_{0}\min\{\Delta_{k},\frac{\varepsilon_{0}}{M}\}.\end{equation}$

(3.6)

由数列$\{f(x_{k})\}$单调不增有下界.故它有极限, 因此有$\lim\limits_{k\rightarrow\infty}(f_{k}-f_{k+1})=0$, 从而对充分大的$k$, 由(3.6) 式有

$\begin{equation}\lim\limits_{k\rightarrow\infty}\Delta_{k}=0.\end{equation}$

(3.7)

又由(3.5) 式, 有$\lim\limits_{k\rightarrow\infty}r_{k}=1.$据算法$1$, 对充分大的$k$应有$\Delta_{k+1}=\min\{\lambda_{2}\Delta_{k},\Delta_{m}\}\geq\Delta_{k}$, 这与式(3.7) 式矛盾, 因此, 对充分大的$k$, $r_{k}<\eta$, 在这种情况下, $\Delta_{k}$将以$\lambda_{1}$的比例压缩, 又得到$\lim\limits_{k\rightarrow\infty}\Delta_{k}=0.$这又与由$(3.5)$得出的$r_{k}\rightarrow1$时, $\Delta_{k+1}\geq\Delta_{k}$矛盾.所以前面的假设成立, 定理结论得证.