论文笔记|Global convergence of a descent PRP type conjugate gradient method for nonconvex optimization

0 摘要

非线性共轭梯度法因其较低的内存占用与较低的运算开销而常被应用于求解大规模无约束优化问题。本文提出了一种新型Polak-Ribiére-Polyak（PRP）型共轭梯度算法，在无需任何线搜索过程且具有充分下降特性的条件下即可实现应用。其显著特点是能够在满足标准Wolfe与Armijo搜索条件的情况下，并不需要预先假设目标函数具有凸性这一前提即可保证良好的全局收敛性质。通过数值实验结果可以看出所提出的共轭梯度算法表现出良好的收敛性和有效性。

1 引言

本文考虑的无约束优化问题：

最速下降法、牛顿法、拟牛顿法以及共轭梯度（CG）方法[27]均被广泛应用于求解该类优化问题。然而，在面对大规模优化问题时，共轭梯度方法展现出显著的优势：其收敛速度较快且无需存储相关矩阵。这种特性使得共轭梯度方法成为解决此类大规模优化问题的重要手段之一。其迭代过程如下：

其中x_k代表当前迭代所处的空间维度数，在优化过程中α_k是由精确线搜索算法计算出的步长参数值，在此过程中我们采用定义明确的方向向量d_k来进行下一步迭代

其中gk表示f在点xk处的梯度，βk称为共轭参数.

共轭梯度法主要应用于金融、医疗、工程、经济、信号处理以及图像复原等多个领域。第一种共轭梯度法是由Hestenes与Schmidting在1952年首次提出作为解决线性方程组问题的有效手段，并被称为线性共轭梯度方法。值得注意的是，在非二次函数情形下，基于不同参数的选择则会导出一系列变种的共轭梯度算法。

βk的著名公式是由：

其中| \cdot |表示向量的欧氏范数.与之对应的共轭梯度法分别被称为PRP (波拉克-里比埃尔-波利亚克)[28]、HS ( Hestenes-施蒂费尔 )[20]、DY ( Dai-yuan )[6]、FR ( Fletcher-Reeves )[16]、CD ( Conjugate Descent )[15]以及LS ( Liu-Storey )[26].在各种不同的共轭梯度技术中,HS、LS以及PRP方法通常被视为实践上非常有效的经典方法.而FR、CD和DY方法则被认为具有较为优良的理论收敛性质.如果函数f是一个严格凸二次函数,并且\alpha_k由精确线搜索确定,那么上述公式将等价地成立.然而,对于一般的目标函数而言,这些方法的表现差异却相当显著.我们参考了文献[7],综述文章[19],以及相关的参考文献,以此了解当前关于共轭梯度法的研究进展.

【综述：

针对普遍函数，在全球范围内已有诸多学者探究了该方法在全局收敛特性上的应用与效果[...]

最近,Zhang [34]对Wei等[29]提出的Wei-Yao-Liu非线性共轭梯度法进行了必要的修正,使其满足充分下降条件并实现全局收敛.在此基础上,Dai等[8]提出了改进型共轭梯度算法,命名为DPRP共轭梯度法.

其中参数μ满足μ > 1.基于Wolfe准则或Armijo规则,研究者们证明该算法在修正后的PRP共轭梯度方法中表现出良好的下降性和全局收敛性。

②Jiang等[ 22 ]对DY公式的分母进行了修正，得到了如下修正的DY共轭梯度法

其中μ > 1 .他们研究了修正方法的全局收敛性，并给出了相应的数值结果.

③Jiang等[ 24 ]提出了一种修正的PRP共轭梯度法，即

他们的方法无需依赖于线搜索，在每次迭代时都能生成下降方向向量。基于标准Wolfe线搜索条件下的情况下可证得全局收敛性

④近期，Aminifard和Babaie - Kafaki [ 1 ]基于自适应Dai - Liao共轭条件[ 5 ]与充分减幅条件提出了修正型PRP共轭梯度算法；其搜索方向如下所述：

相较于而言

为了解决这一缺点问题,Dong [14] 对[1]中的方法进行了优化.然而,他证明了这种优化方法仅在 强Wolfe线搜索条件下 才能实现全局收敛.

借鉴了相关文献的思想，本文提出了一个新的共轭梯度算法，并且其中βk取如下形式：

式中：μ > 2。

这种新的PRP型共轭梯度法具有两个显著特点：首先，在不依赖任何线搜索过程的前提下实现了充分下降性质；其次，在基于标准Wolfe准则和标准Armijo准则下展现出良好的全局收敛特性，并且无需预先知道目标函数是否为凸函数。此外，在上述两种线搜索策略下均表现出了良好的收敛效果。为了验证该算法的有效性与可靠性，我们进行了数值试验并统计了实验结果

论文其余部分架构:
在第二部分中, 我们系统地阐述了修正后的PRP共轭梯度算法, 并验证了其搜索方向的充分下降性(证实第一条性质); 第三部分详细探讨了我们在Wolfe线搜索及Armijo线搜索框架下对方法的全局收敛性进行了深入分析(证实第二条性质); 第四部分综述了一些数值实验结果以检验我们的方法, 并将其实现效果与现有的几种算法进行了对比分析.

2. Algorithm and its property

在此段落中, 我们将详细阐述PRP型共轭梯度法. 旨在阐述我们的方法, 我们计划探讨两种常见的非精确线搜索策略.

标准的Wolfe线搜索是寻找满足的αk：

现在，我们正式提出我们的方法如下。为了简单起见，我们称之为NPRP方法。

接下来，我们将证明算法2.1产生的搜索方向满足充分下降条件。

3. Global convergence

本节旨在探讨所提方法的全局收敛性质。为此，我们需要假设目标函数f(x)满足以下条件

这些假设表明存在两个正数a和b（均为正值），对于所有属于集合U的x值而言，
满足||x|| ≤ a以及||g(x)|| ≤ b这两个条件。
随后，在采用Wolfe线搜索条件或Armijo线搜索条件进行分析后，
我们研究了算法2.1的收敛性性质。

3.1. Global convergent analysis under the Wolfe line search conditions

基于上述经典假设以及标准Wolfe线搜索准则（编号分别为2.1至2.2），我们首先着重证明了所提出的算法在满足Wolfe线搜索准则条件下的全局收敛性质。该引理具有显著的重要性，在评估所提出算法全局收敛性的过程中扮演了关键角色。它与文献[27]中的方法具有相似之处，在此省略详细论证过程

基于前述引理，在满足标准Wolfe线搜索条件中的（2.1）至（2.2）阶段内推导可得：该算法全局收敛。

3.2. Global convergent analysis under the Armijo line search conditions

随后，在满足 Armijo 线搜索条件的前提下

为了实现算法2.1在Armijo线搜索条件下达到全局收敛的目标，在此阶段我们先阐述以下关键引理

因此，

基于上述引理，我们给出了算法2.1在标准Armijo线搜索下的全局收敛性。

5. Conclusions

本文基于Polak-Ribiere-Polyak[28]提出的共轭参数进行了扩展，并在此基础上提出了一个新的PRP型共轭梯度算法。该算法满足充分下降条件且无需任何线搜索即可实现优化目标。我们分别在标准Wolfe线搜索框架和基于目标函数非凸性的标准Armijo框架下探讨了算法的全局收敛性问题，并通过大量数值试验验证了其有效性。此外，在未来的研究工作中我们将着重于确定该算法参数的最佳取值范围，并进一步提高算法的实际计算效率；同时计划将其应用到图像复原与压缩感知等实际工程问题中去