最速下降法原理及例题实例.pdf

《最速下降法原理及例题实例.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最速下降法原理以及其算法的实现最速下降法又称为梯度法，是1847年由著名数学家Cauchy给出的，它是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。作为一种基本的算法，他在最优化方法中占有重要地位。其优点是工作量少，存储变量较少，初始点要求不高；缺点是收敛慢，效率不高，有时达不到最优解。非线性规划研究的对象是非线性函数的数值最优化问题。它的理论和方法渗透到许多方面，特别是在军事、经济、管理、生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。而最速下降法正是n元函数的无约束非线性规划问题minfx(

2、)的一种重要解析法，研究最速下降法原理及其算法实现对我们有着极其重要的意义。一、最速下降法基本原理(一)无约束问题的最优性条件无约束问题的最优解所要满足的必要条件和充分条件是我们设计算法的依据，为此我们有以下几个定理。n1nn定理1设f:RR®在点xRÎ处可微。若存在pRÎ，使TÑ

3、是极大点，此时称它为函数f的**鞍点。以上定理告诉我们，x是无约束问题的的局部最优解的必要条件是：x是其目标函数f的驻点。现给出无约束问题局部最优解的充分条件。n1*n2*定理3设f:RR®在点xRÎ处的Hesse矩阵Ñfx()存在。若*2*Ñ=fx()0，并且Ñfx()正定*则x是无约束问题的严格局部最优解。一般而言，无约束问题的目标函数的驻点不一定是无约束问题的最优解。但对于其目标函数是凸函数的无约束凸规划，下面定理证明了，它的目标函数的驻点就是它的整体最优解。n1*nn定理4设f:RR®，xRÎ，f是R上的可微凸函数。若有*Ñ=fx()0*则x是无约束问

4、题的整体最优解。(二)最速下降法的基本思想和迭代步骤最速下降法又称为梯度法，是1847年由著名数学家Cauchy给出的。他是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。n1设无约束问题中的目标函数f:RR®一阶连续可微。kk最速下降法的基本思想是：从当前点x出发，取函数fx()在点x处下降最快的方向作为我k们的搜索方向p.由fx()的Taylor展式知kkkkTkkf(x)-f(x+tp)=-tÑ+f(x)(po‖‖tp)kk略去t的高阶无穷小项不计，可见取p=-Ñfx()时，函数值下降得最多。于是，我们可

5、以构造出最速下降法的迭代步骤。解无约束问题的的最速下降法计算步骤0第1步选取初始点x，给定终止误差e>0，令k:0=；kkk第2步计算Ñfx()，若‖Ñ£fx()‖e，停止迭代.输出x.否则进行第三步；kk第3步取p=-Ñfx()；第4步进行一维搜索，求t，使得kkkkkf(x+tp)=+minf()xtpkt³0k+1kk令x=+xtp，kk:1=+，转第2步。k由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点。确定最优步长t的方法如下：k方法一：采用任一种一维寻优法kk此时的f(x-Ñtfx())已成为步长t的一元函数，故可用任何

6、一种一维寻优法求出t，即kk+1kkkkf(x)=f(x-tÑf(x))=minf(x-Ñtfx())kt方法二：微分法因为kktf(x-tÑ=f(xt))j()所以，一些简单情况下，可令'j(t)0=以解出近似最优步长t的值。k(三)最速下降法应用举例22(1)T例1minf(x)=x-x+22x++xxx给定初始点X=(0,0)121122éù¶fx()êú¶()xéù1++42xxÑ==êú112解：目标函数fx()的梯度fx()êúêú¶fx()ëû-1++22xx12êúëû¶()x2éù1éù-1(1)(1)(1)(1)(1)Ñ=fX()êú令搜索

7、方向d=-Ñ=fX()êú再从X出发，沿d方向作一维寻优，令ëû-1ëû1é01ùé--ùéùl(1)(1)步长变量为l，最优步长为l，则有Xd+ll=êú+=êúêú1ë01ûëûëûl(1)(1)222故f(x)=f(Xd+l)=(-l)-l+2(-l)+2(-l)l+=ll-=2ljl()1é0ùé--11ùéù'(2)(1)(1)(2)令j(ll)=2-=20可得l=1X=Xd+l=êú+=êúêú求出X点之后，与111ë0ûë11ûëûéù-1éù1(2)(2)(2)上类似地，进行第二次迭代：Ñ=fX()êú令d=-Ñ=fX()êúëû-1ëû1令步

8、长变量为l，最优步长为l，则有2é--