数学杂志  2021, Vol. 41 Issue (3): 212-218   PDF    
扩展功能
加入收藏夹
复制引文信息
加入引用管理器
Email Alert
RSS
本文作者相关文章
马国栋
江羡珍
靳文慧
具有充分下降性的改进FR共轭梯度法
马国栋, 江羡珍, 靳文慧    
广西民族大学数学与物理学院, 广西 南宁 530006
摘要:本文研究了大规模无约束优化问题,提出了一个基于改进的FR共轭参数公式的共轭梯度法.不依赖于任何线搜索准则,算法所产生的搜索方向总是充分下降的.在标准Wolfe线搜索准则下,获得了新算法的全局收敛性.最后,对所提出的算法进行了初步数值实验,其结果表明所改进的方法是有效的.
关键词无约束优化    共轭梯度法    标准Wolfe线搜索    全局收敛性    
THE IMPROVED FR CONJUGATE GRADIENT METHOD WITH SUFFICIENT DESCENT PROPERTY
MA Guo-dong, JIANG Xian-zhen, JIN Wen-hui    
College of Mathematics and Physics, Guangxi University for Nationalities, Nanning Guangxi 530006
Abstract: In this paper, we consider solving large-scale unconstrained optimization, based on the improved parameter formula of the FR method, a conjugate gradient method that is proposed. Without any line search, we proved that the search direction always satisfied sufficient descent condition at each iteration. The global convergence of the proposed method is proved under the standard Wolfe inexact line search condition. Finally, some elementary numerical experiments are reported, which show that the algorithm is promising.
Keywords: unconstrained optimization     conjugate gradient method     Wolfe line search     global convergence    
1 引言

共轭梯度法是求解大规模光滑无约束优化问题$\min\{f(x)|\ x\in R^n\}$的有效方法之一, 其具有算法结构简单, 无需矩阵存储和二次终止性等优点, 特别适用于求解大规模优化问题, 其迭代公式一般形如

$ \begin{eqnarray} \label{1.1} x_{k+1}=x_k+\alpha_k d_k, \end{eqnarray} $ (1.1)
$ \begin{eqnarray}\label{1.2}d_k=\left\{ \begin{array} {lll}-g_k, &k=1;\\ -g_k+\beta_kd_{k-1}, &k\geq2, \end{array}\right. \end{eqnarray} $ (1.2)

其中$g_k=\nabla f(x_k)$, $\alpha_k$为搜索步长, $d_k$为搜索方向, $\beta_k$为搜索方向$d_k$的调控参数. 不同的$\beta_k$对应不同的共轭梯度法, 著名的$\beta_k$计算公式有:

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

与上述四个公式相对应的共轭梯度法分别称为HS方法[1]、FR方法[2]、PRP方法[3, 4]和DY方法[5]. 其中, FR方法和DY方法具有良好的收敛性质, 而HS方法和PRP方法则数值性能优良. 因此, 为寻求收敛性和数值效果都理想的方法, 基于上述调控参数所建立的共轭梯度法已被广泛研究,且获得很多理论性质和数值效果均优良的改进共轭梯度法[6-14]. 如, 文[9]中的算法改进了DY公式

$ \begin{eqnarray}\label{s1.3}\displaystyle \beta_k^{JMJ}=\frac{{\|g_k\|^2}-\frac{\|g_k\|}{{\|d_{k-1}\|}}|g_k^Td_{k-1}|}{{d_{k-1}^T}(g_k-g_{k-1})}, \end{eqnarray} $ (1.3)

在标准Wolfe线搜索准则下获得了算法的全局收敛性, 且具有较为理想的数值效果. 基于文[9]的思想, 文[10]修正了FR共轭梯度参数公式

$ \begin{eqnarray}\label{s1.4}\displaystyle \beta_k^{N}=\frac{{g_k^T}{(g_k-\frac{\|g_k\|}{\|d_{k-1}\|}d_{k-1})}}{{\|g_{k-1}\|}^2}, \end{eqnarray} $ (1.4)

由式(1.4)产生的搜索方向在强Wolfe线搜索准则下满足充分下降条件, 然而由此共轭梯度参数公式所建立的算法未能获得全局收敛性. 鉴于此, 受文[9, 10]思想的启发, 本文将公式(1.4)进一步修正为:

$ \begin{eqnarray}\label{s1.5} \beta_k^{MJJ}=\frac{{\|g_k\|^2}-\frac{({g_k^Td_{k-1}})^2}{\|d_{k-1}\|^2}}{{\|g_{k-1}\|}^2+u\max\{|g_k^Td_{k-1}|, |g_k^Tg_{k-1}|\}}, \end{eqnarray} $ (1.5)

其中参数$u>1$. 显然, 在精确线搜索条件下, 且目标函数为严格凸二次函数, 则式(1.5)退化为FR共轭梯度参数公式.

本文余下部分组织如下: 基于公式(1.5), 第二部分建立了算法框架, 不依赖于任何线搜索条件, 以新公式为方向调控参数所产生的搜索方向总是充分下降的. 第三部分在标准Wolfe非精确线搜索条件下, 获得了算法的全局收敛性; 最后对所提出的算法进行数值测试, 并与同类算法进行比对.

2 算法框架及充分下降性

基于本文所改进的共轭参数公式(1.5), 建立算法框架A:

初始化  任取初始点${x_1}\in{R^n}$, 给定精度$\varepsilon>0$, 参数$u>1$, $d_1=-g_1, k=1$.

步骤1  若${\|g_k\|} < \varepsilon$, 则停止. 否则, 转步骤2.

步骤2   由某个非精确线搜索准则求步长$\alpha_k$.

步骤3   令${x_{k+1}={x_k}+{\alpha_k}{d_k}}$, 由式(1.5)计算${\beta_{k+1}^{MJJ}}$. 令$d_{k+1}=-g_{k+1}+\beta_{k+1}^{MJJ}d_k, \ k: =k+1$, 返回步骤1.

首先, 给出共轭参数公式(1.5)和算法框架A所产生的搜索方向具有如下的性质.

引理2.1   对于任意$k\geq1$, 总有$0\leq\beta_k^{MJJ}\leq\beta_k^{FR}$恒成立.

  设$\theta_k$$g_k^T$$d_{k-1}$的夹角, 有

$ {{|{cos\theta_k}|}^2}=\frac{|{g_k^T}{d_{k-1}}|^2}{{\|g_k\|}^2{\|d_{k-1}\|}^2}. $

于是

$ \beta_k^{MJJ} %{\displaystyle =\frac{{\|g_k\|^2}-\frac{({g_k^Td_{k-1}})^2}{\|d_{k-1}\|^2}}{{\|g_{k-1}\|}^2+u\max\{|g_k^Td_{k-1}|, |g_k^Tg_{k-1}|\}}} {\displaystyle=\frac{{\|g_k\|^2}{[1-\frac{({g_k^Td_{k-1}})^2}{{\|g_k\|}^2\|d_{k-1}\|^2}]}}{{\|g_{k-1}\|}^2+u\max\{|g_k^Td_{k-1}|, |g_k^Tg_{k-1}|\}}} {\displaystyle =\frac{{\|g_k\|^2}{(1-{|cos\theta_k|^2})}}{{\|g_{k-1}\|}^2+u\max\{|g_k^Td_{k-1}|, |g_k^Tg_{k-1}|\}}, } $

进而, 可得

$ 0\leq\beta_k^{MJJ}\leq\frac{\|g_k\|^2}{{\|g_{k-1}\|}^2+u\max\{|g_k^Td_{k-1}|, |g_k^Tg_{k-1}|\}}\leq\frac{\|g_k\|^2}{\|g_{k-1}\|^2}=\beta_k^{FR}. $

故引理获证.

引理2.2  对所有的$k\geq1$$u>1$, 由算法框架A所产生的搜索方向$d_k$满足

$g_k^Td_k\leq-(1-\frac{1}{u}){\|g_k\|}^2, $

即方向$d_k$是充分下降的.

  由$\beta_k^{MJJ}$的定义, 易知

$ \begin{eqnarray} \label{2.1}0\leq\beta_k^{MJJ}=\frac{{\|g_k\|^2}-\frac{({g_k^Td_{k-1}})^2}{\|d_{k-1}\|^2}}{{\|g_{k-1}\|}^2+u\max\{|g_k^Td_{k-1}|, |g_k^Tg_{k-1}|\}}\leq\frac{\|g_k\|^2}{u\max\{|g_k^Td_{k-1}|, |g_k^Tg_{k-1}|\}}. \end{eqnarray} $ (2.1)

将(1.2)两端与$g_k$作内积, 利用(2.1), 得

$ \begin{eqnarray*} g_k^Td_k&&{={g_k^T}({-g_k}+\beta_k^{MJJ}d_{k-1})} {\leq{{-\|g_k\|}^2}+\beta_k^{MJJ}|g_k^Td_{k-1}|} \\&&{\displaystyle\leq{{-\|g_k\|}^2}+\frac{\|g_k\|^2}{u\max\{|g_k^Td_{k-1}|, |g_k^Tg_{k-1}|\}}|g_k^Td_{k-1}|}\\&&{\displaystyle\leq-(1-\frac{1}{u}){\|g_k\|}^2.} \end{eqnarray*} $

因此, 算法框架A所产生的搜索方向是充分下降的. 故引理获证.

由引理2.2可知, 不依赖于任何线搜索条件, 以新公式为方向调控参数所产生的搜索方向总是充分下降的.

为了便于后续的描述, 算法框架A采用如下标准$Wolfe$非精确线搜索准则求步长所产生的算法称为算法MJJ, 即步长$\alpha_k$满足:

$ f(x_k+\alpha_kd_k)\leqslant{f(x_k)+\delta\alpha_kg_k^Td_k}, $ (2.2)
$g(x_k+\alpha_kd_k)^Td_k\geqslant\sigma g_k^Td_k, $ (2.3)

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

3 算法的全局收敛性

为获得算法MJJ的全局收敛性, 首先给出算法所需的两个常规假设条件.

(A1)  目标函数$f(x)$在水平集$\Lambda=\{x\in R^n|f(x)\leqslant f(x_1)\}$上有下界, 其中$x_1$为算法的初始点.

(A2)  目标函数$f(x)$在水平集$\Lambda$的某邻域$U$内可微, 其梯度函数$g(x)=\nabla f(x)$满足Lipschitz条件, 即存在常数$L>0$, 使$\|g(x)-g(y)\|\leq L\|x-y\|, \forall\ x, y\in U$.

下面引理给出著名的Zoutendijk条件, 其在共轭梯度法全局收敛性分析中起着非常重要的作用.

引理3.1  设假设A1和A2成立, 考虑一般迭代方法(1.1)-(1.2), 若搜索方向$d_k$满足$g_k^Td_k < 0$, 步长因子$\alpha_k$满足标准Wolfe线搜索准则, 则$\sum\limits_{k=1}^\infty\frac{(g_k^Td_k)^2}{{\|d_k\|}^2} < \infty$成立. 特别地, 若方向$d_k$是充分下降的, 有$\sum\limits_{k=1}^\infty\frac{{\|g_k\|}^4}{{\|d_k\|}^2} < \infty$成立.

由引理2.1, 引理2.2和引理3.1可建立算法MJJ的全局收敛性定理.

定理3.2  设假设A1和A2成立, 点列$\{x_k\}$由(1.1)和(1.2)产生, 步长$\alpha_k$满足标准$Wolfe$非精确线搜索准则(2.2)-(2.3), 则$\lim\limits_{k\rightarrow\infty}\inf\|g_k\|=0$, 即算法MJJ是全局收敛的.

  由反证法. 若定理3.2不成立, 不妨假设存在常数$\varepsilon>0$, 使得$\|g_k\|^2\geq\varepsilon, $$\ \forall\ k\geq0$. 将式(1.2)两端取平方, 得

$\begin{eqnarray}\label{3.1}\|d_k\|^2=\|g_k\|^2-2\beta_k^{MJJ}g_k^Td_{k-1}+(\beta_k^{MJJ})^2\|d_{k-1}\|^2.\end{eqnarray} $ (3.1)

由式(2.1)可得

$ -2\beta_k^{MJJ}g_k^Td_{k-1}\leq2\mid\beta_k^{MJJ}\mid\mid g_k^Td_{k-1}\mid\leq\frac{2\|g_k\|^2}{u\max\{|g_k^Td_{k-1}|, |g_k^Tg_{k-1}|\}}\mid g_k^Td_{k-1}\mid\leq\frac{2\|g_k\|^2}{u}. $

于是, 将上式代入(3.1), 并利用引理2.1, 有

$ \begin{eqnarray}\label{3.2}{\displaystyle\|d_k\|^2\leq\|g_k\|^2+\frac{2\|g_k\|^2}{u}+(\beta_k^{FR})^2\|d_{k-1}\|^2=\|g_k\|^2(1+\frac{2}{u})+\frac{\|g_k\|^4}{\|g_{k-1}\|^4}\|d_{k-1}\|^2.}\end{eqnarray} $ (3.2)

将式(3.2)两端同除以$\|g_k\|^4$, 得

$ \begin{eqnarray}\label{3.3}\frac{\|d_k\|^2}{\|g_k\|^4}\leq\frac{1}{\|g_k\|^2}(1+\frac{2}{u})+\frac{\|d_{k-1}\|^2}{\|g_{k-1}\|^4}.\end{eqnarray} $ (3.3)

注意到式(1.2)及$\|d_1\|^2=-g_1^Td_1=\|g_1\|^2$, 由(3.3)立得

$ \frac{\|d_k\|^2}{\|g_k\|^4}\leq(1+\frac{2}{u})\sum\limits_{i=1}^k\frac{1}{\|g_i\|^2}. $

又由$\|g_k\|^2\geq\varepsilon$, 有$\frac{\|g_k\|^4}{\|d_k\|^2}\geq\frac{\varepsilon}{k}\frac{u}{u+2}.$ 进而, 立得$\sum\limits_{k=1}^\infty\frac{\|g_k\|^4}{\|d_k\|^2}=+\infty$, 这与引理3.1矛盾. 故定理获证.

4 数值试验

为检验本文所提出的算法实际数值效果, 数值试验共测试了43个问题, 所有算例均取自于无约束优化测试问题集[15], 并与文[9]中的JMJ方法, 文[10]中的NJJ方法, 文[2]中的FR方法及文[6]中的PRP+方法进行比较. 所有测试都采用标准Wolfe线搜索准则(2.2)和(2.3)获得步长. 测试的环境为MATLAB R2017b, Windows 10操作系统, 计算机硬件为Inter(R) Core(TM) i5-8250U CPU 1.80 GHz和8 GB RAM. 相关参数选取如下: $\delta=0.01, \sigma=0.1, u=2.5$. 算法的终止准则为以下两种情形之一: (1) $\|g_k\| < 10^{-5};$ (2) 迭代次数Itr$>2000$. 终止准则(2)出现时认为该方法对这个数值例子失效, 并记为"F".

在试验中, 对所测试算法的迭代次数(Itr), 目标函数函数值计算次数(NF), 梯度计算次数(NG), 计算时间(Tcpu)(单位为秒)及算法终止时目标函数梯度的2-范数($\|g_*\|$)等5个重要指标进行观测和比较, 数值结果详见表 1. 为进一步直观刻划试验效果, 我们还采用Dolan和Mor$\acute{e}$[16]性能图对试验效果进行比对. 图 1-4分别就算法MJJ、算法JMJ、算法NJJ、算法FR及算法PRP+在迭代次数、函数值计算次数、梯度计算次数及计算时间进行比较. 从图 1-4可以更直观地看出, 算法MJJ在所考查的4个指标中均明显优于其他4个算法. 因此, 算法MJJ不仅在解决问题的个数上占据优势, 并且鲁棒性最优. 综上所述, 本文所提出的算法是有效的.

表 1 数值试验报告

图 1 迭代次数比较

图 2 函数值计算次数比较

图 3 梯度计算次数比较

图 4 计算时间比较
参考文献
[1] Hestenes M R, Stiefel E. Method of conjugate gradient for solving linear equations[J]. J. Res. Natl. Bur. Stand., 1952, 49: 409–436. DOI:10.6028/jres.049.044
[2] Fletcher R, Reeves C. Function minimization by conjugate gradients[J]. Comput. J., 1964, 7(2): 149–154. DOI:10.1093/comjnl/7.2.149
[3] Polak E, Ribière G. Note surla convergence de directions conjugèes[J]. Rev. Fr. Inform. Rech. Oper., 1969, 16(3): 35–43.
[4] Polak B T. The conjugate gradient method in extreme problems[J]. USSR Comput. Math. Math. Phys., 1969, 9(4): 94–112. DOI:10.1016/0041-5553(69)90035-4
[5] Dai Y H, Yuan Y X. A nonlinear conjugate gradient method with a strong global convergence property[J]. SIAM J. Optim., 1999, 10(1): 177–182. DOI:10.1137/S1052623497318992
[6] Glibert J C, Nocedal J. Global covergence properties of conjugate gradient method for optimization[J]. SIAM J. Optim., 1992, 2(1): 21–42. DOI:10.1137/0802003
[7] Hager W W, Zhang H C. A new conjugate gradient method with guaranteed descent and an efficient line search[J]. SIAM J. Optim., 2005, 16(1): 170–192. DOI:10.1137/030601880
[8] Andrei N. Hybrid conjugate gradient algorithm for unconstrained optimization[J]. J. Optim. Theory Appl., 2009, 141(2): 249–264. DOI:10.1007/s10957-008-9505-0
[9] 江羡珍, 马国栋, 简金宝. Wolfe线搜索下一个新的全局收敛共轭梯度法[J]. 工程数学学报, 2011, 28(6): 779–786. DOI:10.3969/j.issn.1005-3085.2011.06.009
[10] Jiang X Z, Jian J B. Two modified conjugate gradient methods with disturbance factors for unconstrained optimization[J]. Nonlinear Dynam., 2014, 77(1-2): 387–397. DOI:10.1007/s11071-014-1303-7
[11] 马国栋, 简金宝, 江羡珍. 一个具有下降性的改进Fletcher-Reeves共轭梯度法[J]. 应用数学学报, 2015, 38(1): 89–97.
[12] 景书杰, 王慧婷, 牛海峰, 陈耀. 精确线搜索下一种新的混合共轭梯度法[J]. 数学杂志, 2018, 38(3): 520–524. DOI:10.3969/j.issn.0255-7797.2018.03.016
[13] Jiang X Z, Jian J B. Improved Fletcher-Reeves and Dai-Yuan conjugate gradient methods with the strong Wolfe line search[J]. J. Comput. Appl. Math., 2019, 348: 525–534. DOI:10.1016/j.cam.2018.09.012
[14] 李春梅, 王翠方, 段雪峰. 求解一类矩阵迹极小化问题的非线性共轭梯度法[J]. 数学杂志, 2020, 40(3): 323–331. DOI:10.3969/j.issn.0255-7797.2020.03.008
[15] Morè J J, Garbow B S, Hillstrome K E. Testing unconstrained optimization software[J]. ACM T. Math. Softwar., 1981, 7(1): 17–41. DOI:10.1145/355934.355936
[16] Dolan E D, Moè J J. Benchmarking optimization software with performance profiles[J]. Math. Program, 2002, 91(2): 201–213. DOI:10.1007/s101070100263