留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

一类具有充分下降性的混合型谱共轭梯度法

上一篇

下一篇

王森森, 张俊容, 韩信, 等. 一类具有充分下降性的混合型谱共轭梯度法[J]. 西南大学学报(自然科学版), 2017, 39(5): 139-144. doi: 10.13718/j.cnki.xdzk.2017.05.021
引用本文: 王森森, 张俊容, 韩信, 等. 一类具有充分下降性的混合型谱共轭梯度法[J]. 西南大学学报(自然科学版), 2017, 39(5): 139-144. doi: 10.13718/j.cnki.xdzk.2017.05.021
Sen-sen WANG, Jun-rong ZHANG, Xin HAN, et al. A Mixed Spectral Conjugate Gradient Method with Sufficient Descent Property[J]. Journal of Southwest University Natural Science Edition, 2017, 39(5): 139-144. doi: 10.13718/j.cnki.xdzk.2017.05.021
Citation: Sen-sen WANG, Jun-rong ZHANG, Xin HAN, et al. A Mixed Spectral Conjugate Gradient Method with Sufficient Descent Property[J]. Journal of Southwest University Natural Science Edition, 2017, 39(5): 139-144. doi: 10.13718/j.cnki.xdzk.2017.05.021

一类具有充分下降性的混合型谱共轭梯度法

  • 基金项目: 国家自然科学基金项目(11401487)
详细信息
    作者简介:

    王森森(1990-),男,河南辉县人,硕士研究生,主要从事最优化理论、算法及应用研究 .

    通讯作者: 张俊容,博士,副教授; 
  • 中图分类号: O224

A Mixed Spectral Conjugate Gradient Method with Sufficient Descent Property

  • 摘要: 首先基于共轭梯度法的下降性条件,提出了一类结合了FR法、WYL法、PRP法优点的充分下降的混合型谱共轭梯度法.在Wolfe线搜索下用反证法证明了新的混合型谱共轭梯度法的全局收敛性.最后通过数值算例,将本文算法与WYL法、FR法进行比较,结果表明新算法在迭代次数与迭代总时间上均优于其他另外两种算法.算法的全局收敛性和数值效果的优越性表明新算法是有效的.
  • 加载中
  • 图 1  c-t

    表 1  数值结果

    函数名称 算法 维数/维 迭代次数/次 迭代时间/s gk 每迭代一次的平均时间/s i
    Example1 1 60 19 314 3.16×10-5 16.5 0
    WYL 60 34 1190 5.89×10-5 35 0
    FR 60 110 3123 8.57×10-5 28.4 0
    Example2 1 100 78 387 9.31×10-5 4.96 0
    WYL 100 179 2866 7.83×10-5 16 0
    FR 100 19 1898 4.81×1030 99.9 1
    POWER 1 50 426 1752 8.82×10-5 4.11 0
    WYL 50 279 3601 3.45×10-1 12.9 1
    FR 50 434 3605 9.35×10-1 8.31 1
    Diagonal 4 1 200 69 610 5.51×10-5 8.84 0
    WYL 200 45 2127 1.44×101 47.3 1
    FR 200 69 1488 7.3×10-5 21.6 0
    Extended Penalty 1 20 28 474 8.5×10-5 16.9 0
    WYL 20 28 679 5.27×10-5 24.3 0
    FR 20 36 609 6.45×10-5 16.9 0
    Extended Rosenbrock 1 10 144 217 9.39×10-5 1.51 0
    WYL 10 644 3606 1.37×10-1 5.6 1
    FR 10 151 861 6.72×101 5.7 1
    Extended White Holst 1 100 42 1535 2.97×10-5 36.6 0
    WYL 100 57 3699 0.36×101 64.9 1
    FR 100 51 3685 2.27×10-2 52.6 1
    Perturbed Quadrtic 1 20 31 283 6.35×10-5 9.11 0
    WYL 20 41 874 2.06×10-3 21.3 1
    FR 20 41 441 1.87×10-2 21.3 1
    ENGVAL 1 1 50 91 1182 9.43×10-5 13 0
    WYL 50 35 2137 3.02×10-5 61 0
    FR 50 83 2682 7.61×10-5 32.3 0
    下载: 导出CSV
  • [1] WEI Z X, YAO S W, LIU Y X. The Convergence Properties of Some New Conjugate Gradient Methods [J]. Applied Mathematics and Computation, 2006, 183(2): 1341-1350. doi: 10.1016/j.amc.2006.05.150
    [2] HUANG H, WEI Z X, YAO S W. The Proof of the Sufficient Descent Condtion of Wei-Yao-Liu Conjugate Gradient Method under the Strong Wolfe-Powell Line Search [J]. Applied Mathematics and Computation, 2007, 189(2): 1241-1245. doi: 10.1016/j.amc.2006.12.006
    [3] BIRGIN E G, MARTINEZ J M. A Spectral Conjugate Gradient Method for Unconstraiend Optimization [J]. Applied Mathematics and Optimization, 2001, 43(2): 117-128. doi: 10.1007/s00245-001-0003-0
    [4] ZHANG L, ZHOU W J, Li D H. Global Convergence of a Modified Fletcher-Reeves Conjugate Gradient Method with Armijo-Type Line Search [J]. Numerical Mathematics, 2006, 104(4): 561-572. doi: 10.1007/s00211-006-0028-z
    [5] 王开荣, 曹伟, 王银河. Armijo型线搜素下的谱CD共轭梯度法[J].山东大学学报(理学版), 2011, 45(11): 104-108. doi: http://www.cnki.com.cn/Article/CJFDTOTAL-SDDX201011023.htm
    [6] doi: https://www.researchgate.net/publication/268017897_Global_convergence_of_a_modified_spectral_CD_conjugate_gradient_method CAO W, WANG K R, WANG Y H. Global Convergence of a Modified Spectral CD Conjugate Gradient Method [J]. Journal of Mathematical Research and Exposition, 2011, 31(2): 261-268.
    [7] DU X L, LIU J K. Global Convergence of a Spectral HS Conjugate Gradient Method [J]. Procedia Engineering, 2011, 15; 1487-1492. doi: 10.1016/j.proeng.2011.08.276
    [8] WAN Z, YANG Z L, WANG Y L. New Spectral PRP Conjugdte Gradient Method for Unconstrained Optimization [J]. Applied Mathematics Letters, 2011, 24(1): 16-22. doi: 10.1016/j.aml.2010.08.002
    [9] 黄海, 林穗华.一个PRP型共轭梯度法的收敛性[J].西南大学学报(自然科学版), 2012, 34(3): 22-29. doi: http://xbgjxt.swu.edu.cn/jsuns/jsuns/ch/reader/view_abstract.aspx?file_no=z20120306&flag=1
    [10] 戴彧虹, 袁亚湘.非线性共轭梯度法[M].上海:上海科学出版社, 2000: 10-13.
    [11] doi: https://www.researchgate.net/publication/228737339_An_unconstrained_optimization_test_functions_collection ANDREI N. An Uconstrained Optimization Test Fuctions Collection [J]. Advanced Modelling and Optimzation, 2008, 10(1): 147-161.
  • 加载中
图( 1) 表( 1)
计量
  • 文章访问数:  664
  • HTML全文浏览数:  175
  • PDF下载数:  42
  • 施引文献:  0
出版历程
  • 收稿日期:  2015-10-29
  • 刊出日期:  2017-05-20

一类具有充分下降性的混合型谱共轭梯度法

    通讯作者: 张俊容,博士,副教授; 
    作者简介: 王森森(1990-),男,河南辉县人,硕士研究生,主要从事最优化理论、算法及应用研究
  • 西南大学 数学与统计学院,重庆 400715
基金项目:  国家自然科学基金项目(11401487)

摘要: 首先基于共轭梯度法的下降性条件,提出了一类结合了FR法、WYL法、PRP法优点的充分下降的混合型谱共轭梯度法.在Wolfe线搜索下用反证法证明了新的混合型谱共轭梯度法的全局收敛性.最后通过数值算例,将本文算法与WYL法、FR法进行比较,结果表明新算法在迭代次数与迭代总时间上均优于其他另外两种算法.算法的全局收敛性和数值效果的优越性表明新算法是有效的.

English Abstract

  • 考虑如下的无约束优化问题

    其中f(x)是连续可微函数,其梯度向量$\nabla $f(x)记为g(x).共轭梯度法是求解上述无约束优化问题的一种十分有效的算法.经典共轭梯度法的基本迭代格式为:

    其中:dk为搜索方向;αk为步长因子,通常可以由Wolfe非精确的一维线搜索来确定.

    δσ为满足0<δσ<1的常数;βk为标量参数.关于βk的选择有许多著名的公式,如:

    其中yk-1=gk-gk-1.上述4个公式分别对应4种不同的共轭梯度方法.每种方法又有很多变形,例如Wei等[1]给出了PRP的一个变形,参数βk取值为:

    WYL法继承了PRP法的一些优良性质,例如良好的数值表现,并且Huang等[2]证明了此方法在强Wolfe线搜索下具有全局收敛性和下降性.

    2001年Birgin和Martinez[3]提出了一种谱共轭梯度法,其搜索方向定义如下:

    其中${\theta _k} = \frac{{{\boldsymbol{s}_{k-1}}^{\text{T}}{\boldsymbol{s}_{k-1}}}}{{{\boldsymbol{s}_{k-1}}^{\text{T}}{\boldsymbol{y}_{k - 1}}}} $为谱系数,$ {\beta _k} = \frac{{{{\left( {{\theta _k}{\boldsymbol{y}_{k-1}}-{\boldsymbol{s}_{k-1}}} \right)}^{\text{T}}}{\boldsymbol{y}_{k - 1}}}}{{{\boldsymbol{d}_{k - 1}}^{\text{T}}{\boldsymbol{y}_{k - 1}}}}$sk-1=xk-xk-1=αk-1dk-1.但是Birgin和Martinez提出的谱共轭梯度法的搜索方向dk不满足下降性,当然也不具有全局收敛性.为了获得全局收敛性,Zhang等[4]在此基础上构造出了FR型谱共轭梯度法,其搜索方向dk${\theta _k} = \frac{{{\boldsymbol{d}_{k-1}}^{\text{T}}{\boldsymbol{y}_{k-1}}}}{{{{\left\| {{\boldsymbol{g}_{k-1}}} \right\|}^2}}} $βk=βkFR.此方法的一个重要特点是满足充分下降条件

    其中t>0为常数.此后Wang,Cao等[5-6]提出了CD型谱共轭梯度法;Du和Liu提出了HS型谱共轭梯度法[7];Wan,Huang等[8-9]提出了PRP型的谱共轭梯度法.上述方法都满足充分下降条件(8).

    本文在上述文献的基础上,提出了一类具有充分下降性的混合型谱共轭梯度法,参数βk为:

    谱系数${\theta _k} = c + \beta _k^{{\text{WS}}}\frac{{\boldsymbol{g}_k^{\text{T}}{\boldsymbol{d}_{k-1}}}}{{{{\left\| {{\boldsymbol{g}_k}} \right\|}^2}}} $c为大于0的参数,然后基于(9) 式给出混合型谱共轭梯度法的算法,证明了算法的收敛性,并进行了数值实验.

  • 本节中,首先给出混合型谱共轭梯度法(算法1),然后说明它所具有的一些性质.

    算法1 混合型谱共轭梯度法.

    步骤1 给定初始点x1及精度ε,计算g1,若‖g1‖≤ε,停止.否则,转步骤2.

    步骤2 计算搜索方向dk

    步骤3 由(4) 式计算步长因子αk.

    步骤4 迭代计算xk+1=xk+αkdkgk+1=g(xk+1).若‖gk+1‖≤ε,则停止.

    步骤5 k:=k+1,转步骤2.

    命题1 由算法1产生的序列{gk}和{dk}满足下降性,即对任意k≥1,都有gkTdk<0.

     由算法1得

    命题2 对任意k≥1,参数βkWS满足$ 0 \leqslant \beta _k^{{\text{WS}}} \leqslant \frac{{{{\left\| {{\boldsymbol{g}_k}} \right\|}^2}}}{{{{\left\| {{\boldsymbol{g}_{k-1}}} \right\|}^2}}}$.

     由参数βkWS的定义可知命题成立.

    分析(9) 式有:参数βkWS为FR,WYL,PRP 3者的混合.下面分3种情况对此说明:

    1) 当gkTgk-1≤0时,

    2) 当gkTgk-1>0且$\frac{{\left\| {{\boldsymbol{g}_k}} \right\|}}{{\left\| {{\boldsymbol{g}_{k-1}}} \right\|}} \leqslant 1$时,

    3) 当gkTgk-1>0且$\frac{{\left\| {{\boldsymbol{g}_k}} \right\|}}{{\left\| {{\boldsymbol{g}_{k-1}}} \right\|}} > 1 $时,

    此外由算法1的谱系数的选取可知,可通过选取不同的参数c来优化算法1的数值效果.

  • 为了研究算法的收敛性,下面给出一些基本假设:

    (A1) 设f(x)的水平集$\mathit{\Omega } = \left\{ {\boldsymbol{x} \in {\mathbb{R}^n}|f\left( \boldsymbol{x} \right) \leqslant f\left( {{\boldsymbol{x}_1}} \right)} \right\} $有界,其中x1为初始迭代点.

    (A2) 存在Ω的某个邻域Λ,使得f(x)在该邻域上连续可微且梯度函数g(x)满足Lipschitz条件,即存在常数L>0,使得

    引理1[10] 假设(A1),(A2) 成立,如果搜索方向dk满足下降性,步长αk由Wolfe非精确的一维线搜索确定,那么$\sum {\frac{{{{\left( {\boldsymbol{g}_k^{\text{T}}{\boldsymbol{d}_k}} \right)}^2}}}{{{{\left\| {{\boldsymbol{d}_k}} \right\|}^2}}}} < \infty $.

    定理1 如果条件(A1),(A2) 成立,算法1产生的序列{gk}有

     假设结论不成立,则存在常数γ>0使得

    由(10) 式可得

    从而有

    将(19) 式展开得

    移项可得

    由命题1的证明,(21) 式可变为

    (22) 式两边同时除以(gkTdk)2

    进而有

    综上所述可得

    与引理1矛盾.

  • 下面对算法1进行数值实验,测试函数中Example 1与Example 2的表达式为:

    其它测试对象均来自文献[11]中的函数.实验在PC机上完成,PC的配置如下:AMD A4-3300M CPU 1.90 GHz,2.00 GB内存.程序用Matlab编写,运行环境为Matlab R2010a.算法中参数的选取为:δ=0.001,σ=0.9.终止条件为:‖gk‖≤10-4;或者算法的迭代总时间超过1 800 s;或者超过规定的迭代次数.

    对于算法1中参数c的选取,以二维的香蕉函数为实验对象进行测试,香蕉函数的表达式如下:

    选取不同的c值(0<c<0.1),得到不同的迭代时间t,作出c-t图(图 1).

    图 1可得:当c取0.009时,迭代时间最短,最短时间点坐标为(0.009,29.498 5).另外通过数值实验发现,当c取值大于0且小于106时,算法1仍然有效;但当c取值为0或大于106的时候,算法1无效.所以在本文后面的数值实验中选取c=0.009,将算法1与WYL共轭梯度法及FR共轭梯度法进行比较,实验结果见表 1.

    表 1i的取值0和1分别表示迭代成功与不成功.从表 1可以看出无论是迭代次数、迭代的总时间、还是每次迭代的平均时间,算法1数值效果均优于其它另外两种算法.此外算法1可以调控参数c来优化数值效果,具有一定的灵活性.

参考文献 (11)

目录

/

返回文章
返回