考虑如下无约束优化问题

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

(1.1)

其中$f(x)$是$R^n\longrightarrow R$上的连续可微函数, 用非线性共轭梯度法求解无约束优化问题(1.1), 点列$\{x_k\}$的迭代格式为

$ x_{k+1} =x_k +\alpha_kd_k, $

(1.2)

这里的$\alpha_k$为步长.本文选用精确线搜索计算$\alpha_k$, 即每步迭代中选择$\alpha_k $满足

$ \alpha_k=\min \{\alpha|\nabla f(x_k+\alpha d_k)^T d_k=0, \alpha>0\}. $

(1.3)

选取步长因子$\alpha_k$最好的方法就是使目标函数沿着搜索方向$d_k$达到极小, 从理论上来说, 精确线搜索所得到的步长因子有着最好的下降量.例如Zoutendijk^[1]证明了采取精确线搜索的FR方法对一般非凸函数总收敛; 从文献[2]中的结果可知用精确线搜索的PRP方法对一致凸函数全局收敛; Rivaie^[3]提出了一个新算法在精确线搜索下有更好的结果.

搜索方向$d_k$的迭代格式为

$ \begin{array}{l} d_k=\left\{ \begin{array}{rl} g_k, &k=1, \\ g_k+\beta_kd_{k-1}, &k\geq2, \end{array} \right. \end{array} $

(1.4)

其中$g_k=\bigtriangledown f(x_k)$, 如果用$\theta_k$表示向量$d_k$与$-g_k$的夹角, 则有

$ \cos \theta_k=\frac{-g_k ^T d_k}{\|g_k\|\|d_k\|}, $

(1.5)

这里的$\beta_k$为一标量, 著名的$\beta_k$公式有(可参看文献[4-8])

$ \begin{eqnarray*} &&\beta_k ^{\rm FR}=\frac{\|g_k\|^2}{\|g_{k-1}\|^2}, \beta_k^{\rm PRP}=\frac{g_k ^T (g_k-g_{k-1})}{\|g_{k-1}\|^2}, \\ &&\beta_k^{\rm HS}=\frac{g_k ^T (g_k-g_{k-1})}{d_{k-1} ^T(g_k-g_{k-1})}, \beta_k^{\rm DY}=\frac{\|g_k\|^2}{d_{k-1} ^T (g_k-g_{k-1})}, \end{eqnarray*} $

其中$\|\cdot\|$表示欧式范数.通常情况下, FR和DY方法有很好的收敛性, 而PRP和HS方法却有很好的数值效果.学者们为了寻找既能保证收敛性又可以有良好数值效果的算法, 在以上公式的基础上, 一方面对$\beta_k$进行改进例如文献[3, 9, 10], 另一方面将不同的$\beta_k$公式进行混合^[11-13].最近, 文献[3]中给出了一个新的参数公式

$ \beta_k ^{\rm RMIL}=\frac{g_k ^T (g_k-g_{k-1})}{\|d_{k-1}\|^2}, $

(1.6)

并得到了该算法在精确线搜索下的全局收敛性.受文献[12]的启发, 取$\beta_k^{\rm New}$为

$ \begin{array}{l} \beta_k ^{\rm New}=\left\{ \begin{array}{rl} 0, &\|g_k\| ^2 < |g_k^T g_{k-1}|, \\ \mu\frac{\|g_k\|^2-|g_k^T g_{k-1}|}{|g_k^T d_{k-1}|+\|d_{k-1}\|^2}, &\|g_k\|^2\geq|g_k^T g_{k-1}|, \end{array} \right. \end{array} $

(1.7)

其中$\mu$为参数且$0 < \mu \leq 1$.

本文讨论一种新的混合共轭梯度法, 其中

$ \begin{array}{l} \beta_k =\left\{ \begin{array}{rl} \beta_k ^{\rm New}, &\|g_k\| ^2 \geq |g_k^T g_{k-1}|, \\ \beta_k ^{\rm RMIL}, &\mbox{其他}. \end{array} \right. \end{array} $

(2.1)

算法A  步骤1  给定$\varepsilon>0, x_1\in R^n, 0 < \mu\leq 1, d_1=-g_1, k:=1$.

步骤2  若$\|g_k\| < \varepsilon$, 则停止; 否则转步骤3.

步骤3  由精确线搜索计算步长$\alpha_k $, 使其满足(1.3)式.

步骤4  令$x_{k+1}=x_k+\alpha_kd_k$, 求$g_{k+1}$, 并用(2.1)式试求$\beta_{k+1}$.

步骤5  令$d_{k+1}=-g_{k+1}+\beta_{k+1}d_k$, 令$k=k+1$; 转步骤2.

引理2.1  对任意$k\geq1$, 算法A产生的搜索方向$d_k$满足$g_k^T d_k\leq-C\|g_k\|^2$, 其中$C\geq0$.

证  当$k=1$时, $g_1^T d_1=-\|g_1\|^2 < 0$, 故结论成立.

(ⅰ)当$\beta_k=\beta_k^{\rm New}$时, 若$\beta_k^{\rm New}=0$, 有$g_k^T d_k=-\|g_k\|^2$, 结论成立.否则有

$ \begin{equation*} \beta_k^{\rm New}=\mu\frac{\|g_k\|^2-|g_k^T g_{k-1}|}{|g_k^T d_{k-1}|+\|d_{k-1}\|^2} \leq \mu\frac{\|g_k\|^2}{|g_k^T d_{k-1}|+\|d_{k-1}\|^2}\leq \mu\frac{\|g_k\|^2}{|g_k^T d_{k-1}|}. \end{equation*} $

因此当$k>1$时,

$ \begin{align} g_k^T d_k=-\|g_k\|^2+\beta_k^{\rm New}g_k^T d_{k-1} \leq -\|g_k\|^2+\mu\frac{\|g_k\|^2}{|g_k^T d_{k-1}|}g_k^T d_{k-1} = -(1-\mu)\|g_k\|^2. \end{align} $

(2.2)

因为$0 < \mu\leq 1$, 故$g_k^T d_k\leq-C\|g_k\|^2$, 其中$C\geq0$.

(ⅱ)当$\beta_k=\beta_k^{\rm RMIL}$, $k>1$时, 对式(1.3)有

$ \begin{equation*} g_k^T d_k=-\|g_k\|^2+\beta_k^{\rm RMIL}g_k^T d_{k-1}. \end{equation*} $

对于精确线搜索, 有$g_k^T d_{k-1}=0$.所以$g_k^T d_k=-\|g_k\|^2$, 故$g_k^T d_k\leq-C\|g_k\|^2$成立, 证毕.

引理2.2  同引理2.1中的条件, 由式(1.5)和(2.1)可得$|\beta_k|\leq\beta_k^{\rm RMIL}$.

证  因为

$ \begin{equation*} \beta_k ^{\rm RMIL}=\frac{g_k ^T(g_k-g_{k-1})}{\|d_{k-1}\|^2}=\frac{\|g_k\| ^2-|g_k^T g_{k-1}|}{\|d_{k-1}\|^2}, \end{equation*} $

由(2.1)式知, 当$\beta_k=\beta_k^{\rm New}$时, $\|g_k\| ^2\geq |g_k^T g_{k-1}|$, 所以

$ \begin{equation*} \frac{\|g_k\| ^2-|g_k^T g_{k-1}|}{-\|d_{k-1}\|^2}\leq \frac{\|g_k\| ^2-|g_k^T g_{k-1}|}{|g_k^T d_{k-1}|+\|d_{k-1}\|^2}\leq \frac{\|g_k\| ^2-|g_k^T g_{k-1}|}{\|d_{k-1}\|^2}, \end{equation*} $

所以$-\beta_k^{\rm RMIL}\leq \beta_k^{\rm New}\leq \beta_k^{\rm RMIL}, $故有$|\beta_k|\leq\beta_k^{\rm RMIL}$.证毕.

假设

(H1)目标函数$f(x)$在水平集$L_0=\{x\in R^n|f(x)\leq f(x_1)\}$上有下界, 其中$x_1$为初始点.

(H2)目标函数$f(x)$在水平集$L_0$的一个邻域$N$内连续可微, 且梯度函数$g(x)$满足Lipschitz连续, 即存在常数$L>0$, 使

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

(3.1)

引理3.1  若(H1), (H2)成立, 考虑一般方法$x_{k+1} =x_k +\alpha_kd_k$, 其中$d_k$满足$d_k^T g_k < 0$, 步长$\alpha_k$满足精确线搜索(1.6)式, 则有

$ \begin{equation} \sum\limits_{k\geq 1} \frac{(d_k^T g_k)^2}{\|d_k\|^2} < +\infty. \end{equation} $

(3.2)

证  由(1.6)式, $\alpha_k=\min \{\alpha|\nabla f(x_k+\alpha d_k)^T d_k=0, \alpha>0\}$, 即$g(x_k+\alpha_kd_k)^T d_k=0$.再由Lipschitz条件(3.1), 有$\|g(x_k+\alpha_kd_k)-g(x_k)\|\cdot \|d_k\|\leq L\alpha_k\|d_k\|^2.$由Cauchy-Schwartz不等式可得

$ \begin{equation*} \|g(x_k+\alpha_k d_k)-g(x_k)\| \cdot \|d_k\| \geq[g(x_k+\alpha_k d_k)-g_k]^T d_k=-g_k^T d_k. \end{equation*} $

所以$L\alpha_k\|d_k\|^2\geq-g_k^T d_k$, 即$\alpha_k\geq-\frac{g_k^T d_k}{L\|d_k\|^2}$.又因为由假设可知, 对一切$\alpha>0$都成立

$ \begin{equation*} f_{k+1}\leq f_k+\alpha d_k^T g_k+\frac{\alpha^2}{2}L\|d_k\|^2. \end{equation*} $

令$\alpha^*=\frac{g_k^T d_k}{L\|d_k\|^2}$, 由精确线搜索准则可知

$ \begin{align*} f_k-f_{k+1}&\geq f_k-f(x_k+\alpha^*d_k)\geq \alpha^* d_k^T g_k-\frac{\alpha^2}{2}L\|d_k\|^2\nonumber\\ &=\frac{(g_k^T d_k)^2}{L\|d_k\|^2}-\frac{(g_k^T d_k)^2}{2L\|d_k\|^2} =\frac{(g_k^T d_k)^2}{2L\|d_k\|^2} =C\frac{g_k^T d_k}{\|d_k\|^2}, \end{align*} $

其中$C=\frac{1}{2L}$, 即$f_k - f_{k+1}\geq C\frac{g_k^T d_k}{\|d_k\|^2}$, 对上式从$k=1, 2, \cdots$, 求和, 因为$f(x)$有下界, 故结论成立.

定理3.1  设目标函数满足假设(H1), (H2), 若存在常数$m>0$, 使得$\|g(x)\|\leq m$, $\forall x\in L_0$, 迭代点列$\{x_k\}$由算法A产生, 则有

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

(3.3)

证  假设定理不成立, 所以存在一个常数$C>0$, 有$\|g(x)\|\leq C$.由$d_k+g_k=\beta_kd_{k-1}, $对等式两端取模平方, 并移项得到

$ \begin{equation*} \|d_k\|^2=(\beta_k)^2\|d_{k-1}\|^2-2g_k^2d_k-\|g_k\|^2, \end{equation*} $

由引理2.2可知$|\beta_k|\leq\beta_k^{\rm RMIL}$, 所以

$ \begin{equation*} \|d_k\|^2=(\beta_k^{\rm RMIL})^2\|d_{k-1}\|^2-2g_k^2d_k-\|g_k\|^2. \end{equation*} $

两边除以$(g_k^T d_k)^2$得

$ \begin{align*} \frac{\|d_k\|^2}{(g_k^T d_k)^2}&\leq \frac{(\beta_k^{\rm RMIL})^2\|d_{k-1}\|^2}{(g_k^T d_k)^2}-\frac{\|g_k\|^2}{(g_k^T d_k)^2}-\frac{2}{g_k^T d_k}\nonumber\\ &=\frac{(\beta_k^{\rm RMIL})^2\|d_{k-1}\|^2}{(g_k^T d_k)^2}-(\frac{1}{\|g_k\|}+\frac{\|g_k\|}{g_k^T d_k})^2+\frac{1}{\|g_k\|^2}\nonumber\\ &\leq \frac{(\beta_k^{\rm RMIL})^2\|d_{k-1}\|}{(g_k^T d_k)^2}+\frac{1}{\|g_k\|^2}. \end{align*} $

又因为

$ \begin{equation*} \beta_k ^{\rm RMIL}=\frac{g_k ^T(g_k-g_{k-1})}{\|d_{k-1}\|^2}=\frac{\|g_k\| ^2-g_k^T g_{k-1}}{\|d_{k-1}\|^2}\leq\frac{\|g_k\| ^2}{\|d_{k-1}\|^2}, \end{equation*} $

所以

$ \begin{align*} \frac{\|d_k\|^2}{(g_k^T d_k)^2}&\leq(\frac{\|g_k\|^2}{\|d_{k-1}\|^2})^2\frac{\|d_{k-1}\|^2}{(g_k^T d_k)^2}+\frac{1}{\|g_k\|^2} =\frac{\|g_k\|^2}{\|d_{k-1}\|^2\|d_k\|^2}+\frac{1}{\|g_k\|^2}\nonumber\\ &\leq\frac{1}{\|d_{k-1}\|^2}+\frac{1}{\|g_k\|^2} \leq\cdots\leq\sum\limits_{i=1}^k\frac{1}{\|g_i\|^2}\leq\frac{k}{c^2}. \end{align*} $

所以

$ \begin{equation*} \frac{(g_k^T d_k)^2}{\|d_k\|^2}\geq\frac{c^2}{k}, \end{equation*} $

即

$ \begin{equation*} \sum\limits_{k\geq1}\frac{(g_k^T d_k)^2}{\|d_k\|^2}=+\infty. \end{equation*} $

与引理3.1中的(3.2)式矛盾, 故

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

(3.4)

证毕.