求解无约束优化的一个新的下降共轭梯度法

求解无约束优化问题的共轭梯度法李芳梅，姚瑞哲指导教师：李良摘要：本文主要针对无约束优化问题，利用共轭梯度法（CG方法）求解此类问题，并得出其迭代次数及问题的解。

论文对此种方法给出了具体事例，并对例子进行了matlab软件实现。

1.引言共轭梯度法时介于最速下降法与牛顿法之间的一个方法。

它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点。

共轭梯度法最早是由Hestenes和Stiefel（1952）提出来的，用于解正定系数矩阵的线性方程组。

由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现已广泛应用与实际问题中。

2.共轭梯度法共轭梯度法是共轭方向法的一种。

所谓共轭方向法就是其所有的搜索方向都是相互共轭的方法。

定义设G是n×n对称正定矩阵，d1，d2是n维非零向量。

如果d1T G d2=0，则称向量d1和d2是G-共轭的，简称共轭的。

设d1，d2，…，d m是R n中任一组非零向量，如果d i T G d j=0 （i≠j），则称d1，d2，…，d m是G-共轭的，简称共轭的。

显然，如果d1，d2，…，d m是共轭的，则它们是线性无关的。

算法（共轭梯度法）步1.初始步：给出x0，ε>0,计算r0=G x0-b，令d0=-r0，k:=0. 步2.如果‖r k‖≤ε，停止.步3.计算αk=r k T r k/d k T Gd k,x k+1=x k+αk d k，r k+1=r k+αk Gd k，βk=r k+1T r k+1/r k T r k，d k+1=-r k+1+βk d k.步4.令k:=k+1，转步2.1.共轭梯度法的matlab实现（数值例子）首先建立如下的m.文件function[x,iter]=cgopt(G,b,x0,max_iter,tol)x=x0;fprintf('\n x0=');fprintf('%10.6f',x0);r=G*x-b;%残差d=-r;for k=1:max_iterif norm(r)<=toliter=k-1;fprintf('\n Algorithm finds a solution!');return endalpha=(r'*r)/(d'*G*d);%收敛速度 xx=x+alpha*d; rr=r+alpha*G*d; beta=(rr'*rr)/(r'*r); d=-rr+beta*d; x=xx; r=rr;fprintf('\n x%d=',k); fprintf('%10.6f',x); enditer=max_iter; return然后建立CG_main 的m.文件，带入数值例子function CG_main()12345123451234512345123451023412923277351432312174351512x x x x x x x x x x x x x x x x x x x x x x x x x ++++=⎧⎪+-+-=-⎪⎪-++-=⎨⎪+++-=-⎪---+=⎪⎩ G=[10 1 2 3 4;1 9 -1 2 -3;2 -1 7 3 -5;3 2 3 12 -1;4 -3 -5 -1 15]; b=[12 -27 14 -17 12]'; x0=[0 0 0 0 0]'; max_iter=1000; tol=1e-6;fprintf('\n');fprintf('Conjugate Gradiant Method:\n'); fprintf('=================\n');[x,iter]=cgopt(G,b,x0,max_iter,tol);fprintf('Iterative number:\n %d\n',iter); fprintf('Solution:\n'); fprintf('%10.6f',x);fprintf('\n================\n');4.结论实际上，共轭梯度法是最速下降法的一种改进。

求解大规模无约束优化问题的共轭梯度法共轭梯度法是求解大规模无约束优化问题的一种重要方法，具有快速收敛、少存储、高效率等优势。

本文起首介绍了共轭梯度法的基本原理及算法流程，接着对其收敛性进行了证明。

随后，分析了共轭梯度法在实际应用中存在的一些问题，并提出了相应的解决方案。

在此基础上，本文进一步探讨了共轭梯度法在无约束优化问题中的应用，并通过实例验证了其有效性。

最后，本文对共轭梯度法的进步趋势进行了展望，指出其在大规模数据处理和机器进修领域中可能会有广泛的应用前景。

关键词：共轭梯度法；大规模无约束优化问题；收敛性；实际应用；进步趋势一、引言在科学探究和工程实践中，浩繁问题都可以转化为优化问题，因此优化问题的求解一直是探究热点之一。

对于大规模无约束优化问题，由于其非线性、高维度、复杂性等特点，传统的优化算法往往难以胜任。

共轭梯度法作为一种有效的优化方法，可以在这种状况下发挥重要作用。

二、共轭梯度法的基本原理及算法流程共轭梯度法是求解无约束优化问题的一种迭代法，其基本思想是利用共轭梯度方一直加速迭代过程。

详尽而言，该方法通过一系列的迭代步骤，不息更新查找方向和步长，以期找到最优解。

其迭代流程如下：（1）给出初始点 $x^{(0)}$，初始查找方向 $d^{(0)}$，初始步长 $\alpha^{(0)}$；（2）计算 $x^{(k+1)}=x^{(k)}+\alpha^{(k)}d^{(k)}$；（3）计算 $g^{(k+1)}=\nabla f(x^{(k+1)})$，其中$f(x)$ 是目标函数的梯度；（4）计算 $\beta^{(k+1)}=\frac{\left \| g^{(k+1)}\right \|^2}{\left \| g^{(k)} \right \|^2}$；（5）计算 $d^{(k+1)}=-g^{(k+1)}+\beta^{(k+1)}d^{(k)}$；（6）计算 $\alpha^{(k+1)}=\arg \min_{\alpha \geq 0}f(x^{(k)}+\alpha d^{(k+1)})$；（7）重复步骤（2）至（6），直至达到预定精度或迭代次数上限。

第三章 无约束最优化的梯度方法1.最速下降法假定我们已经迭代了k 次，获得了第k 个迭代点k x 。

从k x 出发，显然应沿下降方向进行，由于负梯度方向是最速下降方向，因此沿负梯度方向应该是有利的。

因此，取搜索方向)(k k x f p -∇=。

)(1k k k k x f t x x ∇-=+此时有：0)()(1=∇∇+k T k x f x f如将该方法应用于二次函数c x b Qx x x f T T ++=21)(，则可求出k t 的显式表达式。

)()()())(()(1k k k k k k k k k k x f Q t x f x f Q t b Qx b x f t x Q b Qx x f ∇-∇=∇-+=+∇-=+=∇+0)()()()(=∇∇-∇∇k T k k k T k x f Q x f t x f x fkTk kTk k T k k T k k Qg g g g x f Q x f x f x f t =∇∇∇∇=)()()()( 2.Newton 法适用条件：如果目标函数)(x f 在n R 上具有连续的二阶偏导数，其Hesse 矩阵)(x G 正定。

基本想法：考虑从k x 到1+k x 的迭代过程。

在k x 点处用二次函数来逼近)(x f ，即：))(()(21)()()()()(k k T k k T k k x x x G x x x x x g x f x Q x f --+-+=≈0)())(()(=+-=∇k k k x g x x x G x Q)()(11k k k k x g x G x x x -+-==3.共轭方向法与共轭梯度法 1) 共轭方向法定义1:设Q 是n n ⨯对称正定矩阵。

若n 维空间中非零向量系110,...,,-m p p p 满足0=j T i Qp p ，)(1,...,2,1,j i m j i ≠-= ,则称110,...,,-m p p p 是Q 共轭的，或称110,...,,-m p p p 的方向是Q 共轭方向。

一种新的无约束优化的混合杂交共轭梯度法高海音;朱天晓;许春玲【摘要】We proposed a new hybrid conjugate gradient method. It does not need to use Wolfe line search to guarantee the global convergence. An initial self-adaptive step size and sufficient descents are obtained to the function at each iteration. Numerical results show that the method is feasible and effective.%针对无约束优化问题,提出一种新的混合杂交共轭梯度法,该方法在不采用Wolfe搜索的条件下,保证了算法的全局收敛性,并在每次迭代过程中,均可得到初始的自适应步长和充分下降方向.数值结果表明,该算法可行、有效.【期刊名称】《吉林大学学报（理学版）》【年(卷),期】2012(050)003【总页数】5页(P457-461)【关键词】共轭梯度法;全局收敛;无约束优化【作者】高海音;朱天晓;许春玲【作者单位】长春大学数学与应用数学系,长春130022;长春大学数学与应用数学系,长春130022;东北师范大学人文学院信息技术学院,长春130117【正文语种】中文【中图分类】O224.2考虑无约束优化问题(1)其中: f: Rn→R1是连续可微函数; Rn为欧氏空间. 针对无约束优化问题(1), 一般采用线搜索方法进行近似求解, 即xk+1=xk+αkdk, 其中: αk为线搜索步长; {xk+1}为迭代产生的迭代序列; dk为线搜索方向. 针对问题(1), 目前已有许多不同的共轭梯度公式及不同的共轭梯度法[1-6]:文献[7]根据不同情况下的共轭梯度公式βk提出了一种混合搜索方向dk的共轭梯度法, 即使得迭代次数和CPU时间都比经典的DY和HS方法好, 并且得到了较好的数值实验结果. 文献[8]提出两种混合共轭梯度算法, 即其中: 文献[9]提出一种校正的WYL共轭梯度法, 给出一个新的共轭梯度公式并且得到了很好的收敛性质. 本文结合上述混合梯度法的思想和改进的共轭梯度公式提出一种新的混合共轭梯度法, 共轭梯度公式如下:进而得到搜索方向为(2)由于FR共轭梯度法具有很好的收敛性, PRP和NPRP梯度法具有很好的计算效率, 因而使搜索方向dk具有了上述的较好性质. 在适当的条件下, 证明了算法是全局收敛的, 数值实验表明算法可行、有效.1 算法目标函数的迭代计算公式不但要计算搜索方向dk, 而且还要计算搜索步长αk. 目前, 产生搜索步长αk的方法有很多, 如精确线搜索、非精确线搜索等, 为了得到合适的步长, 当算法迭代到最优解附近时, 可能会产生锯齿现象, 即得不到合适的搜索步长, 进而得不到终止迭代, 削减了算法的适应能力. 针对该问题, 时贞军等[10]提出一种不采用线搜索计算搜索步长的方法. 本文采用类似文献[10]的方法, 步长计算公式如下：(3)算法1初始化: 假设x1∈Rn为任意初始点, i=0, β1=0, g1=▽f(x1), d1=-g, k ∶=1；1) 终止条件判定并计算dk: 如果‖gk‖≤ε, 则算法停止; 否则计算dk, 当k=1时, 令dk+1=-gk+1, 转2)；当k>1时, 令其中转2)；2) 计算搜索步长αk: 利用式(3)计算搜索步长αk, 转3)；3) 计算xk: 令xk+1=xk+αkdk, 转4)；4) k=k+1, 返回1).2 算法适定性假设1 水平集Λ={x∈Rn: f(x)≤f(x1)}有下界, 其中x1为初始点, 且Λ为有界闭凸集.假设2 目标函数f(x)的梯度▽f(x)是Lipschitz连续函数, 即存在常数M>0, 满足‖▽f(y)-▽f(z)‖≤M‖y-z‖, ∀y,z∈Rn.定理1 假设1条件成立, 搜索方向dk由算法1生成, 则g(k+1)Tdk+1<0.证明: 由算法1知, 可分两种情况考虑:1) 若k=1, 则dk+1=-gk+1, 有gkTdk=-g(k+1)Tgk+1=-‖gk+1‖2<0;2) 若k>1, 则dk+1=-gk+1+βkdk, 其中有注1 算法1是适定的.3 全局收敛性分析引理1 假设1和假设2条件成立, 算法1生成序列{βk}, 则证明: 针对的不同取值, 可分为如下两种情况考虑：1) 当g(k+1)Tgk≥0时, 有因此, 下面讨论的大小:当‖gk+1‖‖gk‖-1<0时, 有因此故当‖gk+1‖‖gk‖-1>0时, 有因此故2) 当g(k+1)Tgk≤0时, 有下面比较的大小:所以定理2 假设1和假设2条件成立, 算法1生成序列{xk}, 则证明: 假设1和假设2条件成立, 则有其余证明可参见文献[11], 故略.推论1 假设1和假设2条件成立, 构造不同的{βk}如下:均可得到类似引理1的结果.推论2 假设1和假设2条件成立,由推论1生成, dk由算法1生成, 且算法1生成迭代序列{xk}, 则4 数值实验在Matlab7.1环境下编写程序代码, 运行环境: CPU奔腾(R), 2.19 GHz, 1 G内存. 设NI表示所有迭代的总次数; CPU时间表示实际运行时间; βk表示不同的共轭梯度计算公式; Er表示数值计算的精度; AS表示目标函数的近似极小值; m为变量维数; n为每个组成函数的个数. 根据算法1, 采用BFGS校正公式对βk进行校正, 采用Rosenbrock, Freudenstein Roth, Trigonometrix函数为测试函数[12]:(4)f(x)=[-13+x1+((5-x2)x2-2)x2]2+[-29+x1+((x2+1)x2-14)x2]2,(5)(6)其中:fi(x)=n-cos(xi)+i(1-cos(xi))-sin(xi);测试初始点x0分别为(1.2,1),(0.5,-2),(1/n,…,1/n); 目标函数的最优解为f(x*)=0, 目标函数极小解x*分别为(1,1),(5,4),(0,…,0). 程序代码中的参数选取为ε=10-6. 每种算法均选择相同的初始点、参数、精度. 将本文算法与经典方法进行比较, 结果列于表1～表3.表1 算法1与经典算法对函数(4)的数值比较结果Table 1 Comparison of results by algorithm 1 and classical algorithm for function (4)βkNIErCPU时间/smnx∗βNEWk210-6122(1.000 000,1.000 000)βFRk31110-627122(1.000 000,1.000 000)βCDk6610-648722(1.000 000,1.000 000)βPRPk3010-61922(1.000 000,1.000 000)βNPRPk2010-61622(1.000 000,1.00 0000)表2 算法1与经典算法对函数(5)的数值比较结果Table 2 Comparison of results by algorithm 1 and classical algorithm for function (5)βkNIErCPU时间/smnx∗βNEWk11010-61022(5.000 000,4.000 000)βFRk20010-62322(5.000 000,4.000 000)βCDk24310-68722(5.000 000,4.000 000)βPRPk12010-61522(5.000 000,4.000 000)βNPRPk12010-61622(5.000 000,4.000 000)表3 算法1与经典算法对函数(6)的数值比较结果Table 3 Comparison of results by algorithm 1 and classical algorithm for function (6)βkNIErCPU时间/smnx∗βNEWk11510-64522(0.000 000,0.000 000)βFRk78510-644022(0.000 000,0.000 000)βCDk1 04710-658722(0.000 000,0.000 000)βPRPk20010-610322(0.000 000,0.000 000)βNPRPk19010-63322(0.000 000,0.000000)βNEWk12010-659500500(0.000 000,0.000 000)βFRk88710-6562500500(0.000 000,0.000 000)βCDk2 04710-6980500500(0.000000,0.000 000)βPRPk30010-6203500500(0.000 000,0.000000)βNPRPk21010-6100500500(0.000 000,0.000 000)由表1～表3可见, 在CPU所用的时间和迭代步数上, 经典共轭梯度算法比本文算法1所用的时间更长, 而且迭代次数也高于算法1, 因此, 算法1可行、有效.本文仅针对凸函数进行了讨论, 如果目标函数为非凸的, 本文算法可能失效, 但可参见文献[13-15]求解.参考文献【相关文献】[1] Fletcher R, Reeves C. Function Minimization by Conjugate Gradients [J]. Comput J, 1964, 7(2): 149-154.[2] Poliak B T. The Conjugate Gradient Method in Extremal Problems [J]. USSR Comput Math Math Phys, 1969, 9(4): 94-112.[3] Fletcher R. Unconstained Optimization Practical Methods of Optimization [M]. NewYork: Wiley, 1987.[4] Polak E, Ribiere G. Note Surl a Convergence de Méthodes de Directions Conjuguées [J]. Rev Francaise Imformat Recherche Operionelle, 1969, 16(1): 35-43.[5] Liu Y, Storey C. Efficient Generalized Conjugate Gradient Algorithms, Part1: Theory [J]. J Optim Theorem Appl, 1991, 69(1): 129-137.[6] DAI Yu-hong, YUAN Ya-xiang. An Efficient Hybrid Conjugate Gradient Method for Unconstrained Optimization [J]. Ann Oper Res, 2001, 103: 33-47.[7] DAI Yu-hong, HAN Ji-ye, LIU Guang-hui, et al. Convergence Properties of Nonlinear Conjugate Gradient Methods [J]. SIAM J Optim, 1999, 21: 348-358.[8] ZHANG Li, ZHOU Wei-jun, LI Dong-hui. A Descent Modified Polak-Ribière-Polyak Conjugate Gradient Method and Its Global Convergence [J]. IMA J Numer Anal, 2006,26(4): 629-640.[9] ZHANG Li, ZHOU Wei-jun. Two Descent Hybrid Conjugate Gradient Methods for Optimization [J]. J Comput Appl Math, 2008, 216(1): 251-264.[10] SHI Zhen-jun, SHEN Jie. On Step-Size Estimation of Line Search Methods [J]. Appl Math Comput, 2006, 173: 360-371.[11] DUAN Fu-jian, SUN Zhong-bo. A Modified Liu-Storey Conjugate Gradient Method and Its Global Convergence for Unconstrained Optimization [C]//Proceeding of Chinese Control and Decision Conference. Shenyang: North East University Press, 2010: 1585-1588.[12] Moré J J, Garbow B S, Hillstrom K E. Testing Unconstrained Optimization Software [J]. ACM Trans Math Software, 1981, 7(1): 17-41.[13] HE Li, JIN Jian-lu, ZHAO Jia-qi, et al. Combined Homotopy Interior-Point Method fora Class of Nonconvex Multi-objective Programming Problem [J]. Journal of Natural Science of Heilongjiang University, 2010, 27(5): 693-697. (贺莉, 金鉴禄, 赵嘉琦, 等. 一类非凸多目标规划问题的组合同伦内点法 [J]. 黑龙江大学自然科学学报, 2010, 27(5): 693-697.)[14] LIU Qing-huai, ZHANG Chun-yang, ZHANG Shu-gong. Homotopy Method for Solving Nonconvex Optimization with Weak Quasi Normal Condition [J]. Acta Mathematicae Applicatae Sinica, 2011, 34(6): 996-1006. (刘庆怀, 张春阳, 张树功. 弱拟法锥条件下非凸优化问题的同伦算法 [J]. 应用数学学报, 2011, 34(6): 996-1006.)[15] ZHU Ning, WANG Da-bo, QIAO Shuang. Application of Particle Swarm Optimization in Generate Alternative Schemes for Urban Planning [J]. Journal of Northeast Normal University: Natural Science Edition, 2010, 42(2): 37-43. (朱宁, 王大博, 乔双. 粒子群优化算法在可供选择城市规划方案中的应用 [J]. 东北师大学报: 自然科学版, 2010, 42(2): 37-43.)。

DOI ：10.14182/ki.1001-2443.2022.05.003一种充分下降的修正共轭梯度法胡倩蕊1，周光辉1，曹尹平2（1.淮北师范大学数学科学学院安徽淮北235000；2.南京财经大学红山学院江苏南京210006）摘要：共轭梯度法是求解大规模无约束优化问题的一类十分重要的方法，充分下降性对共轭梯度法的收敛性证明具有十分重要的作用。

基于经典的共轭梯度法，本文给出了一类具有充分下降性的共轭梯度法，算法的充分下降性是独立于线搜索的选择。

在适当条件下，证明了该算法在标准Armijo 线搜索下对于求解一致凸函数极小值的问题是全局收敛的。

同时，数值实验表明该算法是有效的。

关键词：无约束优化；共轭梯度法；充分下降性；全局收敛性中图分类号：O224文献标志码：A文章编号：1001-2443（2022）05-0424-09前言对于大规模无约束优化问题min {f (x )|x ∈R n }（1）其中f 是一阶连续的可微函数.共轭梯度法是解决问题（1）的一种很受欢迎的方法，凭借其计算简单且存储数据少，收敛迅速和二次终止性等特点，被广泛应用于求解大规模无约束优化问题.其迭代形式为：x k +1=x k +αk d k ,（2）这里αk 为步长因子，d k 是搜索方向且d k 被定义为d k ={-g k ,-g k +βk d k -1,k =1,k ≥2。

（3）其中g k =∇f (x k )为目标函数f 的梯度函数，βk 为参数标量。

几类经典的βk ［1-6］的形式有：βFRk=g k2g k -12，βHS k=g T k y k -1d Τk -1y k -1，βPRP k =g T k y k -1g k -12，βDYk = g k 2d T k -1y k -1，其中y k -1=g k -g k -1， ·表示为欧几里得范数。

当目标函数f 是严格凸二次函数且采用精确线搜索确定步长因子αk 时，上述经典共轭梯度法可以相互等价。