在本文中, 我们考虑以下光滑的无约束优化问题

(1.1) $ \begin{equation} \min\{f(x)\mid x\in{{\Bbb R}} ^n\}, \ \ f:{{\Bbb R}} ^n\rightarrow {{\Bbb R}} , \end{equation} $

其中, $ f $是一个连续的可微的函数. 长期以来, 学者们一直在研究求解无约束优化问题的方法, 并提出多种有效方法, 如牛顿法、最速下降法和共轭梯度法^[1-7]. 共轭梯度法在许多领域都有很强的适用性, 尤其是在求解无约束优化问题中起着重要作用^[8-11]. 在实际的生产中, 无约束优化问题往往是大规模的, 所以如何求解大规模无约束优化问题十分重要, 但由于大规模问题的维度往往非常大, 所以其求解过程十分困难. 由于共轭梯度法其简单的迭代过程、内存需求低等优势, 非线性共轭梯度法是求解大规模无约束优化问题的一种非常普遍且有效的方法. 虽然共轭梯度方法不是目前求解优化问题的最快或最稳定的优化方法. 但是, 当工程学家和数学家求解无约束优化问题时, 共轭梯度法仍是最受欢迎的方法^[12-18]. 求解问题(1.1)的共轭梯度公式设计如下

$ x_{k+1}:=x_k+\alpha_kd_k, k=0, 1, 2, \cdots , $

其中$ \alpha_k $和$ d_k $是共轭梯度方法的两个最重要部分. 它们分别表示第$ k $次迭代期间的步长和搜索方向.

对于一个高效的算法来讲, 选择一个合适的线性搜索技术对算法的性能起着至关重要的作用. 目前, 已有许多单调线搜索方法被提出并应用于共轭梯度算法中, 其中Armijo线搜索是最经典、花费最少的方法之一, 它选择集合$ \left\{ \alpha_k \mid\alpha_k= \bar{\alpha_k}\rho^l_1, l\in \{1, 2, 3, \cdots \}\right\} $中满足以下不等式的最大的$ \alpha_k $作为步长

(1.2) $ \begin{equation} f\left(x_{k}+\alpha_{k} d_{k}\right) \leq f\left(x_{k}\right)+\delta \alpha_{k} g_{k}^{T} d_{k}, \end{equation} $

其中$ \bar{\alpha_k} $是试验步长, 往往取值为1, $ g_k=g(x_k) $是$ f(x) $在点$ x_k $处的梯度, $ \rho_1, \delta\in(0, 1) $是给定的常数. 从根本上说很大一部分已经提出的线性搜索可以看作是(1.2)式的变形和改进.

但是, 在文献[19-22] 中, 作者指出, 迭代序列$ \{x_k\} $有可能会陷入一个非常狭窄和曲折的"山谷"附近, 从而生产非常短或曲折的步长, 在这种情况下大部分的经典单调线性搜索技术可能会失效. 由此可见单调的线性搜索并不能很好的解决所有的问题^{[23, 24]}. 我们通常使用"非单调线性搜索"来解决这一难题, 如文献[19-21, 25-27] 中所述, 非单调线性搜索顾名思义就是, 不是一味的减小函数的值, 当遇到上述情况时, 非单调线性搜索偶尔的会增加目标函数的值. 函数值的增加可以使迭代序列$ x_k $走出这些"短或曲折的步长"的困扰. 因此, 非单调线搜索不仅可以提高算法的收敛速度, 还能增加找到全局最优解的可能性.

在Huang等^[28]的一项研究中, 提出了一种新的非单调线搜索技术. 这种新方法可以看作是对Zhang和Hager^[27]提出的非单调线搜索技术的改进. 但是, 与Zhang和Hager的方法不同, 新的非单调线搜索被证明具有类似于标准Armijo线搜索的优良特性. 其定义如下.

选择初始量$ 0\leq \eta_{\min}\leq \eta_{\max}\leq 1, \rho \leq 1, \ 0<\delta_{\min}<(1-\eta_{\max})\delta_{\max}, \ \delta_{\max}< 1 $, 以及$ \mu>0. $当$ k\ge 1 $, 选择$ \eta_k\in[\eta_{\min}, \eta_{\max}], \ \delta_{k}\in[\delta_{\min}, \frac{\delta_{\max}}{Q{k+1}}] $. 对于初始试验步长$ \bar\alpha_k $, 我们寻找一个$ \alpha_k=\bar\alpha_k\rho^{h_k}\leq \mu $满足以下条件

(1.3) $ \begin{equation} C_{k+1}:=\frac{\eta_{k} Q_{k} C_{k}+f\left(x_{k}+\alpha_{k} d_{k}\right)}{Q_{k+1}} \leq C_{k}+\delta_{k} \alpha_{k} g_{k}^{T} d_{k}, \end{equation} $

其中, $ Q_{k+1}=\eta_kQ_k+1, \ C_0=f(x_0), \ Q_0=1 $, $ h_k $是满足不等式(1.3)的最大整数. 接下来, (1.3)式中$ \delta_k $的存在性通过以下说明给出

$ \begin{eqnarray*} 1<Q_{k+1}=1+\sum\limits_{j=0}^{k} \prod\limits_{i=0}^{j} \eta_{k-j} \leq 1+\sum\limits_{j=0}^{k} \eta_{\max }^{j+1} \leq \sum\limits_{j=0}^{\infty} \eta_{\max }^{j}=\frac{1}{1-\eta_{\max }}, \end{eqnarray*} $

因为$ 0<\delta_{\min}<(1-\eta_{\max})\delta_{\max} $; 有$ \delta_{\min} < \frac{\delta_{\max}}{Q_{k+1}} $. 然后通过(1.3)式得到

$ \begin{eqnarray*} f\left(x_{k}+\alpha_{k} d_{k}\right) \leq\left(Q_{k+1}-\eta_{k} Q_{k}\right) C_{k}+Q_{k+1} \delta_{k} \alpha_{k} g_{k}^{T} d_{k}, \end{eqnarray*} $

因为$ Q_{k+1}-\eta_kQ_k=1 $, 所以, (1.3)式等价于以下不等式

(1.4) $ \begin{equation} f\left(x_{k}+\alpha_{k} d_{k}\right) \leq C_{k}+Q_{k+1} \delta_{k} \alpha_{k} g_{k}^{T} d_{k}. \end{equation} $

显然, Zhang-Hager方法^[27]中的线性搜索规则可以被视为(1.3)式的一种特殊形式.

$ d_k $是搜索方向, 它是解决无约束优化问题的另一个重要组成部分, 我们常常将搜索方向$ d_k $定义如下

(1.5) $ \begin{equation} d_{k}:=\left\{\begin{array}{ll} -g_{k}, & \mbox{ 若 }\ k=0 , \\ -g_{k}+\beta_{k}d_{k-1}, & \mbox{ 若 }\ k \geq 1, \end{array}\right. \end{equation} $

其中, 我们称参数$ \beta_{k} $为共轭参数, 它是一个标量, 在共轭梯度算法中有很重要的地位.

在非线性共轭梯度法中, 共轭参数的取值方式有很多种方法, 其中最经典的共轭参数有: HS方法^[29]、FR方法^[30]、PRP方法^{[31, 32]}、LS方法^[33]、CD方法^[34]和DY方法^[35]. 这些方法中的共轭参数$ \beta_{k} $的定义分别如下

$ \beta_{k}^{H S}: = \frac{ g_{k}^Ty_{k-1}}{d_{k-1}^T y_{k-1}}, \; \; \; \beta_{k}^{D Y}:=\frac{\left\|g_{k}\right\|^{2}}{d_{k-1}^T y_{k-1}}, \; \; \; \beta_{k}^{PRP} := \frac{g_k^Ty_k}{\left\| g_{k-1}\right\| ^2}, $

$ \beta_{k}^{FR} := \frac{\left\| g_k\right\| ^2}{\left\| g_{k-1}\right\| ^2}, \; \; \; \beta_{k}^{LS} := \frac{g_k^Ty_k}{-d_{k-1}^Tg_{k-1}}, \; \; \; \beta_{k}^{CD} := \frac{\left\| g_k\right\| ^2}{-d_{k-1}^Tg_{k-1}}, $

其中, $ y_{k-1}:=g_k-g_{k-1}, s_{k-1}:=x_k-x_{k-1} $以及$ \left\|\cdot \right\| $表示欧几里得范数. 事实上, 这六种方法的共轭参数都有着不同的优势, 但是大致上我们可以将其分为两组：一组是具有良好数值性能的PRP、LS和HS方法, 另一组是具有良好理论收敛性的DY、CD和FR方法. 1970年, Zotendjk通过分析FR算法, 建立了FR方法在精确线性搜索下的的全局收敛性^[36]. 后来, 通过类似的方法DY算法、CD算法和FR算法的收敛性也逐渐被建立完成^{[30, 35]}. 然而, 这几种算法在数值实验中的性能表现不如PRP、HS和LS算法更加优秀, 其造成这种现象的原因在于FR、CD和DY方法的后续步骤, 如果在远离解点的地方生成一了一个较小的步长, 那么之后产生的一系列步长都可能非常短, 这就导致了趋近于收敛点的速度会非常的缓慢^[37]. 但是对于PRP方法、HS方法和LS方法就不会产生上述问题, 如果算法产生了不理想的步长, 这三种算法也可以自动的重启矫正, 所以比起其他方法, 他们在数值实验上会有更好的表现. 近些年, 许多学者在这些经典方法的基础上进行了大量的研究. 比如Hager和Zhang^[38]提出了一种新的共轭梯度法(CG-C), 它是通过修改HS法得到的, 其中$ d_k $的形式如(1.5)式, 共轭参数$ \beta_{k}=\beta_{k}^{NHS}=\max\{\beta_k^N, \mu_k\} $, 其中

$ \begin{eqnarray*} \beta_{k}^{N}:=\frac{g_{k}^{T} y_{k-1}}{d_{k-1}^{T} y_{k-1}}-2 \frac{\left\|y_{k-1}\right\|^{2}}{\left(d_{k-1}^{T} y_{k-1}\right)^{2}} g_{k-1}^{T} d_{k-1}, \quad \mu_{k}:=\frac{1}{\left\|d_{k-1}\right\| \min \left\{\left\|g_{k-1}\right\|, \mu\right\}}. \end{eqnarray*} $

该方法被证明有更加优秀的数值实验表现, 并在一定的假设条件下, 建立了其全局收敛性. Dai和Yuan^[39]也提出了一种求解无约束优化问题的混合共轭梯度方法, 并证明了它的全局收敛性. 顺着这个思路, Liu和Feng^[40]提出了一种基于DY方法求解非线性方程组的方法, 其搜索方向$ d_k $定义为

$ \begin{eqnarray*} d_{k}:=\left\{\begin{array}{ll} -g_{k}, & \mbox{ 若 }\ k=0, \\ -\theta_{k} g_{k}+\beta^{PDY}_{k} d_{k-1}, & \mbox{ 若 }\ k\geq 1, \end{array}\right. \end{eqnarray*} $

其中, $ \theta_k=c-\frac{g_k^Td_{k-1}}{d_{k-1}^Tw_{k-1}} $, $ \beta^{PDY}:=\frac{\left\|g_k \right\|^2 }{d_{k-1}^{T}w_{k-1}}, w_{k-1}:=y_{k-1}+t_{k-1}d_{k-1} $以及$ t_{k-1}:=1+\max\{0, -\frac{d_{k-1}^Ty_{k-1}}{d_{k-1}^Td_{k-1}}\} $.

实验结果表明, PDY算法的数值性能明显优于经典方法. 然而, 共轭梯度法仍有改进的余地. 为了获得更好的性质和数值性能, 学者们开始将目光转向研究三项共轭梯度法. 他们相信因为其良好的性质, 三项共轭梯度法具有更加优秀的性能, 比如三项共轭梯度法很容易获得充分下降性质. 充分下降性的定义为, 存在一个常数$ c>0 $, 使得

(1.6) $ \begin{equation} d_k^Tg_k\leq -c\|g_k\|^2 \end{equation} $

成立, 充分下降性在共轭梯度算法中有很重要的地位比如它能帮助算法更好的获得全局收敛性也可以使收敛性证明的证明过程更加简单明了. 为了实现这一特性, Zhang等^[41]提出了一种三项共轭梯度法, 并将$ d_k $定义为

$ \begin{eqnarray*} d_{k}:=\left\{\begin{array}{ll} -g_{k}, & k=0, \\ { } -g_{k}+\frac{g_k^Ty_kd_{k-1}-d_{k-1}^Tg_ky_k}{\left\| g_{k-1}\right\| ^2}, & k \geq 1. \end{array}\right. \end{eqnarray*} $

很明显, Zhang等人提出的方法具有充分的下降性并且很容易建立其收敛性. 然而, 学者们对该算法的数值性能并不满意, 我们是否可以同时获得PRP、HS和LS方法等良好的数值性能以及FR、CD和DY方法等良好的理论证明性能呢?带着这个疑问, Abubaker等^[42]提出了一类新的搜索方向, 其搜索方向的迭代方式如下

(1.7) $ \begin{equation} d_{k}:=\left\{\begin{array}{ll} -g_{k}, & \mbox{ 若 }\ k=0, \\ { } -\left(1+\beta_{k}^{H S D Y} \frac{g_{k}^{T} d_{k-1}}{\left\|g_{k}\right\|^{2}}\right) g_{k}+\beta_{k}^{H S D Y} d_{k-1}, & \mbox{ 若 }\ k \geq 1. \end{array}\right. \end{equation} $

在这里, $ \beta_{k}^{H S D Y} $是$ \beta_{k}^{M H S } $和$ \beta_{k}^{M D Y} $的凸组合形式, 其表示形式如下

$ \beta_{k}^{H S D Y}:=\left(1-\theta_{k}\right) \beta_{k}^{M H S}+\theta_{k} \beta_{k}^{M D Y}, $

其中的参数定义为

$ \theta_{k}:=\frac{\left\|y_{k-1}\right\|^{2}} {y_{k-1}^T \bar{s}_{k-1}} \in(0, 1), \forall k, \ \ \bar{s}_{k-1}:=s_{k-1}+\max \left\{0, \frac{-s^T_{k-1} y_{k-1}}{\left\|y_{k-1}\right\|^{2}}\right\} y_{k-1}+y_{k-1}, $

$ \beta_{k}^{MHS}: = \frac{ g_{k}^T y_{k-1}}{ d_{k-1}^T w_{k-1}}, \ \ \beta_{k}^{M D Y}:=\frac{\left\|g_{k}\right\|^{2}}{ d_{k-1}^T w_{k-1}}, $

$ w_{k-1}:=y_{k-1}+t_{k-1} d_{k-1}, \ t_{k-1}:=1+\max \left\{0, -\frac{d_{k-1}^T y_{k-1}}{\left\|d_{k-1}\right\|^{2}}\right\}. $

虽然, 搜索方向(1.7)可以获得充分下降性. 但是, 我们能否获得一个性能更加强劲的算法并建立其全局收敛性呢？值得注意的是, 在这个迭代公式中我们仅仅用到了目标函数的梯度信息. 为了提高性能, 新的$ d_k $中我们除了使用函数梯度的信息外, 还将使用函数信息, 更多的信息意味着算法可以更加有目标的完成任务. 基于这一研究思路, 本文提出了一个新的含有函数信息的三项共轭梯度公式, 本文的主要贡献如下.

$ \star $在不使用任何线性搜索技术下, 算法的所有方向都满足充分下降特性.

$ \star $算法的搜索方向$ d_k $不仅有函数的梯度信息还包含函数的信息, 提高了算法的性能.

$ \star $对于无约束优化问题, 证明了给定算法的全局收敛性.

$ \star $实验结果表明, 该算法比现有方法具有更好的数值性能.

$ \star $该算法可用于被脉冲噪声损坏的图像中恢复原始图像的应用中.

本论文的结构如下. 下一节将解释所提出的算法. 第三部分给出了新方法的性质和收敛性结果以及证明. 第四部分给出了"无约束优化问题"和"图像恢复问题"的实验结果. 最后一章将对本文进行总结.

基于上述思想, 在本节中, 我们将提出了一个新的三项共轭梯度公式, 该公式设计为

(2.1) $ \begin{equation} d_{k}:=\left\{\begin{array}{ll} -g_{k}, & \mbox{ 若 }\ k=0, \\ { } -g_{k}+\beta_{k}^{N H S D Y} d_{k-1}-\beta_{k}^{N H S D Y} \frac{g_k^T d_{k-1}}{\left\| g_k\right\| \left\| y^{*}_{k-1}\right\| } y^{*}_{k-1}, & \mbox{ 若 }\ k \geq 1, \end{array}\right. \end{equation} $

其中

$ \beta_{k}^{N H S D Y}:=\left(1-\theta_{k}^*\right) \beta_{k}^{N H S}+\theta_{k}^* \beta_{k}^{N D Y}, $

$ \theta_{k}^*:=\frac{\left\|y_{k-1}^*\right\|^{2}}{ y_{k-1}^{*T} s_{k-1}^*} \in(0, 1), \forall k, \ \ s_{k-1}^*:=s_{k-1}+\max \left\{0, \frac{-s_{k-1}^T y_{k-1}^*}{\left\|y_{k-1}^*\right\|^{2}}\right\} y_{k-1}^*+y_{k-1}^*, $

$ \beta_{k}^{N H S}: = \frac{ g_{k}^T y_{k-1}^*}{ d_{k-1}^T w_{k-1}^*}, \ \ \beta_{k}^{N D Y}:=\frac{\left\|g_{k}\right\|^{2}}{ d_{k-1}^T w_{k-1}^*}, $

$ w_{k-1}^*:=y_{k-1}^*+t_{k-1}^* d_{k-1}, \ t_{k-1}^*:=1+\max \left\{0, -\frac{d_{k-1}^T y_{k-1}^*}{\left\|d_{k-1}\right\|^{2}}\right\}, $

以及

(2.2) $ \begin{equation} y_k^*=y_k+\nu_ks_k, \ \ \nu_k=\max\left\{0, \frac{\left(g\left(x_{k+1}\right)+g\left(x_{k}\right)\right)^{T} s_{k}+2\left(f\left(x_{k}\right)-f\left(x_{k+1}\right)\right)}{\left\|s_{k}\right\|^{2}}\right\}. \end{equation} $

目前, 大多数共轭梯度算法的搜索方向并不含有目标函数本身的信息, 而在本文设计的$ d_k $中, 向量$ y_k^* $不仅具有函数梯度的信息, 而且还具有函数自身信息. 当搜索方向包含函数的信息时, 新的算法会比现有方法在更少的迭代次数和更短的时间内获得满意的结果. 所以含有了函数信息的新方法就可以取得更加良好的理论结果和数值性能. 目前, 已经有很多的学者关注到了这一点, 并取得了一定的贡献^[43]. 就数值性能而言, 这种搜索方向极具竞争力, 这就是为什么我们使用$ y_k^* $而不再使用$ y_k $的原因.

值得注意的是, 根据$ y_{k-1}^* $和$ s_{k-1} $的定义, 我们有

$ \begin{eqnarray*} y^{*T}_{k-1} s^*_{k-1} & \geq &y^{*T}_{k-1}\left(s_{k-1}-\frac{s^T_{k-1} y^*_{k-1}}{\left\|y^*_{k-1}\right\|^{2}} y^*_{k-1}+y^*_{k-1}\right) \\ &= &y^{*T}_{k-1}s_{k-1}-\frac{ s_{k-1}^T y^*_{k-1}}{\left\|y^*_{k-1}\right\|^{2}}\left\|y^*_{k-1}\right\|^{2}+\left\|y^*_{k-1}\right\|^{2} \\ &=&\left\|y^*_{k-1}\right\|^{2} >0, \end{eqnarray*} $

因此

$ \theta_{k}^*:=\frac{\left\|y_{k-1}^*\right\|^{2}}{ y_{k-1}^{*T} s_{k-1}^*} \in(0, 1), $

这就说明了$ \beta_{k}^{N H S D Y} $是$ \beta_{k}^{N H S } $和$ \beta_{k}^{N D Y} $的凸组合形式; 然后我们很容易的可以得到

(2.3) $ \begin{equation} \left|\beta_{k}^{N H S D Y} \right| \leq \left|\beta_{k}^{N H S} \right|+\left|\beta_{k}^{N D Y} \right|. \end{equation} $

对于共轭参数$ \beta_k^{NHS} $和$ \beta_k^{NHS} $的分母, 我们可以得出以下结论

(2.4) $ \begin{eqnarray} d^T_{k-1} w_{k-1}^* \geq d_{k-1}^T y_{k-1}^*+\left\|d_{k-1}\right\|^{2}- d_{k-1}^T y_{k-1}^* & = \left\|d_{k-1}\right\|^{2}>0. \end{eqnarray} $

通过上述对新的搜索方向的描述, 并结合非单调线性搜索技术, 我们可以得到新的算法步骤如下.

算法一

输入: 参数$ Q_0=1, \ \eta_k\in[\eta_{\min}, \eta_{\max}], \ \delta_{k}\in[\delta_{\min}, \frac{\delta_{\max}}{Q{k+1}}], \ \mu>0 $以及$ \rho>1 $.

输出: $ x_k $, $ f_k $.

1) 给定一个初始的点$ x_0\in {{\Bbb R}} ^n $并计算$ d_0=-g(x_0) $和$ C_0=f(x_0) $; 设置$ k=0 $;

2) while $ \left\|g_k\right\|>\epsilon $ do

3) 计算$ Q_{k+1}=\eta_kQ_k+1 $和$ C_{k+1}=\frac{\eta_{k} Q_{k} C_{k}+f\left(x_{k}+\alpha_{k} d_{k}\right)}{Q_{k+1}} $;

4) 寻找步长$ \alpha_k=\bar\alpha_k\rho^{h_k}\leq \mu $满足(1.3)式;

5) 设$ x_{k+1}=x_k+\alpha_kd_k $;

6) 计算$ d_k $ by (2.1)式;

7) $ k:=k+1; $

8) end while

9) End

在本节中, 我们将证明新方法的全局收敛性. 首先, 我们需要建立以下假设来研究算法的某些独特性质.

假设

(1) 水平集$ L_0=\left\{x\mid f(x)\leq f(x_0)\right\} $是有界的;

(2) 目标函数$ f(x) $是两次连续可微的且下有界的, 并且其梯度是Lipschitz连续的, 即有

$ \|g(x)-g(y)\|\leq L\|x-y\|, \, \, \, \, \, \forall x, \, y\in{{\Bbb R}}^n. $

其中$ L $是著名的Lipschitz常数.

注3.1   上述假设意味着存在一个正常数$ G $, 使得

(3.1) $ \begin{equation} \|g_k\|\leq G, \ \ \ \forall x\in L_0. \end{equation} $

引理3.1   让搜索方向$ \{d_k\} $如(2.1)式中定义; 然后, $ d_k $就满足充分下降性质. 即满足不等式

(3.2) $ \begin{equation} g_k^T d_k\leq -\left\| g_k \right\|^{2}. \end{equation} $

证   当$ k=0 $, 很显而易见的有$ g_{k}^Td_{k}\leq -\left\| g_k \right\|^{2}. $

当$ k>1 $, 有

$ \begin{eqnarray*} g_{k}^Td_{k} &=&-\left\| g_k \right\|^{2}+\beta_{k}^{N H S D Y}g_k^T d_{k-1}- \beta_{k}^{N H S D Y} \frac{ g_k^T d_{k-1}}{\left\| g_k\right\| \left\| y^{*}_{k-1}\right\| } g_k^T y_{k-1}^* \\ &\leq& -\left\|g_{k}\right\|^{2}+\beta_{k}^{N H S D Y}g_k^T d_{k-1}-\beta_{k}^{N H S D Y}g_k^T d_{k-1} \\ &\leq &-\left\|g_{k}\right\|^{2}. \end{eqnarray*} $

所以引理成立. 同时使用Cauchy-Schwartz不等式和(3.2)式, 可以得到

(3.3) $ \begin{equation} \left\| d_k\right\| \ge\left\| g_k\right\|. \end{equation} $

引理3.1证毕.

引理3.2   如果$ y_k^* $是由(2.2)定义的, 则我们可以得到

(3.4) $ \begin{equation} \left\| y_k^* \right\|\leq c_0 . \end{equation} $

证   首先使用中值定理, 存在$ \xi_k \in(0, 1) $使得

(3.5) $ \begin{equation} f(x_k+\alpha_{k}d_k)-f(x_k)=\alpha_{k}g(x_k+\xi_k\alpha_{k}d_k)^Td_k. \end{equation} $

接下来, 通过(3.5) 和(3.1) 式, 可以得到以下两种情况.

情况1  当$ \nu_k = 0 $. 因此, 存在一个正常数$ c_1 $使得

$ \left\| y_k^*\right\| =\left\| y_k\right\| \leq \left\| g_{k+1}\right\|+\left\| g_k\right\| \leq 2G. $

取$ c_1\in\left[2G, +\infty\right) $, 则有$ \left\| y_k^*\right\|\leq c_1. $

情况2  当$ \nu_k = \frac{\left(g\left(x_{k+1}\right)+g\left(x_{k}\right)\right)^{T} s_{k}+2\left(f\left(x_{k}\right)-f\left(x_{k+1}\right)\right)}{\left\|s_{k}\right\|^{2}}> 0 $.

$ \begin{eqnarray*} \nu_k &=&\frac{\left(g\left(x_{k+1}\right)+g\left(x_{k}\right)\right)^{T} s_{k}+2\left(f\left(x_{k}\right)-f\left(x_{k}+\alpha_{k}d_k\right)\right)}{\left\|s_{k}\right\|^{2}}\\ &=& \frac{\left(g\left(x_{k+1}\right)+g\left(x_{k}\right)\right)^{T} s_{k}-2\alpha_k g(x_k+\xi_k\alpha_kd_k)^T d_k}{\left\|s_{k}\right\|^{2}}, \end{eqnarray*} $

存在一个正常数$ c_2 $使得

$ \begin{eqnarray*} \left\| y_k^*\right\| &\leq& \left\| y_k\right\| +\left\| \nu_ks_k\right\| \\ &\leq &\left\| y_k\right\| +\left\| \frac{\left(g\left(x_{k+1}\right)+g\left(x_{k}\right)\right ) ^{T} s_{k}-2\alpha_k g(x_k+\xi_k\alpha_kd_k)^T d_k}{\left\|s_{k}\right\|^{2}}s_k\right\| \\ &\leq &\left\| y_k\right\| + \frac{\left\| g\left(x_{k+1}\right)+g\left(x_{k}\right)\right\|\left\| s_{k}\right\| +2 \left\| g(x_k+\xi_k\alpha_kd_k)\right\| \left\| s_k\right\| }{\left\|s_{k}\right\|^{2}} \left\| s_k\right\| \\ &\leq&\left\|y_k \right\| +\left\| g(x_{k+1})+g(x_k)\right\| +2\left\| g(x_k+\xi_k\alpha_kd_k)\right\| \\ &\leq &2\left\| g(x_k+\alpha_{k}d_k)\right\| + 2\left\|g(x_k) \right\|+ 2 \left\| g(x_k+\xi_k\alpha_kd_k)\right\|\\ &\leq &6G . \end{eqnarray*} $

最后, 设$ c_2\in [6G, +\infty) $; 再另$ c_0=\max\{c_1, c_2\} $, 我们就可以得到(3.4)式. 引理3.2得证.

定理3.1   让$ d_k $由公式(2.1)迭代产生, 则总会存在一个试验步长$ \bar{\alpha}_k $使得(1.3)式成立.

该证明与文献[28]中定理1的证明相同, 因此该证明将不再重复. 同时, 从证明中, 我们可以很容易地得到, 对于每一个$ k $, 我们有

(3.6) $ \begin{equation} f_k \leq C_k . \end{equation} $

定理3.2   如果假设(2)成立, $ d_k $是由(2.1)式迭代产生, $ \alpha_k $是由线性搜索(1.3)获得的, 则

(3.7) $ \begin{equation} \lim\limits_{k \to \infty} \alpha_{k} \left\| g_{k}\right\| ^2=0. \end{equation} $

证   通过(1.3)和(3.6)式, 很清楚的可以得到$ C_k $是有下界的.

通过(1.3)式, 很明显, $ C_k $是满足以下条件的递减序列

$ \begin{eqnarray*} \begin{array}{l} C_{1} \leq C_{0}+\delta_{0} \alpha_{0} g_{0}^{T} d_{0}, \\ C_{2} \leq C_{1}+\delta_{1} \alpha_{1} g_{1}^{T} d_{1}, \\ \cdots , \\ C_{k+1} \leq C_{k}+\delta_{k} \alpha_{k} g_{k}^{T} d_{k}, \\ \cdots. \end{array} \end{eqnarray*} $

通过$ \delta_k $的定义, 对于所有的$ k $, $ \delta_k $都严格大于0. 然后, 通过将上述不等式的两边从$ k=0 $到$ \infty $相加, 并使用(3.2)式, 我们可以得到

$ \sum\limits_{k=0}^{\infty}\delta_k\alpha_{k}\left\| g_k\right\| ^2 \leq \sum\limits_{k=0}^{\infty} -\delta_k\alpha_{k} g_{k}^{T} d_{k}<C_0-C_{\infty} <\infty. $

通过上述不等式, 我们完成了证明.

定理3.3   假设(2)成立, 序列$ \{x_k\} $由算法一生成；然后, 存在一个正常数$ c_3 $, 使算法一生成的步长$ \alpha_k $满足

(3.8) $ \begin{equation} \alpha_{k} > c_3 \frac{\left\|g_{k}\right\|^2}{\left\|d_{k}\right\|^{2}}. \end{equation} $

证   根据(1.3), 当$ k $足够大时, 通过线性搜索条件(1.4), 很明显, $ \alpha_{k}\rho^{-1} $不满足(1.4)式, 这意味着

$ f\left(x_{k}+\alpha_{k}\rho^{-1} d_{k}\right) > C_{k}+Q_{k+1} \delta_{k} \alpha_{k}\rho^{-1} g_{k}^{T} d_{k}. $

使用(3.6)式, 则可以获得以下不等式

(3.9) $ \begin{equation} f\left(x_{k}+\alpha_{k}\rho^{-1}d_{k}\right)-f(x_k) >Q_{k+1} \delta_{k} \alpha_{k}\rho^{-1} g(x_k)^{T} d_{k}. \end{equation} $

通过(3.5)式, 假设(2)成立以及$ \xi_k\in(0, 1) $, 则我们可以获得

(3.10) $ \begin{eqnarray} f(x_k+\rho^{-1}\alpha_{k}d_k)-f(x_k)&=&\rho^{-1}\alpha_{k}g(x_k+\xi\alpha_{k}\rho^{-1}d_k)^Td_k{}\\ &=&\rho^{-1}[\alpha_{k}g(x_k+\xi_k\alpha_{k}\rho^{-1}d_k)^Td_k+\alpha_{k}g(x_k)^Td_k-\alpha_{k}g(x_k)^Td_k ] {}\\ &=&\rho^{-1}\alpha_{k}(g(x_k+\xi_k\alpha_{k}\rho^{-1}d_k)-g(x_k))^Td_k+\rho^{-1}\alpha_{k}g(x_k)^Td_k{}\\ &\leq& L\xi_k\rho^{-2}\alpha_{k}^2\left\| d_k\right\| ^2+\rho^{-1}\alpha_{k}g(x_k)^Td_k{}\\ &< &L\rho^{-2}\alpha_{k}^2\left\| d_k\right\| ^2+\rho^{-1}\alpha_{k}g(x_k)^Td_k. \end{eqnarray} $

结合(3.9)和(3.10)式, 可以得到

$ \alpha_{k} > \frac{\rho \left(Q_{k+1} \delta_{k}-1\right) g_{k}^{T} d_{k}}{L\left\|d_{k}\right\|^{2}}. $

由$ \delta_{k}\in[\delta_{\min}, \frac{\delta_{\max}}{Q{k+1}}] $, $ 0<\delta_{\max}<1 $和$ g_k^Td_k\leq -\left\| g_k\right\| ^2 $, 通过整理上述不等式, 我们可以得到

$ \alpha_{k} > \frac{\rho\left(1-Q_{k+1} \delta_{k}\right) \left\| g_{k}\right\| ^{2}}{L \left\|d_{k}\right\|^{2}}\ge\frac{\rho\left(1-\delta_{\max}\right) \left\| g_{k}\right\| ^{2}}{L\left\|d_{k}\right\|^{2}}. $

最后, 设$ c_3=\frac{\rho \left(1-\delta_{\max}\right)}{L} $则(3.8)式成立. 定理3.3证毕.

定理3.4   如果假设(1)(2)成立, 并且序列$ \{x_k, \alpha_k, g_k, d_k\} $是由算法一生产, 可以得到

(3.11) $ \begin{equation} \lim\limits_{k \to \infty}\inf\left\| g_k\right\| =0. \end{equation} $

证   我们将使用反证法的思想, 存在一个常数$ \epsilon^* $和一个下标$ k_0 $, 假设有

(3.12) $ \begin{equation} \left\|g_k \right\| >\epsilon^* \ \ \ \forall k\ge k_0. \end{equation} $

通过(3.3)式得到

$ \left\|d_k \right\| >\epsilon^* \ \ \ \forall k\ge k_0. $

再使用(2.1), (2.3), (2.4), (3.3), (3.4)式和Cauchy-Schwartz不等式可以得到

当$ k=0 $, 有$ \left\| d_0\right\| =\left\| g_0\right\| ; $

当$ k>0 $, 有

$ \begin{eqnarray*} \left\| d_{k}\right\| &=&\left\| -g_{k}+\beta_{k}^{N H S D Y} d_{k-1}-\beta_{k}^{N H S D Y} \frac{g_k^T d_{k-1} }{\left\| g_k\right\| \left\| y^{*}_{k-1}\right\| } y^{*}_{k-1}\right\| \\ &\leq &\left\| g_k\right\| +\left| \beta_{k}^{N H S D Y} \right|\left\| d_{k-1}\right\|+\left|\beta_k^{NHSDY} \right| \frac{\left\| g_k\right\|\left\| y_{k-1}^*\right\| }{\left\| g_k\right\| \left\| y^{*}_{k-1}\right\| } \left\| d_{k-1}\right\| \\ &\leq &\left\| g_k\right\| +2\left| \beta_{k}^{N H S D Y} \right|\left\| d_{k-1}\right\|\\ &\leq &\left\| g_k\right\| +2( \left| \beta^{NHS}_k\right| +\left | \beta^{NDY}_k\right|)\left\| d_{k-1}\right\| \\ &\leq &\left\|g_k \right\| +2 \frac{\left\| g_k\right\| \left\| y_{k-1}^*\right\|+\left\|g_k \right\|^2 }{d_{k-1}^Tw_{k-1}^* } \left\|d_{k-1} \right\| \\ &\leq &\left\|g_k \right\| +2 \frac{\left\| g_k\right\| \left\| y_{k-1}^*\right\|+\left\|g_k \right\|^2 }{\left\| d_{k-1}\right\|^2 } \left\|d_{k-1} \right\| \\ &\leq &\left\|g_k \right\| + 2\frac{c_0\left\| g_k\right\| +\left\|g_k \right\|^2 }{\left\| d_{k-1}\right\| } \\ &= &(1 + 2\frac{c_0 +\left\|g_k \right\| }{\left\| d_{k-1}\right\| } )\left\|g_k \right\|\\ &\leq &(1+\frac{2(c_0+G)}{\epsilon^*})\left\|g_k \right\|. \end{eqnarray*} $

设$ c_4=(1+\frac{2(c_0+G)}{\epsilon^*}) $, 有

(3.13) $ \begin{equation} \left\| d_k\right\| \leq c_4\left\|g_k \right\|, \ \ k=0, 1, 2, .\cdots \end{equation} $

通过(3.8)式, 使用(3.13)式, 则有

$ \begin{eqnarray*} \alpha_{k} > c_3 \frac{\left\|g_{k}\right\|^2}{\left\|d_{k}\right\|^{2}}\geq \frac{c_3}{c_4^2}. \end{eqnarray*} $

这就与(3.7)式产生了矛盾, 所以(3.11)式是成立的. 定理3.4证毕.

在这一章节中, 我们设计了两个实验来研究算法的性能, 并将所提出的算法与其他几种经典的算法进行计算效率和性能的比较. 这两个实验分别是无约束优化问题和图像恢复问题, 在之后的小节中会详细的介绍这两个实验和实验的结果分析. 接下来我们先将列出一些关于实验的信息和参数.

使用的数学软件: MATLAB R2017a.

算法运行环境: Intel(R) Core (TM) i7-4710MQ CPU @ 2.50 GHz, 8.0 GB, RAM, 以及Windows 10操作系统.

实验中使用的方法以及图例曲线解释如下.

方法1 (M1): NHSDY方法(算法一).

方法2 (M2): 一种PDY类型的方法^[40].

方法3 (M3): 一种在Wolfe-Powell(WP)线性搜索技术下的PRP方法.

方法4 (M4): 一个结合了"HSDY"方法(1.7)和线性搜索技术(1.3)的方法.

方法5 (M5): 一个结合了(2.1)式和标准Armijo线性搜索技术(1.2)的方法

为了验证NHSDY方法(方法1)的数值性能, 我们通过使用不同的方法解决无约束优化问题来进行对比, 本文测试了算法的迭代次数(NI)、计算函数的次数和其梯度次数之和(NFG)以及算法的CPU时间(CPU). 同时, 在本数值实验中的三个实验对照组分别是: 方法2、方法3和方法4. 实验中使用的参数数据如下.

被测试问题的维度  3000维, 9000维以及15000维.

使用到的参数   所有的算法都在参数$ \rho=0.5, \eta_k=0.1, \delta_k=0.4 $, $ \eta_k=0.1 $和$ \sigma =0.5 $运行.

停止准则(Himmelblau停止准则^[44])   对于所有的算法, 如果满足条件$ \left\| g_k \right\| \leq \epsilon=10^{-6} $或者迭代次数大于等于$ 1000 $则停止. 如不满足此条件, 则当满足$ \left|f(x_k) \right|>e_1 $时, 让$ stop_1=\frac{\left| f(x_k)-f(x_{k+1})\right| }{f(x_k)} $; 否则, 让$ stop_1=\left| f(x_k)-f(x_{k+1})\right| $. 如果条件$ \left\|g(x)\right\|< \epsilon $或$ stop_1<e_2 $满足则其中一个条件则停止算法, 其中$ e_1=e_2=10^{-5} $.

被测试问题   本实验测试了74个无约束优化问题, 详细的问题列表可以见Andrei的著作^[12].

在Dolan和Moré发表的论文^[45]中, 提出了一种分析和比较这些算法效率的方法. 在本文中将使用这种方法对四种不同的算法进行比较. 图中水平和垂直坐标的参数表示如下: $ \tau $表示这个方法在解决其中一个问题时使用的性能(NI、NFG或CPU时间)和所有方法中的最佳性能的比值的倒数, $ P_{p:r(\rho, s)\leq \tau} $表示当此方法的比率小于参数$ \tau $时, 所能解决的问题占总问题的比值. 这样, 我们就可以对四种方法进行比较, 得到合理的分析. 图 1-3表明, 在所有算法中, "NHSDY"方法(方法1)的性能从某种意义上来讲是最好的, 因为在图一中它以最少的迭代次数(NI)解决了大约53%的测试问题, 而"方法2"、"方法3"和"方法4"最多只解决了42%的测试问题. 同时, 图 2显示, 方法1在计算函数值和梯度值总次数(NFG)的问题上以最少的次数解决了38%的测试问题, 尽管这一结果并不理想, 也不优于方法2的结果. 然而, 当我们放大横坐标, 当$ \tau=15 $时, 方法一可以解决98%以上的问题, 这个结果表明方法1有更强的鲁棒稳定性, 并且对比其他算法也是有一定的竞争力的. 每个算法的CPU时间如图 3所示, 不难看出, 方法1略优于方法2, 明显优于其他两种算法. 综上所述, 本文提出的算法具有一定的优势和较强的竞争力.

在本节中, 我们将解决以下无约束优化问题, 以消除脉冲噪声

$ \min _{x \in {{\Bbb R}} ^{n}} f_{j}(x)=\lambda \sum\limits_{i=1}^{n \times 1} \phi_{j}\left(\mu, \left[W^{*} x\right]_{i}\right)-\lambda \varrho \left\|W^{*} x\right\|_{2}+\frac{1}{2}\|A x-b\|_{2}^{2}, \varrho \in {{\Bbb R}} , j=2, \ldots, $

其中$ W\in {{\Bbb R}} ^{n\times n} $是对应的合成运算符, 它被列为我们用来合成信号$ x=W\varrho $的波形, $ W^* $是分析运算符, $ [W^{*} x]_{i} $是第$ i $次的$ W^*x $元素, $ \phi_j $是第$ j $次具有参数$ \mu $的保边势函数, 最后$ \lambda>0 $是一个常数.

我们的主要工作是从被脉冲噪声破坏的图像中恢复原始图像. 随着对图像处理需求的不断增加, 人们越来越关注如何利用优化方法来解决图像处理问题. 在这个实验中, 我们选择了三种不同的算法, 方法1、方法4和方法5来恢复相同的图像, 以对比三种算法的性能.

实验中使用的参数数据如下.

停止准则  如果条件$ \frac{\left\| g_{k+1}-g_k\right\| }{\left\| g_k\right\|}<10^{-4} $或$ \frac{\left\| x_{k+1}-x_k\right\| }{\left\| x_k\right\|}<10^{-4} $其中一个满足, 则停止程序.

噪声信息   $ 25\% $, $ 50\% $, $ 75\% $ salt-and-pepper噪音.

参数  本实验中使用的参数与上一个实验中使用的参数相同.

被测试问题   从被脉冲噪声破坏的图像中恢复原始图像. 本实验使用的图像分别是, Lena ($ 512\times 512 $), Barbara ($ 512\times 512 $), Man ($ 1024\times 1024 $) 以及Baboon ($ 512\times 512 $).

从图 4-6和表 1可以明显看出, 这三种算法都可以恢复被salt-and-pepper噪声损坏的图像, 无论是在噪音浓度25%、50%还是75%下都可以成果. 此外, 数据显示NHSDY算法(方法1)所使用的CPU时间要比方法4和方法5都短. 简言之, 不难得出以下结论: (ⅰ) 这三种算法在图像恢复应用中都是有效的; (ⅱ) 随着噪声浓度的增加, 所使用的CPU时间也随之增加, 即图像恢复的成本增加; (ⅲ) NHSDY算法(方法1)可以说是一种比较高效率的算法, 因为它相比其他两种算法可以在更短的CPU时间里完成任务, 表明新提出的这种算法具有很强的竞争力和良好的性能. 总之通过以上实验结果和分析可以得出结论, 新提出的算法有非常有前途和竞争力的.

本文提出了一种具有非单调线性搜索的三项共轭梯度算法, 其中搜索方向中的共轭参数是由两个著名共轭参数(HS和DY)组合成的凸组合形式. 给出的新方法具有以下优秀性质: (ⅰ) 在不需要假设和线性搜索的支持下, 满足了充分下降性质; (ⅱ) 在一定合理且常规的假设下, 建立了该方法在非凸函数的全局收敛性; (ⅲ) 函数的信息包含在搜索方向$ d_k $中, 这比现有搜索方向中包含的信息更多, 可以使新方法获得更良好的属性; (ⅳ) 数值实验表明, 该算法与同类算法相比, 具有一定的竞争力.

今后, 有几个方面需要注意. 第一个问题是: 如果将凸组合的思想应用于拟牛顿法, 它是否也可以像本文提出的方法一样具有更好的性质?其次, 我们能否找到其他具有良好性质的共轭梯度公式吗?这可以说是今后的第二条工作. 众所周知, 共轭梯度算法在解决优化问题的有效方法中起着重要作用, 它应该被体现在近年来许多新的研究课题中, 这是我们今后工作的第三个方面.

数据的可用性  所有数据都包含在论文中, 可以使用.

利益问题   没有潜在的利益冲突.