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

《第六节无约束优化方法鲍威尔课件.ppt》由会员分享，可在线阅读，更多相关《第六节无约束优化方法鲍威尔课件.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六节无约束优化方法鲍威尔第1页，此课件共44页哦4.5 4.5 坐标轮换法坐标轮换法一一.坐标轮换法：坐标轮换法：1.基本思想：基本思想：每每次次搜搜索索只只允允许许一一个个变变量量变变化化，其其余余变变量量保保持持不不变变，即即沿沿坐坐标标方方向向轮轮流流进进行行搜搜索索的的寻寻优优方方法法。它它把把多多变变量量的的优优化化问问题题轮轮流流地地转转化化成成单单变变量量（其其余余变变量量视视为为常常量量）的的优优化化问问题题，因因此此又又称称这这种种方方法法为为变变量量轮轮换换法法。此此种种方方法法只只需需目目标标函函数数的的数数值值信信息息而不需要目标函数的导数。而不需要目标函数的导数。第

2、2页，此课件共44页哦计算步骤计算步骤:任选初始点任选初始点,确定搜索方向确定搜索方向第一轮的起点第一轮的起点 ，置，置n个坐标轴方向矢量为单位坐标矢量个坐标轴方向矢量为单位坐标矢量4.5 4.5 坐标轮换法坐标轮换法第3页，此课件共44页哦迭代计算迭代计算k为迭代轮数的序号，取为迭代轮数的序号，取k=1，2，；i为该轮中一维搜索的序号，取为该轮中一维搜索的序号，取i=1，2，n步长步长一般通过一维优化方法求出其最优步长。一般通过一维优化方法求出其最优步长。判断是否中止迭代判断是否中止迭代如满足，迭代中止，并如满足，迭代中止，并输出最优解输出最优解最优解最优解否则，令否则，令kk+1返回步骤（

3、返回步骤（2）4.5 4.5 坐标轮换法坐标轮换法 应应该该是是一一轮轮迭迭代代的的始始点点和和终终点点，不不是是某某搜搜索方向的前后迭代点。索方向的前后迭代点。第4页，此课件共44页哦坐坐标标轮轮换换法法的的流流程程图图第5页，此课件共44页哦例例:用坐标轮换法求下列目标函数的无约束最优解。用坐标轮换法求下列目标函数的无约束最优解。给定初始点给定初始点 ，精度要求，精度要求=0.1解：解：做第一轮迭代计算做第一轮迭代计算沿沿e1方向进行一维搜索方向进行一维搜索式中，式中，为第一轮的起始点，取为第一轮的起始点，取第6页，此课件共44页哦按最优步长原则确定最优步长按最优步长原则确定最优步长1，即

4、极小化，即极小化此问题可由某种一维优化方法求出此问题可由某种一维优化方法求出1:以以 为新起点，沿为新起点，沿e2方向一维搜索方向一维搜索以最优步长原则确定以最优步长原则确定2，即为极小化，即为极小化第7页，此课件共44页哦对于第一轮按终止条件检验对于第一轮按终止条件检验计算计算5轮后，有轮后，有故近似优化解为故近似优化解为第8页，此课件共44页哦4.54.5 坐标轮换法坐标轮换法 3.方法评价：方法评价：方法简单，容易实现。方法简单，容易实现。当维数增加时，效率明显下降。当维数增加时，效率明显下降。收敛慢，以振荡方式逼近最优点收敛慢，以振荡方式逼近最优点。受目标函数的性态影响很大。受目标函数

5、的性态影响很大。如图如图 a)所示，二次就收敛到极值点；所示，二次就收敛到极值点；如图如图 b)所示，多次迭代后逼近极值点；所示，多次迭代后逼近极值点；如图如图 c)所示，目标函数等值线出现山脊（或称陡谷），若所示，目标函数等值线出现山脊（或称陡谷），若搜索到搜索到 A 点，再沿两个坐标轴以点，再沿两个坐标轴以t0步长测试，目标函数值步长测试，目标函数值均上升，计算机判断均上升，计算机判断 A 点为最优点。事实上发生错误。点为最优点。事实上发生错误。第9页，此课件共44页哦 鲍威尔方法是直接搜索法中一个十分鲍威尔方法是直接搜索法中一个十分有效的算法。该算法是沿着逐步产生的共有效的算法。该算法是

6、沿着逐步产生的共轭方向进行搜索的，因此本质上是一种共轭方向进行搜索的，因此本质上是一种共轭方向法。轭方向法。4.64.6 鲍威尔方法鲍威尔方法 第10页，此课件共44页哦一、共轭方向的生成一、共轭方向的生成4.64.6 鲍威尔方法鲍威尔方法 为两个极小点为两个极小点 根据梯度与等值面之间关系可知根据梯度与等值面之间关系可知第11页，此课件共44页哦一、共轭方向的生成一、共轭方向的生成4.64.6 鲍威尔方法鲍威尔方法 对对于于二二次次函函数数，两两点点处处的的梯梯度可表示为度可表示为代入到公式：代入到公式：第12页，此课件共44页哦一、共轭方向的生成一、共轭方向的生成4.64.6 鲍威尔方法鲍

7、威尔方法 结结论论：从从不不同同的的点点出出发发沿沿某某一一方方向向分分别别对对函函数数作作两两次次一一维维搜搜索索，得得到到两两个个极极小小点点，那那么么这这两两个个极极小小点点的的连连线线方向与该方向对方向与该方向对G共轭共轭第13页，此课件共44页哦二、鲍威尔基本算法二、鲍威尔基本算法鲍鲍威威尔尔基基本本算算法法的的搜搜索索过过程程（二二维维）第14页，此课件共44页哦二、鲍威尔基本算法二、鲍威尔基本算法鲍鲍威威尔尔基基本本算算法法的的搜搜索索过过程程（三三维维）第15页，此课件共44页哦 鲍威尔基本算法的步骤：鲍威尔基本算法的步骤：1）第一轮基本方向组取单位坐标矢量系第一轮基本方向组取

8、单位坐标矢量系e1、e2、e3、en，沿这些方向依次作一维搜索，然后将始末两点相连作为新生沿这些方向依次作一维搜索，然后将始末两点相连作为新生方向。方向。2）再再沿沿新新生生方方向向作作一一维维搜搜索索，完完成成第第一一轮轮的的迭迭代代。以以后后每每轮轮的的基基本本方方向向组组是是将将上上轮轮的的第第一一个个方方向向淘淘汰汰，上上轮轮的的新新生生方方向向补入本轮的最后而构成：补入本轮的最后而构成：d2k,d3k,dnk ,dk第16页，此课件共44页哦 鲍威尔基本算法的缺陷：鲍威尔基本算法的缺陷：可可能能在在某某一一轮轮迭迭代代中中出出现现基基本本方方向向组组为为线线性性相相关关的的矢矢量量系

9、系的的情情况。如第况。如第k轮中，产生新的方向：轮中，产生新的方向：dk=xnk-x0k=1kd1k+2kd2k+nkdnk 式式中中，d1k、d2k、dnk为为第第k轮轮基基本本方方向向组组矢矢量量，1k、2k、nk为各方向的最优步长。为各方向的最优步长。若若在在第第k轮轮的的优优化化搜搜索索过过程程中中出出现现 1k=0，则则方方向向dk表表示示为为d2k、d3k、dnk的的线线性性组组合合，以以后后的的各各次次搜搜索索将将在在降降维维的的空间进行，无法得到空间进行，无法得到n维空间的函数极小值，计算将失败。维空间的函数极小值，计算将失败。第17页，此课件共44页哦鲍威尔基本算法的退化鲍威

10、尔基本算法的退化x1x2x3 1=0 2e2 3e3S1如图所示为一个三如图所示为一个三维优化问题的示例，维优化问题的示例，设第一轮中设第一轮中 1=0，则新生方向与，则新生方向与e2、e3共面，随后的共面，随后的各环方向组中，各各环方向组中，各矢量必在该平面内矢量必在该平面内，使搜索局限于二，使搜索局限于二维空间，不能得到维空间，不能得到最优解。最优解。e2e3S1第18页，此课件共44页哦三、鲍威尔修正算法三、鲍威尔修正算法 在在某某轮轮已已经经取取得得的的n+1个个方方向向中中，选选取取n个个线线性性无无关关的的并并且且共共轭程度尽可能高的方向作为下一轮的基本方向组轭程度尽可能高的方向作

11、为下一轮的基本方向组 鲍鲍威威尔尔修修正正算算法法的的搜搜索索方方向向的的构构造造：在在第第k轮轮的的搜搜索索中中，x0k 为为初初始始点点，搜搜索索方方向向为为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轮轮方向组中，依次沿各方向搜索函数下

12、降值方向组中，依次沿各方向搜索函数下降值第19页，此课件共44页哦鲍鲍威威尔尔算算法法的的方方向向淘淘汰汰(F3)(F2)(F1)反射点反射点函数最大下降量函数最大下降量m始点始点终点终点第20页，此课件共44页哦为了构造第为了构造第k+1轮基本方向组，采用如下判轮基本方向组，采用如下判别式别式：按照以下两种情况处理按照以下两种情况处理：1)上式中至少一个不等式成立，则第上式中至少一个不等式成立，则第k+1轮的基本轮的基本方向仍用老方向组方向仍用老方向组d1k、d2k、dnk。k+1轮的初轮的初始点取始点取 x0k+1=xnk F2F3 x0k+1=xn+1k F2 F3第21页，此课件共44

13、页哦2）两式均不成立，则淘汰函数值下降最大的方向，并用两式均不成立，则淘汰函数值下降最大的方向，并用第第k轮的新生方向补入轮的新生方向补入k+1轮基本方向组的最后，即轮基本方向组的最后，即k+1轮的方向组为轮的方向组为d1k、d2k、dm-1k、dm+1k、dnk、dk。(F3)(F2)(F1)反射点反射点始点始点终点终点函数最大下降量函数最大下降量m第22页，此课件共44页哦k+1轮的初始点取轮的初始点取:x0k+1=xk xk是第是第k轮沿轮沿dk方向搜索的极小点。方向搜索的极小点。(F3)(F2)(F1)反射点反射点函数下降量函数下降量始点始点终点终点dk方向极小点方向极小点第23页，此

14、课件共44页哦四、四、修正算法的迭代步骤及流程图修正算法的迭代步骤及流程图Powell算法的步骤如下：算法的步骤如下：任选初始迭代点任选初始迭代点 ，选定迭代精度，选定迭代精度，取初始基本，取初始基本 方向组为单位坐标矢量系方向组为单位坐标矢量系其中，其中，i=1，2n 然后令然后令k=1（轮数）开始迭代（轮数）开始迭代 沿沿 诸方向依次进行诸方向依次进行n次一维搜索，确定各步长次一维搜索，确定各步长 第24页，此课件共44页哦得到点阵得到点阵 i=1，2n构成新生方向构成新生方向沿沿 方向进行一维搜索求得优化步长方向进行一维搜索求得优化步长(3)计算各迭代点的函数值计算各迭代点的函数值 ，找

15、出相邻点函数值差最大者，找出相邻点函数值差最大者（1mn）及与之相对应的两个点及与之相对应的两个点 和和 ，并以，并以 表示两点表示两点的连线方向。的连线方向。第25页，此课件共44页哦（4）关键点函数值关键点函数值（5）判断是否满足迭代终止条件。判断是否满足迭代终止条件。则可结束迭代，最优解为则可结束迭代，最优解为停止计算。否则，继续进行下步。停止计算。否则，继续进行下步。第26页，此课件共44页哦检验鲍威尔判别条件是否成立检验鲍威尔判别条件是否成立若至少其中之一成立转下步，否则转步骤若至少其中之一成立转下步，否则转步骤 确定确定k+1轮的基本方向组和起始点轮的基本方向组和起始点（即取老方向

16、组即取老方向组）当当F2F3当当F2F3令令kk+1，返回步骤，返回步骤第27页，此课件共44页哦 确定确定k+1轮的方向组和起始点轮的方向组和起始点令令kk+1，返回步骤，返回步骤第28页，此课件共44页哦例例 试用鲍威尔修正算法求目标函数的最优解。已知试用鲍威尔修正算法求目标函数的最优解。已知 初始点初始点 ，迭代精度，迭代精度=0.001解解：第一轮迭代计算第一轮迭代计算沿第一坐标方向沿第一坐标方向e1进行一维搜索进行一维搜索1=2第29页，此课件共44页哦以以 为起点，改沿第二坐标轴方向为起点，改沿第二坐标轴方向e2进行一维搜索进行一维搜索2=0.5构成新方向构成新方向第30页，此课件

17、共44页哦沿沿d1方向进行一维搜索得极小点与极小值方向进行一维搜索得极小点与极小值计算点距计算点距需进行第二轮迭代计算需进行第二轮迭代计算第31页，此课件共44页哦第二轮迭代计算第二轮迭代计算首先确定上轮中的最大函数下降量及其相应方向首先确定上轮中的最大函数下降量及其相应方向映射点及其函数值映射点及其函数值第32页，此课件共44页哦检查鲍威尔条件检查鲍威尔条件于是可知于是可知鲍威尔条件两式均不成立。第二轮取基本方向组和起始鲍威尔条件两式均不成立。第二轮取基本方向组和起始点为点为第33页，此课件共44页哦沿沿e2方向作一维搜索得方向作一维搜索得以以 为起点沿为起点沿d1方向一维搜索得方向一维搜索

18、得第34页，此课件共44页哦构成新生方向构成新生方向沿沿d2方向一维搜索得方向一维搜索得检查迭代终止条件检查迭代终止条件需再作第三轮迭代计算。需再作第三轮迭代计算。第35页，此课件共44页哦根据具体情况来分析，根据具体情况来分析，d1，d2实际上为共轭方向，见下图。本题又实际上为共轭方向，见下图。本题又是二次函数，有共轭方向的二次收敛性，上面结果就是问题的最优解。是二次函数，有共轭方向的二次收敛性，上面结果就是问题的最优解。可以预料，如果做第三轮迭代，则一定各一维搜索的步长为零，必有可以预料，如果做第三轮迭代，则一定各一维搜索的步长为零，必有故得最优解故得最优解第36页，此课件共44页哦在在不

19、不计计算算导导数数的的情情况况下下，先先算算出出若若干干点点处处的的函函数数值值，从从它它们们之之间间的的大大小小关关系系中中也也可可以以看看出出函函数数变变化化的的大大概概趋趋势势，为寻求函数的下降方向提供依据。为寻求函数的下降方向提供依据。原原理理：利利用用单单纯纯形形的的顶顶点点，计计算算其其函函数数值值并并加加以以比比较较，从从中中确确定定有有利利的的搜搜索索方方向向和和步步长长，找找到到一一个个较较好好的的点点取取代代单单纯纯形形中中较较差差的的点点，组组成成新新的的单单纯纯形形来来代代替替原原来来的的单单纯纯形形。使使新新单单纯纯形形不不断断的的向向目目标标函函数数的的极极小小点点

20、靠靠近近，直直到到搜搜索索到到极极小小点点位置位置4.74.7 单形替换法单形替换法方法方法 第37页，此课件共44页哦4.74.7 单形替换法单形替换法方法方法 设设x5称为称为x1点相对于点相对于x4点的反射点点的反射点x4为为x2点、点、x3点连线的中点点连线的中点取取第38页，此课件共44页哦4.74.7 单形替换法方法单形替换法方法 五种情况：五种情况：1）如果如果构成新的单纯形构成新的单纯形x2x3x6如果如果构成新的单纯形构成新的单纯形x2x3x5第39页，此课件共44页哦4.74.7 单形替换法单形替换法方法方法 五种情况：五种情况：2）构成新的单纯形构成新的单纯形x2x3x5

21、第40页，此课件共44页哦4.74.7 单形替换法单形替换法方法方法 五种情况：五种情况：3）如果如果构成新的单纯形构成新的单纯形x2x3x7如果如果构成新的单纯形构成新的单纯形x2x3x5第41页，此课件共44页哦4.74.7 单形替换法单形替换法方法方法 五种情况：五种情况：4）如果如果构成新的单纯形构成新的单纯形x2x3x8第42页，此课件共44页哦4.74.7 单形替换法单形替换法方法方法 五种情况：五种情况：5），构成新的单纯形，构成新的单纯形x3x9x11 第43页，此课件共44页哦无约束优化问题的评价准则无约束优化问题的评价准则无约束优化问题的评价准则无约束优化问题的评价准则 为

22、了比较各种优化方法的特性，必须建立合理的评价准则。为了比较各种优化方法的特性，必须建立合理的评价准则。无约束优化方法评价准则主要包括以下几个方面：无约束优化方法评价准则主要包括以下几个方面：1、可靠性、可靠性。即在合理的精度要求下，在一定允许时间。即在合理的精度要求下，在一定允许时间内能解出各种不同类型问题的成功率。能够解出的问题越内能解出各种不同类型问题的成功率。能够解出的问题越多，则算法的可靠性越好。多，则算法的可靠性越好。2、有效性、有效性。即算法的解题效率。它有两个衡量标准。其。即算法的解题效率。它有两个衡量标准。其一是对同一题目，在相同精度和初始条件下，比较机时多少。一是对同一题目，在相同精度和初始条件下，比较机时多少。其二是在相同精度下，计算同一题目所需要的函数的计算次其二是在相同精度下，计算同一题目所需要的函数的计算次数。数。3、简便性、简便性。一方面指实现该算法的准备工作量的大小。一方面指实现该算法的准备工作量的大小。另一方面指算法占用存储单元的数量。另一方面指算法占用存储单元的数量。第44页，此课件共44页哦