梯度下降法（精选3篇）
梯度下降法 篇1
1 概述
考虑无约束优化问题
其中f(x):Rn→R是连续可微函数.利用共轭梯度法可以有效求解问题(1),尤其对于大规模无约束优化问题。
共轭梯度法的迭代格式为xk+1=xk+αkdk,其方向dk定义为:
步长αk由线性搜索得到。
常用的线性搜索有精确线性搜索:求αk满足,Armijo线性搜索:给定ρ∈(0,1),求αk=max{ρi|j=0,1,2,⋯}满足f(xk+αkdk)≤f(xk)+δαkgTkdk,Wolf线性搜索:求αk满足,其中0<δ≤σ<1.有关这些线性搜索实现方式可参看文献[1]。
迭代式(2)中参数βk较著名的计算公式有:
其中gk=▽f(xk)是函数f在xk点处的梯度,yk=gk+1-gk,||∙||是欧式范数.
Al-Baali在文献[1]中证明,对于参数σ<1/2,FR方法在强Wolf线性搜索下非凸函数的全局收敛性,被认为数值效果最好的方法之一是PRP方法,但是对于一般非凸函数,PRP方法即使在采用精确线性搜索时也不能保证全局收敛,如Powell在文献[2]中给出的例子.虽然FR方法有全局收敛性,但是在数值试验效果上不如PRP方法,同时HS方法以及文献[3]中给出的DY方法都有类似的情况.综合上述方法中的优点及剔除缺点,Toua⁃ti-Ahmed和Storey在文献[4]中首先提出了混合PRP-FR方法;Gilbert和Nocedal在文献[5]中进一步研究混合PRP-FR方法,使得参数βk允许取负值.Dai和Yuan在文献[6]研究了混合DY-HS共轭梯度法,且在Wolf线性搜索下保证算法的收敛性。
我们称满足gkTdk<0的搜索方向dk为下降方向,称总是产生下降方向的算法为下降算法。本文的目的是构造一种具有充分下降性质且在较弱条件下保证全局收敛性的算法。
2 算法
本文构造一种新的dk迭代格式
其中,
引理1假设方向dk由(3)产生,则对任意k≥0有
证(i)当k=0时,结论显然成立。
(ii)当k>0时,由式(3)知:
引理证明完毕。
下面给出求无约束优化问题的共轭梯度法的具体步骤。
算法A:
步骤0给定常数δ2,ε>0,δ1,α∈(0,1).任意选取初始点x0∈Rn,令k=0。
步骤1按公式(3)计算dk,其中θk,βkTG由(4)确定.若,则停止;否则转步骤2。
步骤2按照如下线性搜索求步长σk,使σk为1,α,α2,⋯中最大值满足:
步骤3令xk+1=xk+σkdk,k=k+1,转步骤1。
3 算法的良定分析和收敛性证明
在算法分析中需要假设Ω:
(a)水平集L={x∈Rn|f(x)≤f(x0)}有界,其中x0为初始点。
(b)存在L的一个邻域B。使f在B上连续可微,且梯度g满足Lipschitz条件,即存在常数
L1>0,对任意x,y∈B有不等式成立,∀x,y∈B.由假设Ω知,存在常数
N>0,M>0,对∀x∈B下列不等式成立。
引理2存在常数η>0,使得下面不等式对任意充分大的k都成立
证由(6)及假设Ω知.由此及(5)可知,和
特别地,。
下面分两种情形证明(8)成立。
(i)当σk=1.由(5),有,令η=1,则不等式(8)成立。
(ii)当σk<1.由步骤2知α-1σk不满足不等式(6),那么就有下面不等式成立。
由微积分中值定理和假设Ω知,存在lk∈(0,1)使得:
将最后一个不等式代入式(10),得取,则可知不等式(8)成立,引理证明完毕。
那么有引理2和式(9),即可得Zoutendijk..
引理3设目标函数满足假设Ω,序列{xk}由算法A产生,则
下面证明算法的全局收敛性。
定理1若假设Ω成立,{xk}和{dk}由算法A产生,则
证利用反证法,假设结论不成立,则存在常数c>0,使得||gk||≥c,∀k≥0.由式(3)知,因此有
由式(3)和式(11)有
因此有:
.
上式等价于,这与引理3矛盾,定理证明完毕。
参考文献
[1]M.Al-Baali,Descent property and global convergence of theFletcher-Reeves method with inexact line search.IMAJ.Num-ber.Anal.,1985(5):121-124.
[2]Powell M J D.Nonconex Minimization calculations and theconjugate gradient method.Lecture Notes in Math.,1984,1066:121-141.
[3]Dai Y H,Yuan Y X.A nonlinear conjugate gradient with astrong alobal convergence property.SIAM Journal of Optimiza-tion,2000(10):177-182.
[4]Touati-Ahmed D,Storey C.Efficient hybrid conjugate gradi-ent techniques.J.Optim.Theory Appl.,1990,64:379-397.
[5]Gilbert J C,Nocedal J.Global convergence properties of conju-gate gradient method for optimization.SIAM.J.Optim.,1992(2):21-42.
[6]Dai Y H,Yuan Y.An efficient hybrid conjugate gradientmethod for unconstrained optimization.Annals of OperationsResearch,2001(103):33-47.
[7]袁亚湘,孙文瑜.最优化理论与方法[M].北京:科学出版社,1995.
[9]张丽.求解最优化问题的非线性共轭梯度法[D].湖南:湖南大学,2006.
梯度下降法 篇2
关键词：无约束优化,共轭梯度法,全局收敛性
1. 引言
考虑无约束优化问题
构造迭代算法xk +1= xk+ αkdk,其中dk为搜索方向,αk为搜索步长. 对αk和dk的不同选择就构成了不同的算法. 60年代Fletecher等人提出一种共轭梯度算法,其基本结构是: dk= - gk+ βkdk -1,当βk选择不同的公式时就得到不同的共轭梯度算法. 几个代表性的公式是:
这些公式分别在文献[1 - 3]给出,这些方法的收敛性在文献[1 - 2,4 - 6]中已经给出.
共轭梯度法适于求解大规模无约束优化问题.
2. 算法与性质
本文总假设目标函数满足以下假设:
假设( a) 水平集有下界,其中x0为初始点.
假设( b) 在水平集L1的一个邻域U内,f连续可微,其导数函数g满足Lipschitz条件,即存在常数L > 0,使:‖g( x) - g( y) ‖≤L‖x - y‖,x,y∈U.
本文步长αk由强Wolfe准则得到:
其中0 < δ < σ < 1.
求解无约束优化问题的共轭梯度算法:
Step 1选一个初始点,置
Step 2若‖gk‖≤ε,停,否则转下一步.
Step 3由强Wolfe准则( 1) ,( 2) 求得
Step 4 若,停,否则,计算
Step 5置 k: = k + 1,转 Step3.
引理1设目标函数满足以上假设条件,考虑一般方法,其中dk满足,步长αk由强Wolfe准则( 1) ,( 2) 求得,则有
此关系式称为zoutendijk条件,见[5].
梯度下降法 篇3
物流配送中心是集取货、集货、包装、仓库、装卸、分货、配货、加工、信息服务、送货等多种服务功能为一体的物流据点。配送中心的分布对现代物流活动有很大的影响,配送中心合理的选址能够减少货物运输费用,进而大大降低运营成本。目前,关于配送中心选址方法的主要出发点是使各项费用的总和最小化,即达到成本最优化。
配送中心选址问题按照配送中心的规划数量大致可分为:单一配送中心的选址和多配送中心的选址。按照配送中心选址空间的连续性可分为:连续空间的配送中心选址和离散空间的配送中心选址问题。
在求解配送中心选址问题时,常用的定量分析方法包括:解析法、模拟法及启发式算法等。对于连续空间的单一配送中心选址问题,目前大量采用的方法包括:重心法和微分法。
重心法属于模拟方法,该方法将求解物流系统配送中心位置的问题转化为求解平面内物体系统的重心。该方法的求解精度较差,所求点的配送成本不是最低点。
微分法,主要用于解决重心法求解不精确的问题,在重心法所得解的基础上进一步地迭代计算,获得精确的解。利用微分迭代的方法虽然能获得精确解,但是往往需要经过数十次、甚至上百次的迭代运算,该方法的收敛速度很慢。
经过观察,单一配送中心的选址模型,普遍是无约束的最优化问题,模型函数具有良好的性质的凸函数,对于此类问题可以采用共轭梯度的方法快速收敛至最优解。本文由此出发通过传统的重心法求得初始点,然后运用共轭梯度法进行运算最终获得最优解。
1 单一配送中心选址模型
在连续区域内分布着n个资源点及配送点,求此区域内一个配送点使配送成本总额最小。模型假设(1)运输费用只与配送中心与配送点,配送中心与资源点的直线距离以及运输量有关,不考虑城市交通状况;(2)运输费率与运输距离和运输量呈线性关系;(3)选择配送中心时,不考虑配送中心所处地理位置的地产价格。空间选址模型如下:
其中:hi配送费率;wi为i点的配送量或资源量;di为i点与配送中心的距离;各资源点或配送点的空间坐标为(xi,yi);为配送中心的空间坐标。
2 算法介绍
2.1 重心法
重心法是将物流系统的需求点和资源点看成是分布在某一平面范围内的物体系统,各点的需求量和资源量分别看成是物体的重量,物体系统的重心将作为物流网点的最佳设置点,利用确定物体重心的方法来确定物流网点的位置。运用重心法求解配送中心的空间坐标为:
重心法的最大优点是计算快捷,但是所求点不是精确的配送中心最佳位置,配送成本仍然有很大的下降空间,为了克服这样的缺点,本文提出了运用共轭梯度法在重心法所得解的基础上进一步计算,从而获得最优解。
2.2 共轭梯度算法
共轭梯度法主要用于求解大规模的无约束最优化问题,形如:
min f(x) x∈Rn
给出一初始值x1,算法迭代产生x2,x3,…。最后收敛于解xp。在第k次迭代,当前迭代点为xk,线搜索型的方法将产生一搜索方向dk∈Rn,然后求得下一个迭代点:
xk+1=xk+αkdk
其中αk>0为步长因子,dk为搜索方向。经过特定的线性搜索方法沿dk方向求出αk,使得优化函数在dk方向上取得最小值。依此类推,经过不断迭代后函数收敛至最优解。
2.3 算法步骤
步骤1:运用公式(1)求解出优化问题的重心坐标;
步骤2:给定初始值(x0,y0),(x0,y0)为重心法求得的解,设k=1,d1=-▽f(x0,y0);
步骤3:若||▽f(xk,yk)||<ε,停止;否则:
步骤4:若(f(xk+1,yk+1)-f(xk,yk))<t,达到要求的精度,停止;否则k+1→k,转步骤3。
3 算例分析
为了展示共轭梯度算法的良好特性,对比共轭梯度算法与微分法在实际应用中的效果,本文引用蒋长兵的《精确重心算法在物流节点选址中的应用》一文中的具体实例进行对比研究。
图2反映了本例选址模型的函数空间性质,我们可以发现选址模型是一个空间凹函数,有且只有一个全局最优解,且不存在其他的局部极小值点。
由式(1)求得此模型的重心坐标,将此点作为初始点代入,并按照共轭梯度算法进行迭代求解,由于手工计算比较复杂,本文采用Visual C++6.0编程求解。设定||▽f(xk,yk)||<ε,ε=0.05;(f)xk+1,yk+1)-f(xk,yk))≤t,t=0.001,表2列出了迭代过程中的具体值:
由表2可见,当使用共轭梯度法进行迭代运算至第4步时,已经达到了规定精度,求得了最优解。表3反映了使用微分法和共轭梯度法,求解本问题时的效率对比。
由表3可以看出,对比利用微分法需要59次才能得到最优解,共轭梯度法只需要4次迭代就能收敛至最优解,表明了共轭梯度算法在求解这类问题时的优越性。
4 结论
混合了重心法和共轭梯度法的配送中心选址方法具有良好的收敛性质,在求解问题时经过很少次的迭代运算就可以达到最优解。同样,经笔者实践发现,采用最速下降法、牛顿法或者拟牛顿法来代替共轭梯度法也能取得不错的效果,都能在20次以内收敛至最优解。
由于共轭梯度算法在求解无约束最优化问题具有良好性能,这为模型的扩展提供了可能。本例的模型假设了运输费率与运输距离和运输量呈线性关系,而现实中确往往不是这样,同时模型没有考虑一定的固定费用,这也影响了模型的参考价值。这些假设主要为了能使模型适合重心法的求解,但是如果采用了共轭梯度法,便可不受这些约束。
由本方法求出的坐标,在现实中可能不具有实际意义,因为坐标点可能位于湖泊,或者街道的中央,但是其仍可以作为参考点,在此坐标的附近选择更适合的位置建立配送中心,本方法也可以在确定备选点时使用。
参考文献
[1]张波.成品油配送油库选址方法[J].中国物流与采购,2006(10):72-73.
[2]苗兴东,李映红,等.重心法选址探讨[J].交通标准化,2004(10):50-52.
[3]霍红,付玮琼.配送中心选址的定量研究[J].物流科技,2004(7):27-30.
[4]鲁晓春,詹荷生.关于配送中心重心法选址的研究[J].北方交通大学学报,2000(12):24-26.
[5]蒋长兵,王姗姗.精确重心算法在物流节点选址中的应用[J].物流技术,2005(9):32-36.
[6]马士华,林勇,陈志祥.供应链管理[M].北京:机械工业出版社,2000.
[7]方仲民.物流系统规划与设计[M].北京:机械工业出版社,2003.