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

求解无约束优化问题的共轭梯度法李芳梅，姚瑞哲指导教师：李良摘要：本文主要针对无约束优化问题，利用共轭梯度法（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 时，上述经典共轭梯度法可以相互等价。

求解无约束优化问题及非线性方程组的共轭梯度法求解无约束优化问题及非线性方程组的共轭梯度法一、引言无约束优化问题和非线性方程组是数学和工程领域中常见的问题。

它们的解决对于优化模型的求解以及工程实际问题的解决具有重要意义。

本文将介绍一种常用的求解无约束优化问题和非线性方程组的方法——共轭梯度法，包括算法原理、步骤和性能分析等。

二、共轭梯度法的算法原理共轭梯度法是一种迭代法，它通过计算一系列共轭方向，逐步接近于最优解。

具体而言，共轭梯度法的算法原理如下：（1）初始化。

选择一个起始值x0，设置迭代精度ε，取初始共轭方向d0=g0=-∇f(x0)，其中g0为梯度的初始值。

（2）迭代过程。

从k=1开始，根据共轭方向的性质，可以得到更新公式xk=xk-1+αkdk，其中αk为步长，dk为共轭方向。

通过下面的迭代公式可以计算共轭方向dk：di=(-gi)+βidi-1βi=(gi，gi)/(gi-1，gi-1)其中gi为第i次迭代的梯度。

（3）收敛判断。

如果满足||gk||<ε，则停止迭代计算，得到近似解。

否则，继续迭代。

三、共轭梯度法的步骤根据共轭梯度法的算法原理，可以得到具体的步骤如下：（1）初始化。

选择起始点x0，设置迭代精度ε，取初始共轭方向d0=g0=-∇f(x0)，其中g0为梯度的初始值。

（2）循环迭代。

从k=1开始，计算步长αk，更新公式xk=xk-1+αkdk，计算新的梯度gk，计算共轭方向dk。

（3）收敛判断。

如果满足||gk||<ε，则停止迭代。

（4）输出结果。

输出近似解xk。

四、共轭梯度法的性能分析共轭梯度法在求解无约束优化问题和非线性方程组时具有一些优良的性能特点：（1）收敛性。

共轭梯度法在理想情况下可以在n步内达到最优解，其中n为问题的维度。

（2）存储要求小。

共轭梯度法只需要存储上一次迭代的结果，存储量较小。

（3）不需要二阶导数信息。

与牛顿法等方法相比，共轭梯度法不需要二阶导数信息，计算速度更快。

一种新的求解无约束规划的共轭梯度法关哲;于宪伟【摘要】研究无约束优化问题的共轭梯度法，推导出一种新的共轭梯度法，算法在新 Wolfe 线搜索条件下具有充分下降性与全局收敛性。

%A new conjugate gradient method for unconstrained optimization problems is studied inthis pa-per,The algorithm in the new Wolfe line search satisfies the sufficient descent condition,and the global convergence.【期刊名称】《湖北民族学院学报（自然科学版）》【年(卷),期】2016(034)001【总页数】4页(P16-19)【关键词】共轭梯度法;无约束优化;全局收敛性;Wolfe线搜索【作者】关哲;于宪伟【作者单位】渤海大学数理学院，辽宁锦州 121000;渤海大学数理学院，辽宁锦州 121000【正文语种】中文【中图分类】O224共轭梯度法是求解无约束优化问题的重要方法之一，基于其算法简单，存储量小的特点，常用于求解大规模优化问题.考虑无约束优化问题:其中f:Rn→R连续可微，对于为问题(1)的共轭梯度法，一般采用如下的迭代格式：其中：gk=f(xk)是f在xk处的梯度，αk是由线性搜索产生的步长，βk是标量，由αk和βk的选取不同，可以产生不同的共轭梯度法.常用的共轭梯度法有：FR 算法[1]、PRP算法[2-3]、HS算法[4]、DY算法[5]、LS算法[6]、CD算法[7]，参数公式分别为：此外还有许多学者对共轭梯度法进行深入研究，并取得丰硕成果[8-13].步长αk步长通常用非精确线性搜索求得，常用的线搜索有Armijio型线搜索和Wolfe型线搜索[14-18]：标准的Armijio型线搜索：其中:ρ∈(0,1),δ∈(0,0.5).标准的Wolfe线搜索：其中参数0<δ<σ<1.优秀的共轭梯度法一般满足充分下降性与全局收敛性，如果假设dk<0，由式(3)可知βk需要满足：设βk>0，令，则式(7)等价于：可知dk-1，设，则得到新的参数公式：当线性搜索精确时，式(9)等价于FR公式.文献[19]对广义Wolfe线搜索进行改进，得到如下线搜索：其中:σk=min{‖dk‖.笔者对标准Wolfe线搜索做出如下改进.将搜索条件(6)改为：其中dk}，即得到新的线性搜索，本文将在新线搜索条件下讨论新算法的性质.算法1步1 给定初始值x1∈Rn，ε>0，d1=-g1，令k：=1；步2 如果‖gk‖≤ε，则停止，否则转步3；步3 由线搜索式(5)和式(10)求出步长αk，由式(2)得出xk+1；步4 利用式(9)计算，由式(3)计算dk+1，令k：=k+1，转步2.命题1 若gk≠0，则有算法1产生的方向为下降方向，即∀.证明当n=1时，，假设当n=k-1时假设成立,即‖dk‖2，则由式(10)可得：由式(3)有dk=-gk+βkdk-1，等式两端分别与gk做内积，并结合式(9)可得：由数学归纳法知命题1成立.本文做如下假设Η：(i)水平集Ω={x∈Rn|f(x)≤f(x1)}有界，f(x)在Ω下方有界.(ii)在Ω邻域N内，f(x)连续可微且梯度函数g(x)是Lipschitz连续的，即存在常数L>0,使得‖g(x)-g(y)‖≤L‖x-y‖，∀x,y∈N恒成立.命题2[20] 设目标函数满足假设Η，xk由迭代式(2)和式(3)产生，其中dk满足dkgk<0，步长由搜索式(5)和式(10)求得，则有：由命题1得：,由式(10)得：由假设(ii)得：由式(14)和式(15)得：由式(16),{fk}为单调减的收敛数列得：对上式两端分别求和得:得证.命题3 假设Η成立，{gk}为算法1生产的数列，则‖gk‖=0.证明若命题3不成立，则存在r>0，使得对任意k≥1有：由式(3)可得：dk+gk=βkdk-1，两端取模平方，移项得：由式(9)和式(12)易知：对式(20)两端同时除以2，可以得到：利用d1=-g1，并递推得：结合式(22)可以得出：对式(23)两端分别求和可得：=+，与命题2矛盾，所以定理得证.为了测试算法的数值表现，用Matlab编程，对如下函数进行数值实验，并与经典算法进行比较：问题1 f(x)=[-13+x1+((5-x2)x2-2)x2]2+[-29+x1((x2+1)x2-14)x2]2,x0=[3,5]Τ.问题2 f(x)=100(x2-x12)2+(1-x1)2 ,x0=[-1.2,2]Τ.问题3 f(x)=(x12+x22)/(1-x1)2 ,x0=[-1.5,0.5]Τ.问题4 f(x)=x12+2x22+2x32+x42-5(x1+x2)-21x3+7x4,x0=[1,1,1,1]Τ.对以上的4个函数进行数值实验，结果见表1，其中参数取δ=0.4，σ=0.6，终止条件为‖gk‖<10-4或迭代次数超过1 000.通过对经典共轭梯度法与线性搜索的研究，推导出一种新的共轭梯度法，并且在新的搜索条件下证明了算法的充分下降性与全局收敛性，该方法可以类似DY方法，使用简短的证明过程即可证明算法的全局收敛性.数值实验表明算法可行.该算法的其他性质还有待进一步研究.。

⽆约束最优化的常⽤⽅法11/22/2017 12:40:56 PM优化问题在很多领域有着重要的应⽤。

为了⽇后查阅⽅便，本⽂列举常见的⽆约束优化⽅法的计算公式。

需要说明的是，本⽂的⼤部分内容选⾃图书《算法笔记》。

⼀、梯度下降法梯度下降法（Gradient Descent Method）也叫做最速下降法（Steepest Descent Method），因为负梯度是函数局部下降最快的⽅向。

梯度下降梯度下降法的迭代格式为x k+1=x k−αk∇f(x k)梯度下降法⾮常简单，只需要知道如何计算⽬标函数的梯度就可以写出迭代格式。

因此，尽管在不少情况下梯度下降法的收敛速度都很慢，也依然不影响它在⼯业界的⼴泛应⽤。

梯度下降法应⽤到⼀些具体模型上有时也会被视作⼀类特定的算法，例如神经⽹络中的后向传导算法（Back Propagation Algorithm）。

随机梯度下降在机器学习中经常有f(x)=∑m i=1ℓi(x)，其中ℓi(x)是第i个训练样本的损失函数。

这时我们可以使⽤随机梯度下降法（Stochastic Gradient Descent Method）。

其迭代格式为x k+1=x k−αk∇ℓr(x k)其中r∈1,2,⋯,m为随机数。

这种做法可以理解为随机选择⼀个训练样本，进⾏⼀次梯度下降的训练。

在机器学习的问题中，我们通常不需要真的求得最优值，这样不精确的迭代，使得算法不容易过拟合。

由于随机梯度下降法的普及，与此相对的梯度下降法有时被称为批量梯度下降法（Batch Gradient Descent Method），因为它同时考虑所有训练样本。

介于批量梯度下降法和随机梯度下降法之间，还有⼩批量梯度下降法（Min-Batch Gradient Descent Method），也就是每次迭代选择若⼲个训练样本。

步长αk的选取梯度下降法可采⽤BB步长（Barzilai Borwein）。

BB步长有两个计算公式，选择其⼀即可。

无约束优化问题的求解方法无约束优化问题是指在不考虑任何限制条件下，通过调整自变量来寻找函数的最大值或最小值的问题。

在数学和工程领域中，无约束优化问题是一个重要的研究方向，其解决方法也非常丰富和多样。

下面将介绍几种常用的无约束优化问题求解方法。

一、梯度下降法梯度下降法是一种基于一阶导数信息的优化算法。

其基本思想是通过不断迭代地朝着函数的负梯度方向进行搜索，从而找到函数的极小值点。

具体来说，梯度下降法的迭代公式如下：x_(x+1)=x_x−x∇x(x_x)，其中x_x代表第x次迭代的自变量的取值，x称为学习率，∇x(x_x)是函数x(x_x)在点x_x处的梯度。

梯度下降法是求解无约束优化问题的常用方法，具有易于实现和收敛性等优点。

但是，梯度下降法有时可能会陷入局部最优解，因此需要进行多次尝试或采用改进的算法。

二、共轭梯度法共轭梯度法是一种基于二阶导数信息的优化算法。

其基本原理是通过逆Hessian矩阵的乘法来更新自变量的取值，从而加速搜索速度。

具体来说，共轭梯度法的迭代公式如下：x_(x+1)=x_x−x_x,x∇x(x_x)，x_x,x=x∇x(x_x)+x_x,x−1共轭梯度法具有高效、迭代次数少、不需要存储Hessian矩阵等优点。

然而，共轭梯度法也存在一些问题，如对于某些特定的函数可能会陷入收敛困难、对于非二次函数可能收敛速度较慢等。

三、拟牛顿法拟牛顿法是一种综合利用一阶和二阶导数信息的优化算法。

其基本思想是通过利用函数在当前点处的一阶导数和二阶导数近似值来构造一个局部的二次模型，从而求解优化问题。

拟牛顿法的迭代公式如下：x_(x+1)=x_x−(x_x)^−1∇x(x_x)，x_x是拟牛顿法的Hessian矩阵近似值。

拟牛顿法具有利用了二阶导数信息、不需要进行二阶导数计算、有较好的全局收敛性等优点。

但是，拟牛顿法也存在一些问题，如需要存储和更新Hessian矩阵近似值、对于非光滑函数可能无法收敛等。

§3共轭梯度法最速下降法：计算步骤简单，但收敛速度较慢；牛顿法和阻尼牛顿法：收敛度快，但计算量及存储量大（每次需计算海森阵及其逆阵）；希望找到一种方法，它兼有这两种方法的优点，又能克服它们缺点。

共轭方向法就是这样的一类方法，且具有二次终止性。

最典型的共轭方向法是共轭梯度法。

XiDian UniversityXiDian University一、共轭方向法及其性质定义3.1 设A 为n 阶对称阵，12,d d 为n 维非零列向量，若 12()0T d Ad = （3.1）则称向量12,d d 为A −正交，或关于A −共轭。

若n A I =，则（3.1）即为12()0T d d =，这就是通常意义下的正交性，故A −正交，或A −共轭是正交概念的推广。

定义3.2设 12,,,md d d "是n R 中的一组非零向量，如果XiDian University()0 () ,1,2,,i T jd Ad i j i j m =≠=" 则这组向量是A 共轭的，或称它们是一组A 共轭方向。

取 2 11 2A ⎛⎞=⎜⎟⎝⎠，1211,11d d ⎛⎞⎛⎞==⎜⎟⎜⎟−⎝⎠⎝⎠，A 共轭，且是正交的； 3411,02d d ⎛⎞⎛⎞==⎜⎟⎜⎟−⎝⎠⎝⎠A 共轭，但不正交；XiDian University 5610,01d d ⎛⎞⎛⎞==⎜⎟⎜⎟⎝⎠⎝⎠，不是A 共轭，但是正交的 注：正交不一定共轭，共轭也不一定正交.定理 3.1 设A 是n 阶对称正定阵，12,,,md d d "是m 个A 共轭的非零向量，则该向量组线性无关。

证：设存在一组数12,,,m ααα"，使121210m m im i i d d d d αααα=+++==∑"XiDian University则对于{1,2,,}j m ∀∈"，有11()()()()0m m j T i j T i j T j i i i i i dA d d Ad d Ad ααα=====∑∑ 又A 是正定阵，j d 为非零向量，所以0(1,2,,)j j m α=="。

在数学和计算机科学领域，无约束优化问题一直是一个热门的研究课题。

而fr共轭梯度法作为一种求解无约束优化问题的重要方法，在实际应用中展现出了强大的优化能力。

本文将就fr共轭梯度法求解无约束优化问题进行全面评估和探讨。

1. 无约束优化问题的定义无约束优化问题是指在没有约束条件的情况下，寻找一个函数的最小值或最大值的问题。

数学上通常用以下形式表示：\[ min\ f(x) \]\[ s.t.\ x \in R^n \]其中，\( f(x) \)为目标函数，\( x \)为自变量。

无约束优化问题在实际应用中广泛存在，比如在机器学习、信号处理、金融等领域都有着重要的应用价值。

2. fr共轭梯度法的基本原理fr共轭梯度法是一种常用的无约束优化方法，它主要用于求解二次型函数的极小值点。

其基本原理是通过迭代的方式，利用fr共轭方向进行搜索，从而逐步逼近最优解。

具体来说，fr共轭梯度法的迭代公式为：\[ x_{k+1} = x_k + \alpha_k d_k \]其中，\( x_k \)为第k次迭代的解，\( d_k \)为fr共轭方向，\( \alpha_k \)为搜索步长。

3. fr共轭梯度法的优势和局限性fr共轭梯度法相对于其他优化算法具有一定的优势，比如收敛速度较快、内存占用小等。

但是，它也存在一些局限性，比如对非二次型函数的性能表现不佳、依赖初始点选取等。

在实际应用中需要结合具体问题特点来选择合适的优化算法。

4. fr共轭梯度法在深度学习中的应用在深度学习领域，优化算法对于模型训练的收敛速度和性能表现有着重要影响。

fr共轭梯度法作为一种优化算法，被广泛应用于深度学习模型的训练过程中。

它可以有效地加速模型的收敛速度，提高训练效率。

5. 个人观点和理解从我个人的角度来看，fr共轭梯度法作为一种经典的优化算法，在实际应用中展现出了较高的效率和性能。

它在求解无约束优化问题时具有明显的优势，特别适用于二次型函数的优化。