第六节-无约束优化方法-鲍威尔.ppt

《第六节-无约束优化方法-鲍威尔.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章无约束优化方法4.1最速下降法4.2牛顿型方法4.3共轭梯度法4.6鲍威尔方法4.4变尺度法4.5坐标轮换法4.7单形替换法§4.5坐标轮换法一.坐标轮换法：1.基本思想：每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量（其余变量视为常量）的优化问题，因此又称这种方法为变量轮换法。此种方法只需目标函数的数值信息而不需要目标函数的导数。计算步骤:⑴任选初始点,确定搜索方向第一轮的起点，置n个坐标轴方向矢量为单位坐标矢量§4.5坐标轮换法⑵迭代计算k为迭代轮数的

2、序号，取k=1，2，……；i为该轮中一维搜索的序号，取i=1，2，……n步长α一般通过一维优化方法求出其最优步长。⑶判断是否中止迭代如满足，迭代中止，并输出最优解最优解否则，令k←k+1返回步骤（2）§4.5坐标轮换法应该是一轮迭代的始点和终点，不是某搜索方向的前后迭代点。坐标轮换法的流程图例:用坐标轮换法求下列目标函数的无约束最优解。给定初始点，精度要求ε=0.1解：做第一轮迭代计算沿e1方向进行一维搜索式中，为第一轮的起始点，取按最优步长原则确定最优步长α1，即极小化此问题可由某种一维优化方法求出α1:以为新起点，沿e2方向一维搜

3、索以最优步长原则确定α2，即为极小化对于第一轮按终止条件检验计算5轮后，有故近似优化解为§4.5坐标轮换法3.方法评价：方法简单，容易实现。当维数增加时，效率明显下降。收敛慢，以振荡方式逼近最优点。受目标函数的性态影响很大。如图a)所示，二次就收敛到极值点；如图b)所示，多次迭代后逼近极值点；如图c)所示，目标函数等值线出现山脊（或称陡谷），若搜索到A点，再沿两个坐标轴以±t0步长测试，目标函数值均上升，计算机判断A点为最优点。事实上发生错误。鲍威尔方法是直接搜索法中一个十分有效的算法。该算法是沿着逐步产生的共轭方向进行搜索的，因此本

4、质上是一种共轭方向法。§4.6鲍威尔方法一、共轭方向的生成§4.6鲍威尔方法为两个极小点根据梯度与等值面之间关系可知一、共轭方向的生成§4.6鲍威尔方法对于二次函数，两点处的梯度可表示为代入到公式：一、共轭方向的生成§4.6鲍威尔方法结论：从不同的点出发沿某一方向分别对函数作两次一维搜索，得到两个极小点，那么这两个极小点的连线方向与该方向对G共轭二、鲍威尔基本算法鲍威尔基本算法的搜索过程（二维）二、鲍威尔基本算法鲍威尔基本算法的搜索过程（三维）鲍威尔基本算法的步骤：1）第一轮基本方向组取单位坐标矢量系e1、e2、e3、…、en，沿这些

5、方向依次作一维搜索，然后将始末两点相连作为新生方向。2）再沿新生方向作一维搜索，完成第一轮的迭代。以后每轮的基本方向组是将上轮的第一个方向淘汰，上轮的新生方向补入本轮的最后而构成：d2k,d3k,……dnk,dk鲍威尔基本算法的缺陷：可能在某一轮迭代中出现基本方向组为线性相关的矢量系的情况。如第k轮中，产生新的方向：dk=xnk-x0k=1kd1k+2kd2k+•••+nkdnk式中，d1k、d2k、•••、dnk为第k轮基本方向组矢量，1k、2k、•••、nk为各方向的最优步长。若在第k轮的优化搜索过程中出现1k=0，

6、则方向dk表示为d2k、d3k、•••、dnk的线性组合，以后的各次搜索将在降维的空间进行，无法得到n维空间的函数极小值，计算将失败。鲍威尔基本算法的退化x1x2x31=02e23e3S1如图所示为一个三维优化问题的示例，设第一轮中1=0，则新生方向与e2、e3共面，随后的各环方向组中，各矢量必在该平面内，使搜索局限于二维空间，不能得到最优解。e2e3S1三、鲍威尔修正算法在某轮已经取得的n+1个方向中，选取n个线性无关的并且共轭程度尽可能高的方向作为下一轮的基本方向组鲍威尔修正算法的搜索方向的构造：在第k轮的搜索中，x0k为

7、初始点，搜索方向为d1k、d2k、•••、dnk，产生的新方向为dk，此方向的极小点为xk。沿dk方向移动得到点xn+1k=2xnk-x0k，称之为x0k对xnk的映射点。计算x0k、x1k、•••、xnk、xk、xn+1k各点的函数值，记作：F1=F(x0k)F2=F(xnk)F3=F(xn+1k)=F(xm-1k)-F(xmk)是第k轮方向组中，依次沿各方向搜索函数下降值鲍威尔算法的方向淘汰(F3)(F2)(F1)反射点函数最大下降量△m始点终点为了构造第k+1轮基本方向组，采用如下判别式：按照以下两种情况处理：1)上式中至少

8、一个不等式成立，则第k+1轮的基本方向仍用老方向组d1k、d2k、•••、dnk。k+1轮的初始点取x0k+1=xnkF2