本文考虑无约束优化问题:

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

(1.1)

其中$ f:{R^n} \to R $是连续可微函数. 在众多的算法中, 共轭梯度法由于所需储存量小且收敛速度快, 因此被广泛用来求解大规模无约束优化问题.

共轭梯度法的基本迭代格式如下:

$ \begin{equation} {x_{k + 1}} = {x_k} + {\alpha _k}{d_k}, \end{equation} $

(1.2)

其中$ \alpha_k $是由Wolfe线搜索得到的第$ k $步步长; $ d_{k} $是第$ k $步的搜索方向, 其第$ k+1 $步迭代格式如下:

$ \begin{equation} {d_{k+1}} = \left\{ {\begin{array}{*{20}{c}} { - {g_{k+1}}, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;k = 0, }\\ { - {g_{k+1}} + {\beta _{k}}{d_{k}}, \;\;\;\;\;k \ge {\rm{1}}, } \end{array}} \right. \end{equation} $

(1.3)

其中$ g_{k+1}=\nabla f(x_{k+1}) $, $ \beta_{k} $是共轭参数.

共轭梯度法常见的Wolfe线搜索有: 标准Wolfe线搜索、强Wolfe线搜索、推广的Wolfe线搜索以及近似Wolfe线搜索. 本文采用强Wolfe线搜索以及近似Wolfe线搜索:

(1) 强Wolfe线搜索的步长$ \alpha_{k} $满足

$ \begin{equation} f({x_k} + {\alpha _k}{d_k}) \le f({x_k}) + \delta {\alpha _k}g_k^T{d_k}, \end{equation} $

(1.4)

$ \begin{equation} \left|g(x_{k}+\alpha_{k}d_{k})^{T}d_{k}\right|\leq-\sigma g_{k}^{T}d_{k}, \end{equation} $

(1.5)

其中$ 0<\delta<\sigma<1. $

(2) 近似Wolfe线搜索[1]的步长$ \alpha_{k} $满足

$ \begin{equation} g(x_{k}+\alpha_{k}d_{k})^{T}d_{k}\geq\sigma g_{k}^{T}d_{k}, \end{equation} $

(1.6)

$ \begin{equation} g(x_{k}+\alpha_{k}d_{k})^{T}d_{k}\leq(2\delta-1)g_k^{T}d_k, \end{equation} $

(1.7)

其中$ 0<\delta<\sigma<1 $.

共轭参数$ \beta_{k} $经典选取有Hestenes-Stiefel(HS) [2], Fletcher-Reeves(FR) [3], Polak-Ribière-Rolyak(PRP) [4, 5], Conjugate Descent(CD) [6], Liu-Storey(LS) [7]和Dai-Yuan (DY) [8]六种, 其具体表达式如下:

$ \beta _k^{HS} = \frac{{g_{k + 1}^T{y_k}}}{{d_k^T{y_k}}}; \; \; \; \; \beta _k^{FR} = \frac{{{{\left\| {{g_{k + 1}}} \right\|}^2}}}{{{{\left\| {{g_k}} \right\|}^2}}}; \; \; \; \; \beta _k^{PRP} = \frac{{g_{k + 1}^T{y_k}}}{{{{\left\| {{g_k}} \right\|}^2}}}; $

$ \beta _k^{CD} = - \frac{{{{\left\| {{g_{k + 1}}} \right\|}^2}}}{{g_k^T{d_k}}}; \; \; \beta _k^{LS} = - \frac{{g_{k + 1}^T{y_k}}}{{g_k^T{d_k}}}; \; \; \beta _k^{DY} = \frac{{{{\left\| {{g_{k + 1}}} \right\|}^2}}}{{d_k^T{y_k}}}. $

其中$ \|\cdot\| $表示为Euclidean范数, $ {y_k} = {g_{k + 1}} - {g_k} $. 当$ f $是一般连续可微函数或者适用非精确线搜索时, HS、PRP、LS三种方法数值试验效果较好, 但是理论性质较差; FR、CD、DY三种方法理论性质较好, 但是数值试验效果不理想. 为了获得理论收敛性和数值计算效果都更佳的共轭梯度方法, Touati-Ahmed和Storey [9]首次引入混合共轭梯度法, 将数值表现较好的PRP方法与理论收敛性较好的FR方法混合, 其参数如: $ \beta _k^{TS} = \max \{ 0, \min \{ \beta _k^{PRP}, \beta _k^{FR}\} \} . $混合共轭梯度法的提出, 使得共轭梯度方法的理论性质和数值试验都表现的更佳. 随后, 许多学者对混合共轭梯度法进一步进行研究, 见文献[10]、[11]、[12]、[13]等.

2008年, Neculai Andrei [14]为了同时利用HS方法数值试验效果好, DY方法理论性质好这样的优点, 提出了一种修正的混合共轭梯度算法, 其参数$ \beta _k^{HSDY} $是$ \beta _k^{HS} $和$ \beta _k^{DY} $的凸组合, 即:

$ \begin{equation} {\beta _k^{HSDY}} = (1 - {\vartheta _k})\beta _k^{HS} + {\vartheta _k}\beta _k^{DY}, \end{equation} $

(1.8)

其中$ {\vartheta _k} \in [0, 1] $. 注意到当$ {\vartheta _k}=0 $时, HSDY方法等价于HS方法; 当$ {\vartheta _k}=1 $时, HSDY方法等价于DY方法. 由(1.3)式可得:

$ \begin{equation} {d_{k + 1}} = - {g_{k + 1}} + \left( {{\rm{1 - }}{\vartheta _k}} \right){\frac{{g_{k + 1}^T{y_k}}}{{d_k^T{y_k}}}}{d_k} + {\vartheta _k}{\frac{{{{\left\| {{g_{k + 1}}} \right\|}^2}}}{{d_k^T{y_k}}}}{d_k}, \end{equation} $

(1.9)

将上式$ {d_{k + 1}} $记为$ {d_{k + 1}^{HD}} $. $ {\vartheta _k} $的计算方式是采用牛顿方向去逼近$ {d_{k + 1}^{HD}} $, 从而获得

$ \begin{equation} {\vartheta _k} = - \frac{{s_k^T{g_{k + 1}}}}{{g_k^T{g_{k + 1}}}}. \end{equation} $

(1.10)

Neculai Andrei证明了HSDY方法的收敛性, 其数值试验的结果比HS方法和DY方法都更有效.

2015年Zhifeng Dai [15]等对文献[14]中定理2和定理4进行修正, 并提出条件$ 0 < {c_1} \le {\theta _k} < 1 $可以被删除.

2020年Xiuyun Zheng [16]等对文献[14]中定理2和定理4和文献[15]中定理2.1和定理3.1进行了进一步修正, 并指出条件$ 0 < {c_1} \le {\theta _k} < 1 $不能被删除.

1977年perry [17]和1978年shanno [18]提出自调比无记忆BFGS方法:

$ \begin{equation} {d_{k + 1}} = - {H_{k + 1}}{g_{k + 1}}, \end{equation} $

(1.11)

$ \begin{equation} {H_{k + 1}} = \frac{1}{{{\tau _k}}}\left( {I - \frac{{{s_k}y_k^T + {y_k}s_k^T}}{{s_k^T{y_k}}}} \right) + \left( {1 + \frac{1}{{{\tau _k}}}\frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}} \right)\frac{{{s_k}s_k^T}}{{s_k^T{y_k}}}, \end{equation} $

(1.12)

即

$ \begin{equation} {d_{k + 1}} = - {g_{k + 1}} + \left[ {\frac{{g_{k + 1}^T{y_k}}}{{s_k^T{y_k}}} - \left( {{\tau _k} + \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}} \right)\frac{{g_{k + 1}^T{d_k}}}{{d_k^T{y_k}}}} \right]{s_k} + \frac{{g_{k + 1}^T{d_k}}}{{d_k^T{y_k}}}{y_k}. \end{equation} $

(1.13)

若删除(1.13)最后一项, 再取$ {\tau _k} = \dfrac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}} $, 则上述方法就退化到2005年Hager和Zhang [1]提出的共轭梯度法, 其共轭参数为:

$ \begin{equation} \beta_k^{\mathrm{N}}=\frac{g_{k+1}^{T}y_{k}}{d_{k}^{T}y_{k}}-\frac{2\|y_{k}\|^2g_{k+1}^{T}d_{k}}{(d_{k}^{T}y_{k})^2}. \end{equation} $

(1.14)

HSDY方法同时具有HS方法和DY方法各自的优点, 然而HSDY方法是利用牛顿方向去逼近$ {d_{k + 1}} $获得$ {\vartheta _k} $, 在这种情况下要求目标函数是二次可微并且对应的Hesse矩阵是正定的, 但是, 这样一来使得计算复杂、占用内存较大. 因此, 受Perry [17]和shanno [18]思想的启发, 本文提出如下策略计算$ {\vartheta _k} $:

用自调比无记忆BFGS去逼近搜索方向$ {d_{k + 1}} $, 即

$ \begin{equation} {d_{k + 1}} = - {g_{k + 1}} + \left[ {\frac{{g_{k + 1}^T{y_k}}}{{s_k^T{y_k}}} - \left( {{\tau _k} + \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}} \right)\frac{{g_{k + 1}^T{d_k}}}{{d_k^T{y_k}}}} \right]{s_k} + \frac{{g_{k + 1}^T{d_k}}}{{d_k^T{y_k}}}{y_k}. \end{equation} $

(2.1)

计算化简得

$ \begin{equation} {\vartheta _k^N}=-{\tau _k}{\alpha _k}\frac{d_k^T{g_{k+1}}}{{g_k^T{g_{k + 1}}}}= -{\tau _k}\frac{{s_k^T{g_{k+1}}}}{{g_k^T{g_{k + 1}}}}. \end{equation} $

(2.2)

其中, $ {\tau _k} $与Dai和Kou [19]文一致, 即

$ \begin{equation} \tau _k^1 = \min \left\{ {1, \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}} \right\}, \tau _k^2 = \min \left\{ {1, \frac{{s_k^T{y_k}}}{{{{\left\| {{s_k}} \right\|}^2}}}} \right\}. \end{equation} $

(2.3)

本文将参数$ \tau _k^1 $和$ \tau _k^2 $对应的方法分别记作HSDY1方法和HSDY2方法, 即

$ \begin{equation} \beta _k^{HSDY1} = (1{\rm{ + }}\tau _k^1\frac{{s_k^T{y_k}}}{{g_k^T{g_{k + 1}}}})\beta _k^{HS}{\rm{ - }}\tau _k^1\frac{{s_k^T{y_k}}}{{g_k^T{g_{k + 1}}}}\beta _k^{DY}, \end{equation} $

(2.4)

$ \begin{equation} \beta _k^{HSDY2} = (1{\rm{ + }}\tau _k^2\frac{{s_k^T{y_k}}}{{g_k^T{g_{k + 1}}}})\beta _k^{HS}{\rm{ - }}\tau _k^2\frac{{s_k^T{y_k}}}{{g_k^T{g_{k + 1}}}}\beta _k^{DY}. \end{equation} $

(2.5)

为方便后续讨论, 在此先介绍对一些目标函数的基本假设.

假设 (A) 水平集$ \mathcal{L}=\{x\in R^n \mid f(x)\leq f(x_1)\} $是有界的, 其中$ x_1\in R^n $为算法初始点, 即存在常数$ B>0 $, 使得

$ \begin{equation} \|x\|\leq B, \; \; \forall x\in \mathcal{L}. \end{equation} $

(3.1)

假设 (B) 目标函数$ f(x) $在水平集$ \mathcal{L} $的某些邻域$ \mathcal{N} $内是连续可微的, 且梯度函数$ g(x) $是Lipschitz连续的, 即存在常数$ L>0 $, 使得

$ \begin{equation} \|g(x)-g(y)\| \leq L\|x-y\|, \; \; \forall x, y\in \mathcal{N}. \end{equation} $

(3.2)

由假设(A)-(B)可知, 存在常数$ \bar{\gamma}\geq0 $, 使得

$ \begin{equation} \|g(x)\|\leq\bar{\gamma}, \; \; \forall x\in \mathcal{L}. \end{equation} $

(3.3)

引理3.1    若$ f(x) $对于满足假设(A)-(B). 考虑具有(1.2)-(1.3)形式的共轭梯度法, 其中$ d_{k} $是一个下降方向即满足$ g_{k+1}^{T}d_{k+1}\leq0 $, $ \alpha_{k} $满足强Wolfe条件(1.4)和(1.5), 则有

$ \begin{equation} \sum\limits_{k\geq1}\frac{(g_{k}^{T}d_{k})^2}{\|d_{k}\|^2}<\infty. \end{equation} $

(3.4)

引理3.1由Zoutendijk [20]和Wolfe [21, 22] 共同证明, 称(3.4)式为Zoutendijk条件.

下面的定理3.1和定理3.2证明了HSDY1方法和HSDY2方法的下降性.

定理3.1    假设(A)-(B)成立. 考虑HSDY1共轭梯度法, 对任意的$ k\geq0 $, 若$ d_k^T{y_k} \neq 0 $, 则有

$ \begin{equation} g^T_{k + 1}{d_{k + 1}} \le 0. \end{equation} $

(3.5)

证    由(1.3)可知, 当$ k=0 $时, 有$ g^{T}_{1}d_{1}=-\|g_{1}\|^{2} $. 当$ k\geq1 $时, 我们可以得到

$ \begin{eqnarray} g_{k + 1}^T{d_{k + 1}} &=& - {\left\| {{g_{k + 1}}} \right\|^2} + {\beta _k^{HSDY1}}g_{k + 1}^T{d_k} \\ &=&- {\left\| {{g_{k + 1}}} \right\|^2} + \left( {1 + {\tau_k^1}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}} \right)\frac{{g_{k + 1}^T{d_k}g_{k + 1}^T{y_k}}}{{y_k^T{d_k}}} - {\tau_k^1}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\frac{{g_{k + 1}^T{d_k}{{\left\| {{g_{k + 1}}} \right\|}^2}}}{{y_k^T{d_k}}}. \end{eqnarray} $

(3.6)

接下来对$ {\tau ^1} $进行分类讨论:

当$ {\tau ^1} = \min \left\{ {1, \frac{{{{\left\| y_{k} \right\|}^2}}}{{s_k^T{y_k}}}} \right\}=1 $时, 此时与HSDY方法的证明过程一致, 详见[14]、[15]、[16].

当$ \tau^{1} = \min \left\{ {1, \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}} \right\}={\frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}} $时, 则有

$ \begin{align} g_{k + 1}^T{d_{k + 1}} =& - {\left\| {{g_{k + 1}}} \right\|^2} + \left( {1 + \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}} \right)\frac{{g_{k + 1}^T{d_k}g_{k + 1}^T{y_k}}}{{y_k^T{d_k}}} \\ &- \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}\frac{{g_{k + 1}^T{s_k}g_{k + 1}^T{d_k}}}{{g_k^T{g_{k + 1}}}}\frac{{{{\left\| {{g_{k + 1}}} \right\|}^2}}}{{y_k^T{d_k}}} \\ =&- {\left\| {{g_{k + 1}}} \right\|^2}\left( {1 + \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}}} \right) + \left( {1 + \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}} \right){\left\| {{g_{k + 1}}} \right\|^2} \\ =&- {\left\| {{g_{k + 1}}} \right\|^2}\left( {\frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}} - \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}} \right) \\ =&- {\left\| {{g_{k + 1}}} \right\|^2}\frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\left( {\frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}} - 1} \right). \end{align} $

(3.7)

在(1.4)-(1.5)式下有$ s_k^T{y_k} > 0 $成立, 所以

$ \begin{equation} \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}} > 0. \end{equation} $

(3.8)

由[14]中证明可得

$ \begin{equation} \frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}} < 0 \end{equation} $

(3.9)

以及

$ \begin{equation} {\frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}} - 1< 0}. \end{equation} $

(3.10)

再由(3.8)、(3.9)和(3.10)可知

$ - \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\left( {\frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}} - 1} \right) \le 0. $

即$ {g_{k + 1}^T{d_{k + 1}} \le {\rm{0}}} $成立, 故HSDY1方法是具有下降性的. 证毕.

定理3.2    假设(A)-(B)成立. 考虑HSDY2共轭梯度法, 对任意的$ k\geq0 $, 若$ d_k^T{y_k} \neq 0 $, 则有

$ \begin{equation} g^{T}_{k+1}d_{k+1}\le 0. \end{equation} $

(3.11)

注3.1    其证明方法与定理3.1一致, 需要注意的是在(1.4)-(1.5)式下, 仍然可以得到$ \frac{{s_k^T{y_k}}}{{{{\left\| {{s_k}} \right\|}^2}}} > 0. $从而HSDY2方法是具有下降性的.

下面定理3.3和定理3.4证明了HSDY1方法和HSDY2方法的充分下降性.

定理3.3    假设(A)-(B)成立. 考虑HSDY1共轭梯度法, 若$ d_k^T{y_k} \neq 0 $成立, 则存在一自适应参数$ c_{1}>0 $使

$ \begin{equation} g^T_{k + 1}{d_{k + 1}} \leq - {{\rm{c}}_1}{\left\| {{g_{k + 1}}} \right\|^2}, \end{equation} $

(3.12)

其中

$ {c_1} = \left\{ {\begin{array}{*{20}{c}} {1, \quad\qquad\qquad \quad k = 1}, \\ {\frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\left( {\frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}}} \right) - 1, {\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} k > 1{\rm{且}}{\tau ^1}{\rm{ = }}\frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}}, \\ {\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\left( {\frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}}} \right) - 1, {\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} k > 1{\rm{且}}{\tau ^1}{\rm{ = 1}}}. \end{array}} \right. $

证    由(1.3)可知, 当$ k=0 $时, 有$ g^{T}_{1}d_{1}=-\|g_{1}\|^{2} $. 此时$ c_{1}= 1. $

当$ k\geq1 $时, 由(3.9)式可知

$ \begin{eqnarray} g_{k + 1}^T{d_{k + 1}}=- {\left\| {{g_{k + 1}}} \right\|^2}\frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\left( {\frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}} - 1} \right). \end{eqnarray} $

(3.13)

由(3.5), (3.10)和(3.12)式可知, 存在一自适应参数$ c_{1}>0 $使得

$ \begin{eqnarray} c_{1} = \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\left( { \frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}}}-1 \right). \end{eqnarray} $

(3.14)

又或者当$ {\tau ^1} = \min \left\{ {1, \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}} \right\} = 1 $时, 有

$ \begin{eqnarray} g_{k + 1}^T{d_{k + 1}} = - {\left\| {{g_{k + 1}}} \right\|^2}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\left( {\frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}} - 1} \right). \end{eqnarray} $

(3.15)

由(3.5), (3.10)和(3.12)式可知, 存在一自适应参数$ c_{1}>0 $使得

$ \begin{eqnarray} c_{1} = \frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\left( {\frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}} - 1} \right). \end{eqnarray} $

(3.16)

所以HSDY1方法是具有充分下降性. 证毕.

定理3.4  假设(A)-(B)成立. 考虑HSDY2共轭梯度法, 若$ d_k^T{y_k} \neq 0 $成立, 则存在一自适应参数$ c_{2}>0 $使

$ \begin{equation} g^T_{k + 1}{d_{k + 1}} \leq - c_{2}{\left\| {{g_{k + 1}}} \right\|^2}, \end{equation} $

(3.17)

其中

$ {c_2} = \left\{ {\begin{array}{*{20}{c}} {1, \quad\qquad\qquad \quad k = 1, }\\ {\frac{{s_k^T{y_k}}}{{{{\left\| {{s_k}} \right\|}^2}}}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\left( {\frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}} - 1} \right), \quad k > 1\text{且}{\tau ^2}{\rm{ = }}\frac{{s_k^T{y_k}}}{{{{\left\| {{s_k}} \right\|}^2}}}, }\\ {\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\left( {\frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}}} \right) - 1, \quad k > 1\text{且}{\tau ^2}{\rm{ = 1}}{\rm{.}}} \end{array}} \right. $

证    由(1.3)式, 当$ k=0 $时, 有$ g^{T}_{1}d_{1}=-\|g_{1}\|^{2} $, 此时$ c_{2}=1. $

当$ k\geq1 $时, 由(3.9)式可知:

$ \begin{eqnarray} g_{k + 1}^T{d_{k + 1}}= -g_{k + 1}^T{d_{k + 1}} = - {\left\| {{g_{k + 1}}} \right\|^2}\frac{{s_k^T{y_k}}}{{{{\left\| {{s_k}} \right\|}^2}}}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\left( {\frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}} - 1} \right). \end{eqnarray} $

(3.18)

由(3.10), (3.11)和(3.17)式可知, 存在一自适应参数$ c_{2}>0 $使得

$ \begin{eqnarray} {c_2} = \frac{{s_k^T{y_k}}}{{{{\left\| {{s_k}} \right\|}^2}}}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\left( {\frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}} - 1} \right). \end{eqnarray} $

(3.19)

又或者当$ {\tau ^2} = \min \left\{ {1, \frac{{s_k^T{y_k}}}{{{{\left\| {{s_k}} \right\|}^2}}}} \right\} = 1 $时, 则有

$ \begin{eqnarray} g_{k + 1}^T{d_{k + 1}} = - {\left\| {{g_{k + 1}}} \right\|^2}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\left( {\frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}} - 1} \right). \end{eqnarray} $

(3.20)

由(3.10), (3.11)和(3.17)式可知, 存在一自适应参数$ c_{2}>0 $使得

$ \begin{eqnarray} c_{2} = \frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\left( {\frac{{g_{k + 1}^T{d_k}}}{{y_k^T{d_k}}} - 1} \right). \end{eqnarray} $

(3.21)

所以HSDY2方法是具有充分下降性. 证毕.

定理3.1–定理3.4证明了HSDY1和HSDY2方法的下降性和充分下降性. 接下来, 我们将证明HSDY1和HSDY2方法对一致凸函数具有强收敛性, 再证明HSDY1和HSDY2方法对一般函数具有全局收敛性.

我们先给出一致凸函数的等价定义: 如果存在常数$ \mu>0 $, 使得

$ \begin{equation} (\nabla f(x)-\nabla f(y))^{T}(x-y)\geq \mu\|x-y\|^2, \; \; \forall x, y\in \mathcal{L}. \end{equation} $

(4.1)

定理4.1    假设(A)-(B)成立. 考虑HSDY1共轭梯度法, 其中步长$ {\alpha _k} $满足强Wolfe线搜索(1.4)和(1.5). 若$ f $为一致凸函数, 则有

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

(4.2)

证    由Lipschitze条件(3.2)式以及$ f $为一致凸函数, 有

$ \begin{equation} \|y_{k}\|\leq L\|s_{k}\|, \end{equation} $

(4.3)

$ \begin{equation} d_{k}^{T}y_{k}\geq \mu\|d_{k}\|\|s_{k}\|. \end{equation} $

(4.4)

当$ {\tau ^1} = \min \left\{ {1, \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}} \right\} = 1 $时, 由(1.3), (4.3) 和(4.4), 利用三角不等式及柯西不等式有

$ \begin{eqnarray} \left| {{\beta _k^{HSDY1}}} \right| &=& \left| {\left( {1 - {\vartheta _k^{N}}} \right){\beta ^{HS}} + {\vartheta _k^{N}}{\beta ^{DY}}} \right| \\ &=& \left| {\left( {1 + \frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}} \right)\frac{{g_{k + 1}^T{y_k}}}{{y_k^T{d_k}}} - \frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\frac{{{{\left\| {{g_{k + 1}}} \right\|}^2}}}{{y_k^T{d_k}}}} \right| \\ &=& \left| {\frac{{g_{k + 1}^T{y_k}}}{{y_k^T{d_k}}} + \frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\left( {\frac{{g_{k + 1}^T{y_k}}}{{y_k^T{d_k}}} - \frac{{{{\left\| {{g_{k + 1}}} \right\|}^2}}}{{y_k^T{d_k}}}} \right)} \right| \\ &=& \left| {\frac{{g_{k + 1}^T{y_k}}}{{y_k^T{d_k}}} - \frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\frac{{g_{k + 1}^T{g_k}}}{{y_k^T{d_k}}}} \right| \\ &\leq& \left| {\frac{{g_{k + 1}^T{y_k}}}{{y_k^T{d_k}}} + \frac{{g_{k + 1}^T{s_k}}}{{y_k^T{d_k}}}} \right| \leq \left| {\frac{{\left( {L + 1} \right)\left\| {{g_{k + 1}}} \right\|\left\| {{s_k}} \right\|}}{{\mu \left\| {{d_k}} \right\|\left\| {{s_k}} \right\|}}} \right| \leq \frac{{\left( {L + 1} \right)\left\| {{g_{k + 1}}} \right\|}}{{\mu \left\| {{d_k}} \right\|}}, \end{eqnarray} $

(4.5)

则

$ \begin{eqnarray} \left\| {{d_{k + 1}}} \right\| \le \left\| {{g_{k + 1}}} \right\| + \left| {{\beta _k}} \right|\left\| {{d_k}} \right\| \leq \left\| {{g_{k + 1}}} \right\| + \frac{{\left( {L + 1} \right)\left\| {{g_{k + 1}}} \right\|}}{{\mu \left\| {{d_k}} \right\|}}\left\| {{d_k}} \right\| \leq \left( {1 + \frac{{\left( {L + 1} \right)}}{\mu }} \right)\left\| {{g_{k + 1}}} \right\|. \end{eqnarray} $

(4.6)

当$ \tau^{1} = \min \left\{ {1, \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}} \right\}={\frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}} $时, 由(1.3), (4.3)和(4.4), 利用三角不等式及柯西不等式有

$ \begin{eqnarray} \left| {\beta _k^{HSDY1}} \right| &=& \left| {\left( {1 - \vartheta _k^N} \right){\beta ^{HS}} + \vartheta _k^N{\beta ^{DY}}} \right| \\ &=& \left| {\left( {1 + \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}} \right)\frac{{g_{k + 1}^T{y_k}}}{{y_k^T{d_k}}} - \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}\frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\frac{{{{\left\| {{g_{k + 1}}} \right\|}^2}}}{{y_k^T{d_k}}}} \right| \\ &=& \left| {\frac{{g_{k + 1}^T{y_k}}}{{y_k^T{d_k}}} - \frac{{{{\left\| {{y_k}} \right\|}^2}}}{{s_k^T{y_k}}}\frac{{g_{k + 1}^T{s_k}}}{{y_k^T{d_k}}}} \right| \\ &\leq& \left| {\frac{{g_{k + 1}^T{y_k}}}{{y_k^T{d_k}}} + \frac{{{{\left\| {{y_k}} \right\|}^2}g_{k + 1}^T{d_k}}}{{{{\left( {y_k^T{d_k}} \right)}^2}}}} \right| \\ &\leq& \left| {\frac{{L\left\| {{g_{k + 1}}} \right\|\left\| {{s_k}} \right\|}}{{\mu \left\| {{d_k}} \right\|\left\| {{s_k}} \right\|}} + \frac{{{L^2}\left\| {{g_{k + 1}}} \right\|{{\left\| {{s_k}} \right\|}^2}}}{{{\mu ^2}\left\| {{d_k}} \right\|{{\left\| {{s_k}} \right\|}^2}}}} \right| \\ &=& \left( {\frac{L}{\mu } + \frac{{{L^2}}}{{{\mu ^2}}}} \right)\frac{{\left\| {{g_{k + 1}}} \right\|}}{{\left\| {{d_k}} \right\|}}, \end{eqnarray} $

(4.7)

则

$ \begin{eqnarray} \left\| {{d_{k + 1}}} \right\| &\le& \left\| {{g_{k + 1}}} \right\| + \left| {{\beta _k^{HSDY1}}} \right|\left\| {{d_k}} \right\| \\ &\leq& \left\| {{g_{k + 1}}} \right\| + \left( {\frac{L}{\mu } + \frac{{{L^2}}}{{{\mu ^2}}}} \right)\frac{{\left\| {{g_{k + 1}}} \right\|}}{{\left\| {{d_k}} \right\|}}\left\| {{d_k}} \right\| \\ &\leq& \left( {1 + \frac{L}{\mu } + \frac{{{L^2}}}{{{\mu ^2}}}} \right)\left\| {{g_{k + 1}}} \right\|. \end{eqnarray} $

(4.8)

根据Zoutentijk条件(3.4)和定理2.3可得:

$ \begin{equation} \sum\limits_{k\geq1}\frac{\|g_k\|^{4}}{\|d_k\|^{2}}<\infty, \end{equation} $

(4.9)

由(4.6)和(4.9)式可得:

$ \begin{equation} \sum\limits_{k\geq1}\|g_{k}\|^2<\infty. \end{equation} $

(4.10)

所以(4.2)式成立. 证毕.

接下来, 我们将证明三个重要的引理.

引理4.1    假设(A)-(B)成立. 考虑HSDY1共轭梯度法, 其中步长$ {\alpha _k} $满足强Wolfe线搜索(1.4)和(1.5). 若存在一个常数$ \gamma > 0 $, 则有

$ \begin{equation} \|g_{k}\|\geq\gamma, \; \; \forall k\geq1, \end{equation} $

(4.11)

则$ d_{k}\neq0 $且

$ \begin{equation} \sum\limits_{k\geq1}\|u_{k}-u_{k-1}\|^2<\infty, \end{equation} $

(4.12)

其中$ u_{k}=\frac{d_{k}}{\|d_{k}\|}. $

证明  因为充分下降性条件(3.12)成立, 所以$ d_{k}\neq0 $, 故对于$ u_{k} $的定义是有意义的. 将(2.4)式中的$ \beta _k^{HSDY1} $分为如下两部分:

$ \begin{equation} \beta _k^1 = \left( {1 - {\vartheta _k^N}} \right)\beta _k^{HS}, \; \; \; \; \beta _k^2 = {\vartheta _k^N}\beta _k^{DY}. \end{equation} $

(4.13)

记

$ \begin{equation} w_{k}:=\frac{-g_k+\beta_{k-1}^{1}d_{k-1}}{\|d_k\|}, \; \; \delta_{k}:=\frac{\beta_{k-1}^{2}\|d_{k-1}\|}{\|d_{k}\|}. \end{equation} $

(4.14)

当$ k\geq2 $时, $ d_k=-g_k+\beta_{k-1}d_{k-1} $, 得

$ \begin{equation} u_{k}=w_{k}+\delta_{k}u_{k-1}. \end{equation} $

(4.15)

由$ \|u_{k}\|=\|u_{k-1}\|=1 $和(4.15)得

$ \begin{equation} \|w_{k}\|=\|u_{k}-\delta_{k}u_{k-1}\|=\|\delta_{k}u_{k}-u_{k-1}\|. \end{equation} $

(4.16)

又因为$ \delta_{k}\geq0 $, 再根据(4.16)我们可以得到

$ \begin{eqnarray} \|u_{k}-u_{k-1}\| &\leq&\|(1+\delta_{k})u_{k}-(1+\delta_{k})u_{k-1}\|\\ &\leq&\|u_{k}-\delta_{k}u_{k-1}\|+\|\delta_{k}u_{k}-u_{k-1}\|\\ &=&2\|w_{k}\|. \end{eqnarray} $

(4.17)

存在一个自适应参数$ {c_3} > 0 $, 使得$ {c_3} = \frac{{{{\left\| {{g_{k + 1}}} \right\|}^2}}}{{\left| {g_k^T{g_{k + 1}}} \right|}} $. 由(4.13)得

$ \begin{equation} \left\|-g_k+\beta_{k-1}^{2}d_{k-1}\right\|\leq\|g_k\|+\left|\beta_{k-1}^{2}\right|\|d_{k-1}\|\leq(1+{c_3})\|g_k\|, \end{equation} $

(4.18)

另外, 再根据(4.14), (4.17)和(4.18)可知

$ \begin{equation} \|u_k-u_{k-1}\|\leq2\|w_k\|\leq2(1+c_{3})\frac{\|g_k\|}{\|d_k\|}. \end{equation} $

(4.19)

最后, 结合(4.11), 再根据(3.4)和(3.12)可以得到

$ \begin{equation} \sum\limits_{k \ge 1} {\frac{{{g_k}{^2}}}{{{d_k}{^2}}}} \le \frac{1}{{{\gamma ^2}}}\sum\limits_{k \ge 1} {\frac{{{g_k}{^4}}}{{{d_k}{^2}}}} \le \frac{1}{{{\gamma ^2}{c_1}^2}}\sum\limits_{k \ge 1} {\frac{{{{(g_k^T{d_k})}^2}}}{{{d_k}{^2}}}} < + \infty . \end{equation} $

(4.20)

由(4.19)和(4.20)式可知

$ \begin{equation} \sum\limits_{k\geq1}\|u_{k}-u_{k-1}\|^2\leq 4(1+{c_3})^{2}\sum\limits_{k\geq1}\frac{\|g_k\|^2}{\|d_k\|^2}<\infty. \end{equation} $

(4.21)

证毕.

文献[24]中给出的性质($ \ast $), 对于收敛性结果的证明和分析产生了重要的作用. 下面证明HSDY1和HSDY2方法满足性质($ \ast $).

引理4.2    考虑由(1.2), (1.3)以及(2.4)产生的HSDY1, 其中步长$ {\alpha _k} $满足强Wolfe线搜索(1.4)和(1.5), 且(4.12)成立, 则HSDY1方法满足性质($ \ast $), 即若存在常数$ b>1 $和$ \lambda>0 $, 使得对所有的$ k $有$ |\beta_{k}|\leq b \quad \text{ 以及}\quad \|s_{k-1}\|\leq\lambda\Rightarrow |\beta_{k}|\leq\frac{1}{b}. $

证明    因为水平集$ \mathcal{L} $有界, 可知点列$ \{{x_{k}}\} $有界, 由梯度函数$ g $的连续性, 则存在$ \overline{\gamma}>0 $, 使得

$ \begin{equation} \|x_{k}\|\leq\overline{\gamma}, \; \; \|g_k\|\leq\overline{\gamma}, \; \; \forall k\geq1, \end{equation} $

(4.22)

根据(1.6), (3.5)和(4.11), 我们可以得到

$ \begin{equation} d_k^T{y_k} \ge - (1 - \sigma )g_k^T{d_k} \ge {c_1}(1 - \sigma ){g_k}{^2} \ge {c_1}(1 - \sigma ){\gamma ^2} > 0. \end{equation} $

(4.23)

由(4.23)最左端的不等式得

$ \begin{equation} \sigma g_{k}^{T}d_{k}\geq\frac{\sigma}{\sigma-1}d_{k}^{T}y_{k}. \end{equation} $

(4.24)

进一步, 由(4.23)和(4.24)有

$ \begin{equation} \frac{g_{k+1}^{T}d_{k}}{d_{k}^{T}y_{k}}\geq\frac{\sigma}{\sigma-1}, \end{equation} $

(4.25)

再根据(3.5)和(1.6)得

$ \begin{eqnarray} \frac{g_{k+1}^{T}d_{k}}{d_{k}^{T}y_{k}}=1+\frac{g_{k}^{T}d_{k}}{d_{k}^{T}y_{k}}\leq& 1, \end{eqnarray} $

(4.26)

将(4.25)和(4.26)合并得

$ \begin{equation} \frac{\sigma}{\sigma-1}\leq\frac{g_{k+1}^{T}d_{k}}{d_{k}^{T}y_{k}}\leq1, \end{equation} $

(4.27)

进而有

$ \begin{equation} \left|\frac{g_{k+1}^{T}d_{k}}{d_{k}^{T}y_{k}}\right|\leq M, \end{equation} $

(4.28)

其中$ M=\max\left\{1, \dfrac{\sigma}{1-\sigma}\right\} $. 由(4.22)式可以得到$ \|s_{k}\|=\|x_{k+1}-x_{k}\|\leq2\overline{\gamma} $成立.

下面根据(2.4), (4.22), (4.23), (4.28)及$ \|y_{k}\|\leq L\|s_{k}\| $对$ \left| {{\beta _k}} \right| $分类讨论.

对HSDY1方法有

$ \begin{eqnarray} \left| {{\beta _k}} \right| &=& \left| {\frac{{g_{k + 1}^T{y_k}}}{{y_k^T{d_k}}} + \frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\left( {\frac{{g_{k + 1}^T{y_k}}}{{y_k^T{d_k}}} - \frac{{{{\left\| {{g_{k + 1}}} \right\|}^2}}}{{y_k^T{d_k}}}} \right)} \right| \\ &=& \left| {\frac{{g_{k + 1}^T{y_k}}}{{y_k^T{d_k}}} - \frac{{g_{k + 1}^T{s_k}}}{{g_k^T{g_{k + 1}}}}\frac{{g_{k + 1}^T{g_k}}}{{y_k^T{d_k}}}} \right| \\ &\le& \left| {\frac{{g_{k + 1}^T{y_k}}}{{y_k^T{d_k}}}} \right|{\rm{ + }}\left| {\frac{{g_{k + 1}^T{s_k}}}{{y_k^T{d_k}}}} \right| \\ &\le& \frac{{\left( {L + 1} \right)\left\| {{g_{k + 1}}} \right\|\left\| {{s_k}} \right\|}}{{\bar c(1 - \sigma ){\gamma ^2}}}. \end{eqnarray} $

(4.29)

令$ N = \frac{{\left( {L + 1} \right)\left\| {{g_{k + 1}}} \right\|\left\| {{s_k}} \right\|}}{{{c_1}(1 - \sigma ){\gamma ^2}}} $, 则有$ \left| {{\beta _k}} \right| \le N\left\| {{s_k}} \right\| $, 定义$ b=2N\overline{\gamma} $, $ \lambda=\frac{1}{2N^2\overline{\gamma}} $, 则对所有$ k\geq1 $, 有

$ \begin{equation} |\beta_k|\leq b, \end{equation} $

(4.30)

且

$ \begin{equation} \|s_{k}\|\leq\lambda\; \Longrightarrow\; |\beta_k|\leq\frac{1}{b}. \end{equation} $

(4.31)

由(4.30)和(4.31)式, HSDY1方法满足性质($ \ast $).

定义4.1    正整数集为$ N^* $, 常数$ \lambda>0 $和一个正整数$ \Delta $, 记

$ \begin{equation} K_{k, \Delta}^{\lambda}:=\{i\in N^*:k\leq i\leq k+\Delta-1, \|s_{i-1}\|>\lambda\}. \end{equation} $

(4.32)

令$ |K_{k, \Delta}^{\lambda}| $为$ K_{k, \Delta}^{\lambda} $中的元素个数.

引理4.3    假设(A)-(B)成立. 考虑形如(1.2), (1.3)和(2.4)的HSDY1方法, 步长$ \alpha_{k} $通过强Wolfe线搜索(1.4)和(1.5)计算得到. 如果(4.11)成立, 则存在常数$ \lambda>0 $, 使得任意$ \Delta\in N^* $和任意指标集$ k_{0} $, 存在$ k\geq k_{0} $, 使得

$ \begin{equation} |K_{k, \Delta}^{\lambda}|>\frac{\Delta}{2}. \end{equation} $

(4.33)

注4.1    由性质(*)中证明到的HSDY1方法满足性质(A)以及$ \|d_{k}\|^{2} $至多线性增长, 类似于文献[24]中引理3.5的证明可得到上述引理的证明.

下面是HSDY1方法全局收敛性定理.

定理4.2    假设(A)-(B)成立. 考虑形如(1.2), (1.3)和(2.5)式的HSDY1方法, 步长$ \alpha_{k} $满足强Wolfe线搜索(1.4) 和(1.5), 则有

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

由引理4.1-4.3, HSDY1方法满足性质(*)以及$ \{{x_{k}}\} $是有界的, 参照文献[24]中定理4.3证明, 可以证得上述定理.

HSDY2方法的全局收敛性证明与HSDY1的方法类似.

由于DK方法是当前共轭梯度算法研究领域中公认的数值计算效果最好的方法之一, 在这一小节中, 为了验证HSDY, HSDY1, HSDY2方法的有效性, 我们将这三种方法同DK+ 方法作数值比较, 其中$ \eta =0.5 $. 本文选取文献[23]中的62个测试问题, 维数1000-100000. 计算中这四个方法的步长$ \alpha_k $都通过近似Wolfe线搜索(1.6)和(1.7)计算获得, 线搜索中的具体参数取$ \delta=0.1, \sigma=0.9 $. 算法的测试环境为华硕Windows 10操作系统Intel(R) Core(TM) i5-3337U CPU@1.80GHz 1.80GHz, 4GB内存.

对HSDY, HSDY1, HSDY2和DK方法的数值进行数据处理结果见表 1. 我们得到下面的比值表(见表 1)和性能曲线图(见图 1–4). 通过表 1中的比值结果可以看出, HSDY、HSDY1以及HSDY2方法都优于DK方法, 且HSDY2方法的计算效果最好.

本文采用文献[25]的技术得到以下性能曲线图。下图 1–4分别对应的是DK, HSDY, HSDY1以及HSDY2四种方法, 在近似Wolfe线搜索条件下解决测试问题所用的计算时间, 函数计算次数, 梯度计算次数以及迭代次数的性能曲线图. 从图中也可以看出HSDY, HSDY1以及HSDY2方法都优于DK方法, 且HSDY1方法的计算效果最好.

本文通过新的放缩方式, 提出两个参数自适应选取的HSDY共轭梯度法; 通过采用BFGS方法而不是牛顿法去逼近搜索方向, 在此条件下, 不必要求目标函数是二次可微的并且对应的Hesse矩阵是正定的. 本文提出的这两类共轭梯度法HSDY1, HSDY2均可以证明在强Wolfe线搜索条件下具有全局收敛性, 这在理论上是很好的; 在计算上与当前公认的数值计算最好的DK共轭梯度法都是可比的.