第四章无约束优化方法.ppt

《第四章无约束优化方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1第四章常用的无约束优化方法4.1坐标轮换法4.2鲍威尔(Powell)法4.3梯度法4.5牛顿法4.6DFP变尺度法4.7BFGS变尺度法无约束优化方法的评价准则及选用2若存在则称X*点为无约束最优点，F(X)为无约束最优值。直接搜索法：坐标轮换法、鲍威尔法方法间接法：梯度法、牛顿法、变尺度法直接搜索法：只需进行函数值的计算与比较来确定迭代方向和步长间接法：利用函数的一阶或二阶偏导数矩阵来确定迭代方向和步长对于无约束优化问题:34.1坐标轮换法基本思想：把一个n维无约束最优化问题转化为依次沿n个坐标轴方向的一维最优化问题。即迭代方向依次为:第一轮:任取一初始点X(0)一维搜索求得一维

2、搜索求得第二轮:4终止准则:上式点距准则中的两点应是一轮迭代的始点与终点利用一维优化方法确定沿该方向上具有最小目标函数值的步长，即:min{F(X(k)+αS(k))}=F(X(k)+α(k)S(k))迭代步长α的确定:5坐标轮换法的流程图6坐标轮换法的特点:具有程序结构简单，易于掌握等优点。但收敛慢，适用于n<10的低维优化问题。另收敛速度与等值线的形状有关7例题4.1用坐标轮换法求目标函数的无约束最优解。给定初始点精度要求ε=0.1解：作第一轮迭代计算。沿e1方向进行一维搜索按最优步长原则确定步长α1，即极小化此问题可用某种一维优化方法求出α1。在这里，我们暂且借用

3、微分学求导解出，令其一阶导数为零，α1=5以为新起点，沿e2方向一维搜索以最优步长原则确定α2，即极小化得α2=4.5，对于第一轮按终止条件检验8例题4.1对于第一轮按终止条件检验:继续第二轮迭代计算。以下各轮的计算结果列于表4.1。9例题4.1计算五轮后有故近似优化解为F*＝F(x*)=7.9502510例题4.1用解析法验证解:令正定114.2鲍威尔(Powell)法鲍威尔法是直接搜索法中一个十分有效的算法。该算法是沿着逐步产生的共轭方向进行搜索的，因此本质上是一种共轭方向法，鲍威尔法的收敛速率较快。以共轭方向作为搜索方向，不只限于鲍威尔法，也用于其他一些较为有效的方法，可以统称为

4、共轭方向法。因此，共轭方向的概念在优化方法研究中占有重要的地位。共轭方向在最优化问题中的应用是基于其具有一个重要性质，即：设S1、S2、…、Sn是关于A的n个互相共轭的向量，则对于求正定二次函数的极小点，从任意初始点出发，依次沿Si（i=1，2，…，n)方向进行一维最优化搜索，至多n步便可以收敛到极小点．122.5关于优化方法中搜寻方向的理论基础2.5.2共轭方向(见第二章)一、共轭方向的基本概念若有两个n维矢量S1、S2，对n×n阶对称正定矩阵A能满足:称n维空间矢量S1与S2对A共轭共轭矢量所代表的方向称为共轭方向。正交:可以看作是共轭的特例例:(1)共轭并正交13例:(2)共轭但

5、不正交设A为n×n阶实对称正定矩阵，有一组非零的n维矢量S1、S2、…、Sq，若满足i≠j则称矢量系Si(i＝1，2，…，q≤n)对于矩阵A共轭14以二维函数为例:二维正定二次函数具有两个重要特性：1）二维正定二次函数的等值线是同心的椭圆族，且椭圆中心就是正定二元二次函数的极小点。2)过同心椭圆族中心x*作任意直线，此直线与诸椭圆交点处的切线相互平行。或者说：两条平行的任意方向的切线,其切点的连线必通过椭圆簇的中心。可以证明上诉S1和S2方向是关于矩阵A的共轭方向。15S1与S2是对A共轭的一对矢量证明：梯度而即结论:两个平行方向的极小点构成的新方向与原方向相互共轭即S1与S2对A共轭

6、也即对于二维正定二次函数只要分别沿两个共轭方向寻优即可找到最优点.16与此类似，可以推出对于n维正定二次函数，共轭方向的一个十分重要的极为有用的性质：从任意初始点出发，依次沿n个线性无关的与A共轭的方向S1，S2，…Sn各进行一维搜索，那么总能在第n步或n步之前就能达到n维正定二次函数的极小点；并且这个性质与所有的n个方向的次序无关。简言之，用共轭方向法对于二次函数从理论上来讲，n步就可达到极小点。因而说共轭方向法具有有限步收敛的特性。通常称具有这种性质的算法为二次收敛算法。共轭矢量之所以引起优化研究者的重视，就是因为它的这些性质对提高优化方法的收敛速率极为有用。17例设二维目标函数，

7、给定方向S1＝e2，初始点，求与S1相共轭的S2，并求函数的极小点。解：(1)第一个搜索方向(2)函数的海赛矩阵对称正定(3)从点沿S1方向求极小点x(1)，即18例解：(4)任取另初始点沿S1方向一维搜索求得该方向极小点x(2)X(2)=(5)求与S1相共轭的方向S2S2=X(2)-X(1)=核验计算矢量S1与S2确为对A矩阵共轭。(6)从x(1)点出发，沿S2方向作一维搜索，得极小点X*=[00]T194.2.1鲍威尔基本算法（共轭方向的原