您好,欢迎访问三七文档
硕士学位论文-1-一、无约束优化问题设:nfRR是连续可微函数,考察如下无约束优化问题[1]:(),nminfxxR,(1)我们称:nfRR为问题(1)的目标函数.记()fx为()fx在x处的梯度,若点*nxR满足*()0,fx我们称之为函数f的驻点,或稳定点.由最优解的条件可知,问题(1.1)的解都是稳定点.二、迭代法的基本格式求解(1)常用迭代法,其基本思想是:给定一个初始点0nxR,按照某一迭代规则产生一个点列{}kx,且{()}kfx单调递减,使得当{}kx是有穷点列时,其最后一个点是问题的最优解.当{}kx是无穷点列时,它有极限点,且其极限点是问题的最优解.记kx是第k次迭代时的迭代点,{}kd是第k次迭代时的迭代方向,(0)kk是第k次的迭代步长,则有基本的迭代公式:1,kkkkxxd其中kd是f在x处的一个下降方向,满足()0Tkfxd,k称为步长,通常用线性搜索得到.常用的线性搜索方式如精确线性搜索[2],即k是下面的一维最优化问题的解:0min().kkfxd三、常用的线搜索:(1)Armijo线性搜索:给定(0,1),(0,1),求{,0,1,2,}jkmaxj,满足条件:()()Tkkkkkkkfxdfxgd.(2)(2)Wolfe线性搜索:求k满足条件:()()Tkkkkkkkfxdfxgd,(3)()TTkkkkkkdgxdgd.(4)其中01,第一个不等式保证充分下降,第二个不等式防止步长过小.非线性共轭梯度法的改进-2-(3)强Wolfe线性搜索求k满足条件:()()Tkkkkkkkfxdfxgd,(5)|()|||TTkkkkkkdgxdgd.(6)其中01.(3)推广的Wolfe线性搜索:求k满足条件:()()Tkkkkkkkfxdfxgd,(7)12()TTTkkkkkkkkgddgxdgd.(8)其中12(0,1),0,当12时,推广的Wolfe线性搜索就是强Wolfe线性搜索.(4)Goldstein线性搜索[2]:求k满足条件:12()()TTkkkkkkkkkkgdfxdfxgd,(9)其中:121201.四、常用的算法最速下降法:设f二次连续可微,且对任意的xR,则迭代方向:()kkdfx采用精确线性搜索确定步长。牛顿法:设f二次连续可微,且对任意的xR,2()fx正定,则迭代方向:21()()kkkdfxfx,是函数f在kx处的下降方向,该方向称为Newton方向.它是f在kx处的二次近似212()()()()TTkkkkfxfxssfxsfxs的最小值点.或等价地,kd是下面关于d的线性方程组的解:2()()0.kkfxdfx(10)硕士学位论文-3-拟牛顿法:拟牛顿法的基本思想是在Newton法的子问题(1.11)中用2()kfx的某个近似矩阵kB取代2()kfx.即在某种意义下2()kkBfx,使相应的算法产生的方向是Newton方向的近似.此外,对所有的,kkB对称正定,且容易计算.设f二次连续可微,利用多元函数数Taylor展开得如下近似:2111()()()()kkkkkfxfxfxxx,因此kB的一种合理的取法是:用1kB取代21()kfx时,上面的近似等式成立,即1kB满足方程1kkkBsy,(11)其中,11,()()kkkkkksxxyfxfx.若令111,kkHB则拟牛顿方程(11)可以等价地写成1kkkHys,注意到1kkksxx,拟Newton方向是Newton方向在某种意义上的一个近似.BFGS算法被认为是目前最好的一种算法之一,得到了极为广泛的应用,其修正公式为:1TTkkkkkkkkTTkkkkkBssByyBBsBsys.(12)BFGS算法的步骤:步0:给定常数0,初始对称下定阵0B,选取初始点0nxR,置:0k,步1:如果||()||kfx,终止;步2:解线性方程组:()0kkBdfx;步3:由线搜索确定步长k;步4:令1kkkkxxd,若1||()||kfx,则停止;否则,按(12)确定1kB,步5:置:1kk,转步2.如果步4中采用Armijo型线性搜索,则采用如下修正公式:1,0,,,0.TTTkkkkkkkkkTTkkkkkkTkkkBssByyByssBsysBBys非线性共轭梯度法的改进-4-共轭梯度法共轭梯度法的格式为:1,kkkkxxd(13)其中,方向kd由下式确定:,10,,1.kkkkkgkdgdk(14)其中,参数k的选取满足共轭性,即当目标函数()fx为二次函数时,应使得搜索方向kd与1kd关于()fx的Hessian阵2()kfx共轭.(1.14)中参数k的不同选取方式对应于不同的共轭梯度法,著名的共轭梯度法包括:FR算法、PRP算法、HS算法、共轭下降法(CD算法[11])和DY算法[12],分别由Fletcher-Reever、Polak-Ribiere-Polyak、Hestenes-Stiefel、Fletcher以及Dai-Yuan给出,这些算法中k的定义如下[4]:211221111221111||||,,,||||||||||||||||,,TTFRPRPHSkkkkkkkkTkkkkCDDYkkkkTTkkkkggygyggdyggdgdy其中11kkkygg,||||表示欧氏范数.其中:FR方法在精确线搜索下收敛,DY方法在Wolfe线搜索下收敛,CD算法在强Wolfe线搜索下下降。Hager和Zhang提出了一种新的共轭梯度法,这里我们称为HZ方法,其中HZk的计算方法如下:21111111||||12THZkkkkkTTkkkkyydgdydy(15)对于上述方法,Hager和Zhang证明了kd的充分下降条件:278||||Tkkkgdg.(16)张丽等人提出了一种保守的HZ方法:设kx为当前迭代点00,dg(0)kdk按下式定义:2,111111||||||||||,,.TrkkkkkkHZkkkgifsygsdgdelse(17)硕士学位论文-5-其中HZk由(15)定义,1111,kkkkkksxxygg,1和r是两个常数.该算法在Armijo线搜索下全局收敛。算法4.1(MHZ算法)步0:给定常数1(0,1),(0,1),0,0其中,选取初始点0nxR,置:0k,如果||||kg,终止;步1:按(17)计算kd步2:计算步长k满足Armijo条件(2);步3:令1kkkkxxd;如果1||||kg,终止;步4:置:1kk转步1.非线性共轭梯度法的改进-6-
本文标题:最优化算法期末复习
链接地址:https://www.777doc.com/doc-1272218 .html