王东升-直接搜索法.ppt

《王东升-直接搜索法.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、1坐标轮转法Powell法（改进算法）无约束最优化的直接法(DirectMethodsforUnconstrainedOptimizations)2坐标轮换法基本原理基本思想：是把含有n个变量的优化问题轮换地转化为单变量（其它变量视为常量）的优化问题．所谓单变量优化问题就是沿某个坐标轴方向进行一维搜索的问题．寻优思路：先选定一个初始点X0作为第一轮搜索的始点，依次沿n个坐标轴方向进行一维搜索，每次只在一个坐标轴方向上改变相应变量的值，其它n-1个变量均保持不变．在沿第一个坐标轴方向进行一维搜索得到目标函数值的最小点（或近似最小点）后，再以此点作为始点转

2、到沿第二个坐标轴方向进行一维搜索得到，直到沿第n个坐标轴方向搜索结束得到为一个循环．如果不满足收敛准则，则以作为初始点转入下一轮循环，直到经过k次循环，获得满足收敛准则的点，即作为最优点．3迭代步骤取初始点，置坐标轴搜索方向：……首先沿方向进行一维搜索，求出该方向上目标函数的极值点；再以为初始点沿方向进行一维搜索，得到极值点；仿此依次沿进行一维搜索，最终得到极值点．这就完成了第一轮搜索．如果能够满足收敛准则，即可停止搜索，以作为输出．否则，继续以为初始点，进行第二轮循环，依次沿进行一维搜索，得到第二循环的极值点．如此进行下去，直至最终找到满足收敛准则（

3、终止准则）的点，即求得了最优解，再求出目标函数值．具体迭代过程如下：4已知目标函数，终止限．（1）任选取始点作为第一轮循环的初始点，．（2）置搜索方向依次为……（3）按下式求最优步长并进行迭代计算（4）如果，即转（5）；如果，则转（3）．（5）收敛性准则，若满足判别式，即停止迭代，输出最优解及；若不满足，则令转（3）．5有关说明坐标轮换法的优点是算法简单，计算量小，其缺点是计算效率低，对高维问题尤为突出．因此，坐标轮换法通常用于维数较低的优化问题（一般）．6坐标轮换法在各种不同情况下的效能（a）搜索有效；（b）搜索低效；（c）搜索无效存在的问题7鲍威尔

4、法优点无需求解目标函数一阶和二阶导数不明确目标函数表达式；目标函数复杂；对目标函数解析性质不作苛刻要求属于直接求解方法；对函数类型要求较少，适用面广；收敛速度较快直接法收敛速度较慢，但鲍威尔法寻找最速收敛方向，故属直接法中最有效的方法；8理论基础（1/6）共轭方向的性质性质1若非零向量系d0,d1,d2,…,dm-1是对G共轭，则这m个向量是线性无关的。性质2在n维空间中互相共轭的非零向量的个数不超过n。性质3从任意初始点出发，顺次沿n个G的共轭方向d0,d1,d2,…,进行一维搜索，最多经过n次迭代就可以找到的二次函数f(x)极小点。9理论基础（2/

5、6）10理论基础（3/6）11理论基础（4/6）12理论基础（5/6）13理论基础（6/6）14Powell原始算法15Powell原始算法（1/2）16Powell原始算法（2/2）17Powell改进算法1）问题的提出应用Powell基本算法时，若有一次搜索的最优步长为基本算法时，若有一次搜索的最优步长为0，且该方向被换掉，则该算法失效。18Powell改进算法2)Powell对基本算法的改进在获得新方向构成新方向组时,不是轮换地去掉原来的方向,而是经判别后,在n+1个方向中留下最接近共轭的n个方向.①根据Powell条件判定是否需换方向；②如需换

6、向，则换掉函数值下降量最大的方向.19Powell改进算法在某环已经取得的n+1各方向中，选取n个线性无关的并且共轭程度尽可能高的方向作为下一环的基本方向组。鲍威尔修正算法的搜索方向的构造：在第k环的搜索中，x0k为初始点，搜索方向为S1k、S2k、•••、Snk，产生的新方向为Sk，此方向的极小点为xk。点xn+1k=2xnk-x0k，为x0k对xnk的映射点。计算x0k、x1k、•••、xnk、xk、xn+1k各点的函数值，记作：F1=F(x0k)F2=F(xnk)F3=F(xn+1k)=F(xmk)-F(xm-1k)是第k环方向组中，依

7、次沿各方向搜索函数值下降最大值，即Smk方向函数下降最大。20Powell改进算法为了构造第k+1环基本方向组，采用如下判别式：按照以下两种情况处理：1、上式中至少一个不等式成立，则第k+1环的基本方向仍用老方向组S1k、S2k、•••、Snk。k+1的环初始点取x0k+1=xnkF2

8、k环沿Sn+1k方向搜索的极小点。鲍威尔算法的终止条件：

9、

10、xk-x0k

11、

12、21Powel