高级搜索

留言板

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

求解无约束问题的修正PRP共轭梯度算法

, 

上一篇

下一篇

李春念, 袁功林. 求解无约束问题的修正PRP共轭梯度算法[J]. 西南大学学报（自然科学版）, 2018, 40(9): 67-75. doi: 10.13718/j.cnki.xdzk.2018.09.011
引用本文: 李春念, 袁功林. 求解无约束问题的修正PRP共轭梯度算法[J]. 西南大学学报（自然科学版）, 2018, 40(9): 67-75. doi: 10.13718/j.cnki.xdzk.2018.09.011
shu
Chun-nian LI, Gong-lin YUAN. A Modified Polak-Ribière-Polyak Conjugate Gradient Algorithm for Smooth Convex Programs[J]. Journal of Southwest University Natural Science Edition, 2018, 40(9): 67-75. doi: 10.13718/j.cnki.xdzk.2018.09.011
Citation: Chun-nian LI, Gong-lin YUAN. A Modified Polak-Ribière-Polyak Conjugate Gradient Algorithm for Smooth Convex Programs[J]. Journal of Southwest University Natural Science Edition, 2018, 40(9): 67-75. doi: 10.13718/j.cnki.xdzk.2018.09.011
shu

求解无约束问题的修正PRP共轭梯度算法

  • 广西大学 数学与信息学院, 南宁 530004

  • 基金项目: 国家自然科学基金项目（11261006）；广西杰出青年科学基金项目（2015GXNSFGA139001）
详细信息
    作者简介:

    李春念(1992-), 女, 硕士研究生, 主要从事最优化理论方法及其应用的研究 .

    通讯作者: 袁功林, 教授, 博士研究生导师

  • 中图分类号: O224

A Modified Polak-Ribière-Polyak Conjugate Gradient Algorithm for Smooth Convex Programs

  • College of Mathematics and Information Science, Guangxi University, Nanning 530004, China

  • 摘要: 提出了一种改进的PRP共轭梯度算法，其搜索方向自动具有充分下降性和信赖域性质，且在一定条件下，具有全局收敛性.数值结果表明该算法对求解无约束光滑问题是有效的.
    Abstract: In this paper, a modified PRP conjugate gradient algorithm is proposed. The search direction of this algorithm belongs to a trust region automatically, and its search direction possesses descent property. Under suitable conditions, the method owns global convergence. Some elementary numerical experiments indicate that the presented method is effective for unconstrained smooth problems.
  • 加载中

  • 图 1  算法MPRP与算法PRP的性能图(Totle2)

    下载: 全尺寸图片 幻灯片

    表 1  数值结果

    算法 MPRP PRP
    n/维 I/次 T/次 n/维 I/次 T/次
    Extended Freudenstein & Roth Function 6 000 21 57 6 000 45 128
    15 000 21 61 15 000 271 773
    Extended Trigonometric Function 6 000 81 176 6 000 60 134
    15 000 85 186 15 000 63 142
    Extended Rosenbrock Function 6 000 106 353 6 000 46 125
    15 000 77 231 15 000 1 000 2 841
    Extended White & Holst function 6 000 64 197 6 000 501 1 427
    15 000 70 236 15 000 389 1 115
    Extended Beale FunctIonU63(MatrixRom) 6 000 26 71 6 000 457 1 293
    15 000 25 71 15 000 507 1 435
    Extended Penalty Function 6 000 114 250 6 000 82 187
    15 000 128 280 15 000 92 209
    Perturbed Quadratic function 6 000 1 000 2 002 6 000 1 000 2 808
    15 000 1 000 2 002 15 000 1 000 2 811
    Raydan 1 Function 6 000 23 51 6 000 20 49
    15 000 23 51 15 000 20 49
    Raydan 2 Function 6 000 12 26 6 000 6 14
    15 000 12 26 15 000 6 14
    Diagonal 1 Function 6 000 2 13 6 000 2 13
    15 000 2 13 15 000 2 13
    Diagonal 2 Function 6 000 66 153 6 000 62 216
    15 000 14 50 15 000 21 86
    Diagonal 3 Function 6 000 17 36 6 000 20 46
    15 000 17 36 15 000 20 46
    Hager Function 6 000 19 46 6 000 14 33
    15 000 2 13 15 000 2 13
    Generalize-d Tridiagonal-1 Functi-on 6 000 6 15 6 000 5 13
    15 000 5 15 15 000 5 13
    Extended Tridiagonal-1 Function 6 000 40 104 6 000 1 000 2 830
    15 000 46 127 15 000 1 000 2 827
    Extended Three Exponential Terms 6 000 21 44 6 000 35 73
    15 000 24 50 15 000 20 42
    Generalize-d Tridiago-nal-2 6 000 50 104 6 000 39 114
    15 000 49 102 15 000 31 84
    Diagonal 4 Function 6 000 5 17 6 000 363 1 023
    15 000 5 17 15 000 383 1081
    Diagonal 5 Function (MatrixRom) 6 000 3 9 6 000 3 10
    15 000 3 9 15 000 3 10
    Extended Himmelbla-u Function 6 000 20 61 6 000 55 114
    15 000 26 67 15 000 62 128
    Generalize-d PSC1 Function 6 000 32 73 6 000 24 57
    15 000 34 77 15 000 24 57
    Extended PSC1 Function 6 000 10 75 6 000 7 51
    15 000 10 75 15 000 7 51
    Extended Powell 6 000 144 440 6 000 1 000 2 826
    15 000 409 1 376 15 000 1 000 2 818
    Extended Block Diagonal BD1 Function 6 000 70 232 6 000 8 85
    15 000 53 152 15 000 34 148
    Extended Maratos Function 6 000 38 76 6 000 32 64
    15 000 19 40 15 000 49 100
    Extended Cliff 6 000 106 230 6 000 83 184
    15 000 89 198 15 000 72 165
    Quadratic Diagonal Perturbed Function 6 000 47 156 6 000 1 000 2 820
    15 000 63 215 15 000 1 000 2 827
    Extended Wood Function 6 000 45 109 6 000 43 119
    15 000 44 109 15 000 46 127
    Extended Hiebert Function 6 000 29 92 6 000 1 000 483
    15 000 29 92 15 000 1 000 2 829
    Quadratic Function QF1 6 000 1 000 2 002 6 000 1 000 2 823
    15 000 1 000 2 002 15 000 1 000 2 820
    Extended Quadratic Penalty QP1 Function 6 000 41 90 6 000 29 66
    15 000 42 92 15 000 31 70
    Extended Quadratic Penalty QP2 Function 6 000 71 146 6 000 54 112
    15 000 39 84 15 000 26 61
    A Quadratic Function QF2 6 000 3 7 6 000 3 7
    15 000 2 5 15 000 2 5
    Extended EP1 Function 6 000 5 10 6 000 5 11
    15 000 7 14 15 000 5 10
    Extended Tridiagonal-2 Function 6 000 16 32 6 000 12 24
    15 000 23 46 15 000 20 40
    BDQRTIC (CUTE) 6 000 17 64 6 000 723 2 073
    15 000 38 108 15 000 953 2 742
    TRIDIA (CUTE) 6 000 1 000 2015 6 000 1 000 2 853
    15 000 1 000 2 003 15 000 1 000 2 869
    ARWHEAD (CUTE) 6 000 16 40 6 000 727 2 055
    15 000 11 29 15 000 668 1 883
    NONDIA (Shanno-78) (CUTE) 6 000 27 54 6 000 7 15
    15 000 29 58 15 000 8 17
    NONDQUAR (CUTE) 6 000 1 000 2157 6 000 1 000 2 858
    15 000 1 000 2 221 15 000 1 000 2 924
    DQDRTIC (CUTE) 6 000 43 106 6 000 521 1 475
    15 000 34 82 15 000 291 821
    EG2 (CUTE) 6 000 4 33 6 000 12 55
    15 000 4 33 15 000 7 31
    DIXMAANA (CUTE) 6 000 23 50 6 000 16 36
    15 000 24 52 15 000 17 38
    DIXMAANB (CUTE) 6 000 39 82 6 000 21 46
    15 000 41 86 15 000 22 48
    DIXMAANC (CUTE) 6 000 69 142 6 000 55 114
    15 000 72 148 15 000 58 120
    DIXMAANE (CUTE) 6 000 249 509 6 000 176 510
    15 000 781 1573 15 000 298 874
    Partial Perturbed Quadratic 6 000 80 178 6 000 77 209
    15 000 93 217 15 000 286 789
    Broyden Tridiagonal 6 000 38 92 6 000 43 111
    15 000 56 115 15 000 32 91
    Almost Perturbed Quadratic 6 000 1 000 2 002 6 000 1 000 2 826
    15 000 1 000 2 002 15 000 1 000 2813
    Tridiagonal Perturbed Quadratic 6 000 1 000 2 002 6 000 1 000 2 837
    15 000 1 000 2 002 15 000 1 000 2811
    EDENSCH Function (CUTE) 6 000 23 48 6 000 14 30
    15 000 23 48 15 000 14 30
    VARDIM Function (CUTE) 6 000 171 374 6 000 123 278
    15 000 187 408 15 000 135 304
    STAIRCASE S1 6 000 1 000 2009 6 000 1 000 2 837
    15 000 1 000 2044 15 000 1 000 2 824
    LIARWHD (CUTE) 6 000 59 173 6 000 251 713
    15 000 46 120 15 000 1 000 2 819
    DIAGONAL 6 6 000 22 46 6 000 8 19
    15 000 23 48 15 000 8 19
    DIXON3DQ (CUTE) 6 000 1 000 2 003 6 000 1 000 2 868
    15 000 1 000 2 003 15 000 1 000 2 871
    DIXMAANF (CUTE) 6 000 72 150 6 000 58 162
    15 000 81 168 15 000 84 239
    DIXMAANG (CUTE) 6 000 142 297 6 000 189 542
    15 000 129 275 15 000 240 697
    DIXMAANH (CUTE) 6 000 78 165 6 000 61 166
    15 000 87 183 15 000 70 197
    DIXMAANI (CUTE) 6 000 331 683 6 000 188 550
    15 000 551 1 113 15 000 171 494
    DIXMAANJ (CUTE) 6 000 71 148 6 000 64 182
    15 000 81 168 15 000 72 204
    DIXMAANK (CUTE) 6 000 108 228 6 000 150 432
    15 000 120 252 15 000 166 473
    DIXMAANL (CUTE) 6 000 1 000 2006 6 000 287 832
    15 000 1 000 2006 15 000 529 1 476
    DIXMAAND (CUTE) 6 000 27 60 6 000 28 63
    15 000 27 60 15 000 29 65
    ENGVAL1 (CUTE) 6 000 41 86 6 000 39 82
    15 000 41 86 15 000 39 80
    FLETCHCR (CUTE) 6 000 1 000 2 022 6 000 3 265
    15 000 1 000 2 022 15 000 5 7
    COSINE (CUTE) 6 000 22 157 6 000 5 35
    15 000 23 118 15 000 5 43
    Extended DENSCHNB (CUTE) 6 000 36 74 6 000 18 38
    15 000 38 78 15 000 19 40
    Extended DENSCHNF (CUTE) 6 000 38 81 6 000 63 131
    15 000 39 83 15 000 65 135
    SINQUAD (CUTE) 6 000 34 119 6 000 119 332
    15 000 41 133 15 000 663 1 859
    BIGGSB1 (CUTE) 6 000 1 000 2001 6 000 1 000 2 844
    15 000 1 000 2 001 15 000 1 000 2 840
    Partial Perturbed Quadratic PPQ2 6 000 610 1 972 6 000 1 000 2 812
    15 000 657 2 076 15 000 1 000 2 828
    Scaled Quadratic SQ1 6 000 1 000 2 002 6 000 1 000 2 828
    15 000 1 000 2 002 15 000 1 000 2 813
    Scaled Quadratic SQ2 6 000 1 000 2 002 6 000 1 000 2 798
    15 000 1 000 2 002 15 000 1 000 2 797
    下载: 导出CSV
  • [1] doi: http://www.ams.org/mathscinet-getitem?mr=255025 POLAK E, RIBIERE G. Note Sur La Convergence de Methode de Directions Conjuguees[J]. Revue Francaise Information Recherche Operationnelle, 2009, 16(16):35-43.
    [2] POLYAK B T. The Conjugate Gradient Method in Extremal Problems[J]. Ussr Computational Mathematics and Mathematical Physics, 1969, 9(4):94-112. doi: 10.1016/0041-5553(69)90035-4
    [3] ZHANG L, ZHOU W J, LI D H. A Descent Modified Polak-Ribière-Polyak Conjugate Gradient Method and Its Global Convergence[J]. Ima Journal of Numerical Analysis, 2006, 26(4):629-640. doi: 10.1093/imanum/drl016
    [4] WEI Z, YAO S, LIU L. 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
    [5] FLETCHER R, REEVES C M. Function Minimization by Conjugate Gradients[J]. Computer Journal, 1964, 7(2):149-154. doi: 10.1093/comjnl/7.2.149
    [6] HAGER W W, ZHANG H. A New Conjugate Gradient Method with Guaranteed Descent and an Efficient Line Search[J]. Siam Journal on Optimization, 2005, 16(1):170-192. doi: 10.1137/030601880
    [7] HAGER W W, ZHANG H. Algorithm 851:CG_DESCENT, A Conjugate Gradient Method with Guaranteed Descent[J]. ACM Transactions on Mathematical Software, 2006, 32(1):113-137. doi: 10.1145/1132973
    [8] HESTENES M R, STIEFEL E. Method of Conjugate Gradient for Solving Linear Equations[J]. Res Nation Bur Stand, 1952, 49(6):409-436. doi: 10.6028/jres.049.044
    [9] CARDENAS S. Efficient Generalized Conjugate Gradient Algorithms I Theory.[J]. Journal of Optimization Theory and Applications, 1991, 69(1):129-137. doi: 10.1007/BF00940464
    [10] doi: http://d.old.wanfangdata.com.cn/Periodical/xnnydxxb201707015 YUAN G, LU X. A Modified PRP Conjugate Gradient Method[J]. Annals of Operations Research, 2009, 166(1):73-90.
    [11] YUAN G L, LU X W, WEI Z X. A Conjugate Gradient Method with Descent Direction for Unconstrained Optimization[J]. Journal of Computational and Applied Mathematics, 2009, 233(2):519-530. doi: 10.1016/j.cam.2009.08.001
    [12] YUAN G L, MENG Z H, LI Y. A Modified Hestenes and Stiefel Conjugate Gradient Algorithm for Large-Scale Nonsmooth Minimizations and Nonlinear Equations[J]. Journal of Optimization Theory and Applications, 2016, 168(1):129-152. doi: 10.1007/s10957-015-0781-1
    [13] doi: http://www.sciencedirect.com/science/article/pii/S0307904X1730104X YUAN G L, WEI Z X, LU X W. Global Convergence of BFGS and PRP Methods Under a Modified Weak Wolfe-Powell Lline Search[J]. Applied Mathematical Modelling, 2017(47):811-825.
    [14] doi: https://core.ac.uk/display/102945182 ANDREI N. An Unconstrained Optimization Test Functions Collection[J]. Advanced Modeling and Optimization, 2008, 10(1):147-161.
    [15] YUAN G L, WEI Z X, LU X W. A BFGS Trust-Region Method for Nonlinear Equations[J]. Computing, 2011, 92(4):317-333. doi: 10.1007/s00607-011-0146-z
  • 加载中
图( 1) 表( 1)
计量
  • 文章访问数:  1546
  • HTML全文浏览数:  1292
  • PDF下载数:  108
  • 施引文献:  0
出版历程
  • 收稿日期:  2017-05-17
  • 刊出日期:  2018-09-20

求解无约束问题的修正PRP共轭梯度算法

    通讯作者: 袁功林, 教授, 博士研究生导师
    作者简介: 李春念(1992-), 女, 硕士研究生, 主要从事最优化理论方法及其应用的研究
  • 广西大学 数学与信息学院, 南宁 530004
  • 收稿日期:  2017-05-17
基金项目:  国家自然科学基金项目（11261006）；广西杰出青年科学基金项目（2015GXNSFGA139001）

摘要: 提出了一种改进的PRP共轭梯度算法，其搜索方向自动具有充分下降性和信赖域性质，且在一定条件下，具有全局收敛性.数值结果表明该算法对求解无约束光滑问题是有效的.

English Abstract

    全文HTML

  • 考虑下列无约束问题：

    其中$\mathit{\boldsymbol{f}}:{\mathbb{R}^n} \to \mathbb{R}$二次连续可导.求解此类问题的方法有很多，共轭梯度法就是其中一类. PRP方法是共轭梯度法中最有效的方法之一[1-2]，其公式为

    其中

    此方法数值表现很出色，但理论结果不是很理想.

    有学者认为该方法收敛性不好的原因在于βkPRP＜0可能发生，另一个原因在于不具有充分下降性.对此Zhang[3]提出了一种3项共轭梯度公式：

    该算法弥补了原算法自动下降性上的不足，但它不具备信赖域性质. Wei等[4]提出了一个新的公式：

    其中

    容易得到

    可见βkWYL≥0，解决了βkPRP可能小于0的问题，并且在收敛性和数值结果方面都有一定的提升.基于以上方法，很多学者对此作了相应的研究[5-12].本文在已有研究基础上给出了一个新的搜索方向，此搜索方向自动具有充分下降性和信赖域特征.

1.   动机和算法

  • 本文给出如下改进的搜索方向：

    此搜索方向不仅具有充分下降性，而且还有信赖域特征.

    本文的算法步骤如下：

    算法1(改进的PRP算法)

    Step 0：给定${\mathit{\boldsymbol{x}}_0} \in {\mathbb{R}^n}$，ε∈(0，1)，$\delta \in \left( {0, \frac{1}{2}} \right)$，δ1∈(0，δ)，σ∈(δ，1)，c1，c2∈(0，1).令d1=-g1= $-\nabla \mathit{\boldsymbol{f}}\left( {{\mathit{\boldsymbol{x}}_1}} \right)$，k：=1.

    Step 1：如果‖gk‖≤ε，则停止；否则进行Step 2.

    Step 2：通过MWWP线搜索[13]：

    计算步长αk.

    Step 3：令xk+1=xk+αkdk.

    Step 4：若‖gk+1‖≤ε，则停止；否则进行Step 5.

    Step 5：由式(4)计算搜索方向dk+1.

    Step 6：令k：=k+1，返回Step 2.

    注  (5)和(6)式是文献[13]中提出的一种修正的WWP线搜索，该线搜索技术保证了BFGS和PRP对一般函数的全局收敛性，并且在数值结果方面表现良好，所以本文采用此技术.

2.   收敛性分析

  • 引理1  由式(4)的定义搜索方向满足如下性质：

    证

    1) 当k=0时，d0=-g0，性质显然成立.

    2) 当k≥1时，

    故性质(7)成立.以下验证性质(8)，

    综上所述，性质(7)，(8)成立.证毕.

    为了分析算法的全局收敛性，给出如下假设：

    假设1  (A)水平集L0={x|f(x)≤f(x0)}有界.

    (B) 设目标函数f(x)两次连续可微且下方有界，梯度函数g(x)满足Lipschitz连续且系数L＞0，即

    定理1  令{xk，αk，dk，gk}由算法1给出，且假设1成立，有

    证  由MWWP线搜索和假设1(B)可知，

    对不等式两边从k=0到∞求和并结合假设1(B)，可知

    即得

    利用性质(7)得

    通过MWWP线搜索以及式(9)和(7)，可得

    因此

    其中

    将不等式(12)代入到(11)式，得到(10)式，原命题成立.证毕.

3.   数值结果

  • 本节为数值实验的结果分析，算法MPRP中具有固定初始点的测试函数[14]，数值实验中，所有代码均为Matlab语言，测试环境是惠普笔记本电脑，CPU为Inter Pentium(R)Dual-Core E5800 3.2 GHz，操作系统为Window 7.

    算法1中参数设定为δ=0.1，δ1=0.05，σ=0.9，c1=0.3，c2=0.5，实验的终止条件是‖gk‖≤10-5.数值结果见表 1，其中n表示问题的维数，I表示实验中的迭代次数，T表示函数值和梯度值的计算总次数.

    从表 1可以看出，算法MPRP在计算维数相同的条件下，计算出结果所需要的迭代次数较少，且能有效求解.

    为了分析算法的性能，利用文献[15]的技术比较MPRP算法与PRP算法关于函数值和梯度值的计算总次数的性能图(图 1).由图 1可以看出，MPRP具有更好的数值表现.

4.   结语

  • 本文基于文献[13]的思路，运用了一种改进的WWP搜索方向技术求解无约束问题.在一定的条件下，证明了算法MPRP的下降性、全局收敛性等性质，实验结果也表明该算法是可行的.

参考文献 (15)

目录

版权所有：西南大学学报（自然科学版）

地址：重庆市北碚区西南大学 电话：023-68254576, 68252540, 68366165,68366917 电子邮箱：lkxb@swu.edu.cn

本系统由北京仁和汇智信息技术有限公司开发

/

返回文章
返回