一类修正的共轭梯度法及其数值计算效果

A Kind of Modified Conjugate Gradient Method and Its Numerical Calculation Effect

摘要: 给出一个新的β^c_κ和δ_κ公式，新的共轭梯度法继承了FR方法的优点，在SWP线搜索下，具备良好的全局收敛性。在WWP线搜索下，给出谱共轭梯度法相应的分析。数值实验表明，本文提出的共轭梯度法数值计算性能更有效。

Abstract: A new formula β^c_κ and δ_κ is given. The new conjugate gradient method inherits the advantages of the FR method. Under the SWP line search, it should have good global convergence. Under the WWP line search, the corresponding analysis of the spectral conjugate gradient method is given. Numerical experiments show that the numerical calculation performance of the conjugate gradient method proposed in this paper is more effective.

1. 引言

考虑无约束优化问题：

$\min \left\{f\left(x\right):x\in {ℝ}^n\right\}$ (1)

其中，函数 $f:{ℝ}^n\to ℝ$ 的光滑函数，由于该方法低存储性，易于计算，目前被广泛运用于石油勘探、大气模拟、航天航空和工程优化等领域的求解问题上 [1]。一般地，求解问题(1)，需给定初始点 $x_0\in {ℝ}^n$，共轭梯度法由最初的线性优化推广到非线性优化问题上，用于求解大规模无约束优化问题，其早期的迭代公式如下：

$x_{k+1}=x_k+{\alpha }_k{d}_k$ (2)

${\alpha }_k$ 为搜索步长， $d_k$ 为搜索方向， $d_k$ 的定义如下：

$d_k=\{\begin{array}{l}-g_k;k=1\\ -g_k+{\beta }_k{d}_{k-1};k>1\end{array}$ (3)

其中， $g_k=\nabla f\left(x_k\right)$，是f在 $x_k$ 处的梯度，由(3)式可知，共轭梯度法的两个核心问题分别是步长因子 ${\alpha }_k$ 的计算和搜索方向 $d_k$ 的选取，需要寻找合适的步长搜索规则，如弱Wolfe线搜索(WWP)、强Wolfe线搜索(SWP)和推广的Wolfe线搜索，分别如下：

$\{\begin{array}{l}f\left(x_k+{\alpha }_k{d}_k\right)\le f\left(x_k\right)+\delta {\alpha }_k{g}_k^{\text{T}}{d}_k\\ g_{k+1}^{\text{T}}{d}_k\ge \sigma g_k^{\text{T}}{d}_k\end{array}$

$\{\begin{array}{l}f\left(x_k+{\alpha }_k{d}_k\right)\le f\left(x_k\right)+\delta {\alpha }_k{g}_k^{\text{T}}{d}_k\\ \left|g_{k+1}^{\text{T}}{d}_k\right|\le \sigma \left|g_k^T{d}_k\right|\end{array}$

$\{\begin{array}{l}f\left(x_k+{\alpha }_k{d}_k\right)\le f\left(x_k\right)+\delta {\alpha }_k{g}_k^{\text{T}}{d}_k\\ \sigma g_k^{\text{T}}{d}_k\le g_{k+1}^{\text{T}}{d}_k\le -{\sigma }_1{g}_k^{\text{T}}{d}_k\end{array}$

当 $0<\delta <\sigma <1$ 和 ${\sigma }_{\text{1}}\ge \text{0}$ 是常数， ${\beta }_k$ 为共轭参数，常用的 ${\beta }_k$ 公式 [2] [3] [4] [5] 如下：

$\begin{array}{l}{\beta }_k^{FR}=\frac{{\Vert g_k\Vert }^2}{{\Vert g_{k-1}\Vert }^2}\left(\text{Fletcher-Reeves},1964\right)\\ {\beta }_k^{DY}=\frac{{\Vert g_k\Vert }^2}{d_{k-1}^{\text{T}}{y}_{k-1}}\left(\text{DaiYuan},1999\right)\\ {\beta }_k^{PRP}=\frac{g_k^{\text{T}}{y}_{k-1}}{{\Vert g_{k-1}\Vert }^2}\left(\text{Polak-Ribiere-Polyak},1969\right)\\ {\beta }_k^{HS}=-\frac{g_k^{\text{T}}{y}_{k-1}}{d_{k-1}^{\text{T}}{g}_{k-1}}\left(\text{Hestenses-Stiefel},1952\right)\end{array}$ (4)

其中， $\Vert ·\Vert$ 为Euclidean范数， $y_{k-1}=g_k-g_{k-1}$，一般而言，目标函数为严格凸时，PRP方法与HS方法的数值计算效果优于FR方法和DY方法，但收敛性却没有后两种方法好。当目标函数非凸时，即使采用Curry原则选取步长因子，即 ${\alpha }_k$ 为一维函数 ${\Phi }_k\left(\alpha \right)=\left\{f\left(x_k+\alpha d_k\right):\alpha >0\right\}$ 的第一个极小点，也无法保证它们全局收敛，以上方法在收敛性分析和数值计算性能上有所差异。近年来，共轭梯度法的许多变种被广泛研究，在一定程度上继承了经典方法的某些特性。2012年，在文献 [6] 的基础上，Dai等 [7] 提出一种新的DPRP方法，分母变成线性组合的形式，其共轭参数 ${\beta }_k^{DPRP}$ 定义为

${\beta }_k^{DPRP}=\frac{{\Vert g_k\Vert }^2-\frac{\Vert g_k\Vert }{\Vert g_{k-1}\Vert }\left|g_k^{\text{T}}{g}_{k-1}\right|}{\mu \left|g_k^{\text{T}}{d}_{k-1}\right|+{\Vert g_{k-1}\Vert }^2}$ (5)

其中 $\mu >1$，Dai等人首先证明了该方法在不进行任何线搜索的情况下具有充分下降性，其次证明在Wolfe线搜索或Armijo线搜索下的全局收敛性。并把这个结果扩展到HS方法中 [8]，也是进行相应的收敛性分析，数值实验结果表明DPRP方法比文献 [6] 中方法更有效。

2019年，景书杰等 [9] 提出一类改进的谱共轭梯度法，新的共轭系数和谱系数公式定义为

$\begin{array}{l}{\beta }_k^{SN}=\frac{g_k^{\text{T}}\left(\frac{\Vert g_{k-1}\Vert }{\Vert g_k\Vert }{g}_k-g_{k-1}-d_{k-1}\right)}{{\Vert d_{k-1}\Vert }^2+\mu \left|g_k^{\text{T}}{d}_{k-1}\right|},\mu >1\\ {\theta }_k=1+{\beta }_k^{SN}\frac{g_k^{\text{T}}{d}_{k-1}}{{\Vert g_k\Vert }^2}\end{array}$ (6)

根据现有的共轭系数公式，构造一个新的共轭系数公式和谱系数公式，从而提出一种新的谱共轭梯度法，保证算法在每次迭代时不依赖于任何线搜索总能产生充分下降的搜索方向，并在Armijo线搜索和一般假设条件下，给出算法的全局收敛性证明。将式(5)的分子或者分母推广到其它共轭梯度法上，或者建立混合共轭梯度法，也具备良好的数值计算效果。更多的可以参看文献 [10] [11] [12] [13] [14]。

文章结构如下：第2节两种新算法的提出；第3节共轭梯度法及其全局收敛性；第4节谱共轭梯度法及其全局收敛性；第5节数值实验和第6节全文总结。

2. 修改的共轭梯度法和谱共轭梯度法

基于以上文献的思想，特别是 ${\beta }_k^{DPRP}$ 和 ${\beta }_k^{SN}$ 的构造，本文对文献 [15] 的公式做出如下的修改，给出一个新的 ${\beta }_k^C$ 公式

${\beta }_k^C=\frac{g_k^{\text{T}}\left(\frac{2\Vert g_{k-1}\Vert -\Vert g_k\Vert }{\Vert g_k\Vert }{g}_k-g_{k-1}-d_{k-1}\right)}{{\Vert g_{k-1}\Vert }^2+\mu \left|g_k^{\text{T}}{d}_{k-1}\right|+\lambda },\mu \ge 0,\lambda >0$ (7)

基于公式(7)，采用SWP线搜索条件来修正共轭梯度算法如下：

算法1

Step 1：初始值 $x_0\in R^n$， $\epsilon >0$，令 $\mu \ge 0$， $\lambda >0$， $0<\rho <\sigma <1$， $k:=1$， $d_1=-g_1$，计算 $g_k$，若 $\Vert g_1\Vert \le \epsilon$，则停止。

Step 2：用SWP线搜索公式计算 ${\alpha }_k$，

Step 3：令 $x_{k+1}=x_k+{\alpha }_k{d}_k$，若 $\Vert g_{k+1}\Vert \le \epsilon$，则停止，

Step 4：用式(3)和(7)分别计算 $d_{k+1},{\beta }_{k+1}^C$，

Step 5：使得 $k:=k+1$，转Step 2。

谱共轭梯度法作为求解问题(1)的另一方式被提出，通过调整谱系数和共轭参数，建立合适的算法，本文降低线搜索条件，故采用WWP线搜索条件设计谱共轭梯度算法如下：

算法2

Step 1：初始值 $x_0\in R^n$， $\epsilon >0$，令 $\mu \ge 0$， $\lambda >0$， $0<\rho <\sigma <1$， $k:=1$， $d_1=-g_1$，计算 $g_k$，若 $\Vert g_1\Vert \le \epsilon$，则停止。

Step 2：用WWP线搜索公式计算 ${\alpha }_k$，

Step 3：令 $x_{k+1}=x_k+{\alpha }_k{d}_k$，若 $\Vert g_{k+1}\Vert \le \epsilon$，则停止，

Step 4：用(7)式计算 ${\beta }_{k+1}^C$，由下式计算搜索方向 $d_{k+1}$

$\begin{array}{l}{d}_{k+1}=-{\delta }_{k+1}{g}_{k+1}+{\beta }_{k+1}{d}_k\\ {\delta }_{k+1}=1+{\beta }_{k+1}^C\frac{g_{k+1}^{\text{T}}{d}_k}{{\Vert g_{k+1}\Vert }^2}\end{array}$

Step 5：使得 $k:=k+1$，转Step 2。

以下常规性假设在共轭梯度法的研究中经常被用到

假设H [9] (H1)定义目标函数 $f\left(x\right)$ 在水平集 $\Omega =\left\{x\in {ℝ}^n;f\left(x\right)\le f\left(x_0\right)\right\}$ 有下界，且 $x_0$ 为初始点。

(H2) 目标函数 $f\left(x\right)$ 在水平集 $\Omega$ 的一个领域N内连续可微，其梯度函数满足Lipschitz连续，即存常数 $L>0$，使得 $\Vert g\left(x\right)-g\left(y\right)\Vert \le L\Vert x-y\Vert ,\forall x,y\in N$。

3. 共轭梯度法及其全局收敛性

引理3.1：若假设H成立，考虑序列 $x_{k+1}=x_k+{\alpha }_k{d}_k$，序列 $\left\{g_k\right\}$ 和 $\left\{d_k\right\}$ 由算法1生成，如果

1) 对所有k均成立 $\Vert g_{k+1}\Vert >3L{\alpha }_k\Vert d_k\Vert$

2) 存在常数 $r>0$，使得对任给 $k>0$，都有 $\Vert g_k\Vert >r$ 成立，则存在一个充分大的 $k_0$，使得 $k>k_0$ 时， ${\beta }_{k+1}^C$ 满足

$\text{0}\le {\beta }_{k+1}^C\le {\beta }_{k+1}^{FR}=\frac{{\Vert g_{k+1}\Vert }^2}{{\Vert g_k\Vert }^2}$ (8)

证明：因为 ${\beta }_{k+1}^C$ 的定义为

${\beta }_{k+1}^C=\frac{g_{k+1}^{\text{T}}\left(\frac{2\Vert g_k\Vert -\Vert g_{k+1}\Vert }{\Vert g_{k+1}\Vert }{g}_{k+1}-g_k-d_k\right)}{{\Vert g_k\Vert }^2+\mu \left|g_{k+1}^{\text{T}}{d}_k\right|+\lambda }$ (9)

1) 证明分子 $g_{k+1}^{\text{T}}\left(\frac{2\Vert g_k\Vert -\Vert g_{k+1}\Vert }{\Vert g_{k+1}\Vert }{g}_{k+1}-g_k-d_k\right)\le \Vert g_{k+1}\Vert 3L{\alpha }_k\Vert d_k\Vert$ 成立

$\begin{array}{l}{g}_{k+1}^{\text{T}}\left(\frac{2\Vert g_k\Vert -\Vert g_{k+1}\Vert }{\Vert g_{k+1}\Vert }{g}_{k+1}-g_k-d_k\right)\le \Vert g_{k+1}\Vert \cdot \Vert \frac{2\Vert g_k\Vert -\Vert g_{k+1}\Vert }{\Vert g_{k+1}\Vert }{g}_{k+1}-g_{k+1}+g_{k+1}-g_k\Vert \\ \le \Vert g_{k+1}\Vert \left(\Vert \frac{2\Vert g_k\Vert -\Vert g_{k+1}\Vert }{\Vert g_{k+1}\Vert }{g}_{k+1}-g_{k+1}\Vert +\Vert g_{k+1}-g_k\Vert \right)\\ \le \Vert \left(2\Vert g_k\Vert -\Vert g_{k+1}\Vert \right)g_{k+1}-\Vert g_{k+1}\Vert \cdot g_{k+1}\Vert +\Vert g_{k+1}\Vert \cdot \Vert g_{k+1}-g_k\Vert \\ \le 2\Vert g_k-g_{k+1}\Vert \cdot \Vert g_{k+1}\Vert +\Vert g_{k+1}\Vert \cdot \Vert g_{k+1}-g_k\Vert \\ \le 3\Vert g_{k+1}\Vert \cdot \Vert g_{k+1}-g_k\Vert \le \Vert g_{k+1}\Vert 3L{\alpha }_k\Vert d_k\Vert \end{array}$

2) 将以上化简结果代入式(9)中

${\beta }_{k+1}^C=\frac{g_{k+1}^{\text{T}}\left(\frac{2\Vert g_k\Vert -\Vert g_{k+1}\Vert }{\Vert g_{k+1}\Vert }{g}_{k+1}-g_k-d_k\right)}{{\Vert g_k\Vert }^2+\mu \left|g_{k+1}^{\text{T}}{d}_k\right|+\lambda }\le \frac{\Vert g_{k+1}\Vert 3L{\alpha }_k\Vert d_k\Vert }{{\Vert g_k\Vert }^2+\mu \left|g_{k+1}^{\text{T}}{d}_k\right|+\lambda }\le \frac{\Vert g_{k+1}\Vert \cdot 3L{\alpha }_k\Vert d_k\Vert }{{\Vert g_k\Vert }^2}$

因为

$0\le {\alpha }_k\Vert d_k\Vert <\frac{\Vert g_{k+1}\Vert }{3L}$

则引理3.1得证。

引理3.2：如果参数 $\sigma <\frac{1}{2},\mu \ge 0,\lambda >0$，则存在常数 $c_1=\frac{1-2\sigma +{\sigma }^k}{1-\sigma },c_2=\frac{1-{\sigma }^k}{1-\sigma }$ 对所有的k，有下式成立：

$-c_2{\Vert g_k\Vert }^2\le g_k^{\text{T}}{d}_k\le -c_1{\Vert g_k\Vert }^2,\forall k\ge 1$ (10)

证明：数学归纳法：当 $k=1,d_1=-g_1,g_1^{\text{T}}{d}_1=-{\Vert g_1\Vert }^2$，则(10)式成立。

假设 $k>1$，都有 $g_k^{\text{T}}{d}_k<0$ 成立，令(3)式中k为k + 1时与 $g_{k+1}^{\text{T}}$ 作内积，结合(8)式得

$\frac{-g_{k+1}^{\text{T}}{d}_{k+1}}{{\Vert g_{k+1}\Vert }^2}=1-\frac{g_{k+1}^{\text{T}}{d}_k}{{\Vert g_k\Vert }^2}$

在上式中用

$\sigma d_k^{\text{T}}{g}_k\le d_k^{\text{T}}g\left(x_k+{\alpha }_k{d}_k\right)\le -\sigma d_k^{\text{T}}{g}_k$

则有

$1+\sigma \frac{g_k^{\text{T}}{d}_k}{{\Vert g_k\Vert }^2}\le \frac{-g_{k+1}^{\text{T}}{d}_{k+1}}{{\Vert g_{k+1}\Vert }^2}\le 1-\sigma \frac{g_k^{\text{T}}{d}_k}{{\Vert g_k\Vert }^2}$ (11)

利用(11)式递推可得：

$c_1=\frac{1-2\sigma +{\sigma }^k}{1-\sigma }\le \frac{-g_{k+1}^{\text{T}}{d}_{k+1}}{{\Vert g_{k+1}\Vert }^2}\le \frac{1-{\sigma }^k}{1-\sigma }=c_2$

由归纳法知，上述引理成立。当 $\sigma <\frac{1}{2}$ 时，充分下降条件对正常数 $c=\frac{1-2\sigma }{1-\sigma }$ 也成立。

由引理3.2和文献 [1] 引理1.4.1，可得以下引理。

引理3.3：若假设H成立，序列 $\left\{x_k\right\}$ 由算法1生成， $d_k$ 满足 $g_k^{\text{T}}{d}_k<0$， ${\alpha }_k$ 由SWP线搜索得到，则Zoutendijk条件成立：

${\displaystyle \underset{k\ge 1}{\sum }\frac{{\Vert g_k\Vert }^4}{{\Vert d_k\Vert }^2}}<+\infty$

证明：由SWP线搜索得 $d_k^{\text{T}}{y}_k\ge \left(\sigma -1\right)g_k^{\text{T}}{d}_k$。

由Lipschitz条件得 $d_k^{\text{T}}{y}_k\le {\alpha }_{k}L{\Vert d_k\Vert }^2$，把两式结合，则有

${\alpha }_k\ge \frac{\sigma -1}{L}\cdot \frac{g_k^{\text{T}}{d}_k}{{\Vert d_k\Vert }^2}$ (12)

由SWP线搜索和(12)式得

$f_k-f_{k+1}\ge c\frac{{\left(g_k^{\text{T}}{d}_k\right)}^2}{{\Vert d_k\Vert }^2}$

其中， $c=\frac{\delta \left(1-\sigma \right)}{L}$，对上式从 $k=1,2,\cdots$ 求和，由假设H(1)知， ${\displaystyle \underset{k\ge 1}{\sum }\frac{{\left(g_k^{\text{T}}{d}_k\right)}^2}{{\Vert d_k\Vert }^2}}<+\infty$ 成立，由充分下降条件 $g_k^{\text{T}}{d}_k\le -c{\Vert g_k\Vert }^2$ 成立，则有

${\displaystyle \underset{k\ge 1}{\sum }\frac{{\Vert g_k\Vert }^4}{{\Vert d_k\Vert }^2}}<+\infty$

以下是算法1的全局收敛性结果。

定理1：若假设H成立，序列 $\left\{g_k\right\}$ 和 $\left\{d_k\right\}$ 由算法1生成，若 $\sigma <\frac{1}{2}$，则 $\underset{k\to \infty }{\lim }\inf \Vert g_k\Vert =0$。

证明：反证法，即存在常数 $r>0$，有 $\Vert g_k\Vert \ge r,\forall k\ge 1$

$\begin{array}{l}\because d_{k+1}=-g_{k+1}+{\beta }_{k+1}^C{d}_k\\ {\Vert d_{k+1}\Vert }^2={\left({\beta }_{k+1}^C\right)}^2{\Vert d_k\Vert }^2-2{\beta }_{k+1}^C{g}_{k+1}^{\text{T}}{d}_k+{\Vert g_{k+1}\Vert }^2\end{array}$

两边同除 ${\Vert g_{k+1}\Vert }^4$

$\frac{{\Vert d_{k+1}\Vert }^2}{{\Vert g_{k+1}\Vert }^4}={\left({\beta }_{k+1}^C\right)}^2\frac{{\Vert d_k\Vert }^2}{{\Vert g_{k+1}\Vert }^4}-2{\beta }_{k+1}^C\frac{g_{k+1}^{\text{T}}{d}_k}{{\Vert g_{k+1}\Vert }^4}+\frac{1}{{\Vert g_{k+1}\Vert }^2}$

由SWP线搜索、(8)式和(10)式知

$\frac{\left|g_{k+1}^{\text{T}}{d}_k\right|}{{\Vert g_k\Vert }^2}\le \frac{\sigma \left|g_k^{\text{T}}{d}_k\right|}{{\Vert g_k\Vert }^2}\le \frac{\sigma }{1-\sigma }$

$\begin{array}{l}\frac{\text{||}{d}_{k+1}{\text{||}}^2}{\left|\right|g_{k+1}|{|}^{\text{4}}}\le {\left({\beta }_{k+1}^{FR}\right)}^2\frac{{\Vert d_k\Vert }^2}{{\Vert g_{k+1}\Vert }^4}+2{\beta }_{k+1}^{FR}\frac{\left|g_{k+1}^{\text{T}}{d}_k\right|}{{\Vert g_{k+1}\Vert }^4}+\frac{1}{{\Vert g_{k+1}\Vert }^2}\\ \le \frac{{\Vert d_k\Vert }^2}{{\Vert g_k\Vert }^4}+2\sigma \frac{\left|g_k^{\text{T}}{d}_k\right|}{{\Vert g_{k+1}\Vert }^4\cdot {\Vert g_k\Vert }^2}+\frac{1}{{\Vert g_{k+1}\Vert }^2}\le \frac{{\Vert d_k\Vert }^2}{{\Vert g_k\Vert }^4}+\frac{1}{{\Vert g_{k+1}\Vert }^2}\left(1+\frac{2\sigma }{1-\sigma }\right)\\ \le \frac{1+\sigma }{1-\sigma }{\displaystyle \underset{i=1}{\overset{k+1}{\sum }}\frac{1}{{\Vert g_i\Vert }^2}}\le \frac{1+\sigma }{1-\sigma }\frac{k+1}{r^2}\end{array}$

由上式得

${\displaystyle \underset{k\ge 1}{\sum }\frac{{\Vert g_{k+1}\Vert }^4}{{\Vert d_{k+1}\Vert }^2}}\ge \frac{1-\sigma }{1+\sigma }{r}^2{\displaystyle \underset{k\ge 1}{\sum }\frac{1}{k+1}}=+\infty$

与引理3.3矛盾，故定理1得证。

4. 谱共轭梯度法及其全局收敛性

引理4.1：序列 $\left\{g_k\right\}$ 和 $\left\{d_k\right\}$ 由算法2生成， $\forall k\ge 1$，都有 $g_k^{\text{T}}{d}_k=-{\Vert g_k\Vert }^2<0$。

证：当 $k=1$ 时， $d_1=-g_1,g_1^{\text{T}}{d}_1=-{\Vert g_1\Vert }^2<0$ 成立，

当 $k>1$ 时， $\begin{array}{c}{g}_k^{\text{T}}{d}_k=-{\delta }_k{\Vert g_k\Vert }^2+{\beta }_k^C{g}_k^{\text{T}}{d}_{k-1}\\ =-\left(1+{\beta }_k^C\frac{g_k^{\text{T}}{d}_{k-1}}{{\Vert g_k\Vert }^2}\right){\Vert g_k\Vert }^2+{\beta }_k^C{g}_k^{\text{T}}{d}_{k-1}\\ =-{\Vert g_k\Vert }^2-{\beta }_k^C{g}_k^{\text{T}}{d}_{k-1}+{\beta }_k^C{g}_k^{\text{T}}{d}_{k-1}\\ =-{\Vert g_k\Vert }^2<0\end{array}$

故算法2中产生的搜索方向 $d_k$ 满足充分下降性。

引理4.2：若假设H成立， $d_k$ 满足 $d_k^{\text{T}}{g}_k<0$， ${\alpha }_k$ 满足WWP线搜索，则Zoutendijk条件成立：

${\displaystyle \underset{k\ge 1}{\sum }\frac{{\left(g_k^{\text{T}}{d}_k\right)}^2}{{\Vert d_k\Vert }^2}}<+\infty$

定理2：若假设H成立，序列 $\left\{g_k\right\}$ 和 $\left\{d_k\right\}$ 由算法2生成，则 $\underset{k\to \infty }{\lim }\inf \Vert g_k\Vert =0$。

证明：假设结论不成立，则存在一个常数 $r>0$，使得 $\Vert g_k\Vert \ge r,\forall k\ge 0$，因为

${\delta }_{k+1}=\left(1+{\beta }_{k+1}^C\frac{g_{k+1}^{\text{T}}{d}_k}{{\Vert g_{k+1}\Vert }^2}\right)$

由算法2中定义的搜索方向 $d_{k+1}$，两边取范数模平方得

${\Vert d_{k+1}\Vert }^2={\left({\beta }_{k+1}^C\right)}^2{\Vert d_k\Vert }^2-2{\delta }_{k+1}{d}_{k+1}^{\text{T}}{g}_{k+1}-{\delta }_{k+1}^2{\Vert g_{k+1}\Vert }^2$

两端同除 ${\Vert g_{k+1}\Vert }^4$，又因为 $d_{k+1}^{\text{T}}{g}_{k+1}=-{\Vert g_{k+1}\Vert }^2$。

又因为引理3.1

$\begin{array}{c}\frac{{\Vert d_{k+1}\Vert }^2}{{\Vert g_{k+1}\Vert }^4}={\left({\beta }_{k+1}^C\right)}^2\frac{{\Vert d_k\Vert }^2}{{\Vert g_{k+1}\Vert }^4}+\frac{2{\delta }_{k+1}}{{\Vert g_{k+1}\Vert }^2}-\frac{{\delta }_{k+1}^2}{{\Vert g_{k+1}\Vert }^2}\\ \le {\left(\frac{{\Vert g_{k+1}\Vert }^2}{{\Vert g_k\Vert }^2}\right)}^2\frac{{\Vert d_k\Vert }^2}{{\Vert g_{k+1}\Vert }^4}-\frac{{\left({\delta }_{k+1}-1\right)}^2}{{\Vert g_{k+1}\Vert }^2}+\frac{1}{{\Vert g_{k+1}\Vert }^2}\le \frac{{\Vert d_k\Vert }^2}{{\Vert g_k\Vert }^4}+\frac{1}{{\Vert g_{k+1}\Vert }^2}\end{array}$

当 $k=0$ 时， $d_0=-g_0$，上式写成

$\le \frac{1}{{\Vert g_0\Vert }^2}+\frac{1}{{\Vert g_{k+1}\Vert }^2}\le \cdots \le {\displaystyle \underset{i=0}{\overset{k+1}{\sum }}\frac{1}{{\Vert g_i\Vert }^2}}\le \frac{k+2}{r^2}$

所以有

${\displaystyle \underset{i=0}{\overset{k}{\sum }}\frac{{\Vert g_{k+1}\Vert }^4}{{\Vert d_{k+1}\Vert }^2}}\ge r^2{\displaystyle \underset{i=0}{\overset{k}{\sum }}\frac{1}{k+1}}=+\infty$

此结论与引理4.2的Zoutendijk条件矛盾，故定理2成立。

5. 数值实验

本节中，我们分析所提出新方法的数值性能，分别与文献 [15] 的方法作比较，记为WSWP，还有文献 [16] 的方法作比较，记为RMIL+，本文的共轭梯度法和谱共轭梯度法分别记为FSWP和PCWWP，无约束测试问题选自文献 [17]，算法运行的终止条件为 $\Vert g_k\Vert \le {10}^{-6}$ 或迭代次数超过10,000，所有代码实现都在Matlab2016a中进行，数值结果以NI，NF，NG的形式表示，其中，NI指迭代次数，NF指函数取值，NG指梯度取值。“-”指算法运行失效。各符号和参数说明如下：

RMIL + SWP：RMIL + 公式用SWP线搜索， $\sigma =0.1,\delta =0.01$ ；

WSPW：韦等提出的公式用SWP线搜索， $\sigma =0.1,\delta =0.01$ ；

FSWP：本文提出的共轭梯度法用SWP线搜索， $\sigma =0.2,\delta =0.01,\mu =4.5,\lambda =0.2$ ：

PCWWP：本文提出的谱共轭梯度法用WWP线搜索， $\sigma =0.1,\delta =0.01,\mu =4.5,\lambda =0$。

Table 1. Numerical results of each method

表1. 各方法的数值计算结果

从表1中可以看出，基于新的参数公式，本文提出的共轭梯度法(FSWP)的数值计算性能优于表中其它方法，能解决绝大部分测试问题，相反，本文提出的谱共轭梯度法收敛性条件减弱，但数值计算性能(PCWWP)却没有共轭梯度法的好，如何调整谱共轭梯度法的两个参数，使之达到更好的计算效果，仍需进一步研究。

6. 总结

本文借鉴已有文献的思路，对经典的共轭梯度法中的共轭参数作简单的分解或变形，而不改变原公式的大致结构，从而提出类似的 ${\beta }_k$ 新参数公式，并分别在SWP线搜索下建立新的共轭梯度法的全局收敛性分析和WWP线搜索下建立谱共轭梯度法的全局收敛性分析，数值实验与经典方法作比较，本文提出的共轭梯度法更有效。