《第六节无约束优化方法鲍威尔》由会员分享，可在线阅读，更多相关《第六节无约束优化方法鲍威尔（48页珍藏版）》请在金锄头文库上搜索。
1、 第四章 无约束优化方法4.1 最速下降法4.2 牛顿型方法4.3 共轭梯度法4.6 鲍威尔方法4.4 变尺度法4.5 坐标轮换法4.7 单形替换法2021/6/714.5 4.5 坐标轮换法坐标轮换法一一. . 坐标轮换法：坐标轮换法：1. 1. 基本思想：基本思想：每每次次搜搜索索只只允允许许一一个个变变量量变变化化，其其余余变变量量保保持持不不变变，即即沿沿坐坐标标方方向向轮轮流流进进行行搜搜索索的的寻寻优优方方法法。它它把把多多变变量量的的优优化化问问题题轮轮流流地地转转化化成成单单变变量量（其其余余变变量量视视为为常常量量）的的优优化化问问题题，因因此此又又称称这这种种方方法法为为变
2、变量量轮轮换换法法。此此种种方方法法只只需需目目标标函函数数的的数数值值信信息息而而不不需需要要目目标函数的导数。标函数的导数。2021/6/72计算步骤计算步骤:任选初始点任选初始点,确定搜索方向确定搜索方向第一轮的起点第一轮的起点 ，置，置n个坐标轴方向矢量为单位坐标矢量个坐标轴方向矢量为单位坐标矢量4.5 4.5 坐标轮换法坐标轮换法2021/6/73迭代计算迭代计算k为迭代轮数的序号，取为迭代轮数的序号，取k=1，2，；i为该轮中一维搜索的序号，取为该轮中一维搜索的序号，取i=1，2，n步长步长一般通过一维优化方法求出其最优步长。一般通过一维优化方法求出其最优步长。判断是否中止迭代判断
3、是否中止迭代如满足，迭代中止，如满足，迭代中止，并输出最优解并输出最优解最优解最优解否则，令否则，令kk+1返回步骤（返回步骤（2）4.5 4.5 坐标轮换法坐标轮换法 应应该该是是一一轮轮迭迭代代的的始始点点和和终终点点，不不是是某某搜搜索索方方向向的前后迭代点。的前后迭代点。2021/6/74坐坐标标轮轮换换法法的的流流程程图图2021/6/75例例:用坐标轮换法求下列目标函数的无约束最优解。用坐标轮换法求下列目标函数的无约束最优解。 给定初始点给定初始点 ，精度要求，精度要求=0.1解：解：做第一轮迭代计算做第一轮迭代计算沿沿e1方向进行一维搜索方向进行一维搜索式中，式中， 为第一轮的起
4、始点，取为第一轮的起始点，取2021/6/76按最优步长原则确定最优步长按最优步长原则确定最优步长1，即极小化，即极小化此问题可由某种一维优化方法求出此问题可由某种一维优化方法求出1: 以以 为新起点，沿为新起点，沿e2方向一维搜索方向一维搜索以最优步长原则确定以最优步长原则确定2，即为极小化，即为极小化2021/6/77对于第一轮按终止条件检验对于第一轮按终止条件检验计算计算5轮后，有轮后，有故近似优化解为故近似优化解为2021/6/784.54.5 坐标轮换法坐标轮换法 3. 方法评价：方法评价： 方法简单，容易实现。方法简单，容易实现。 当维数增加时，效率明显下降。当维数增加时，效率明显
5、下降。 收敛慢，以振荡方式逼近最优点收敛慢，以振荡方式逼近最优点。 受目标函数的性态影响很大。受目标函数的性态影响很大。 如图如图 a) 所示，二次就收敛到极值点；所示，二次就收敛到极值点； 如图如图 b) 所示，多次迭代后逼近极值点；所示，多次迭代后逼近极值点； 如图如图 c) 所示，目标函数等值线出现山脊（或称陡所示，目标函数等值线出现山脊（或称陡谷），若搜索到谷），若搜索到 A 点，再沿两个坐标轴以点，再沿两个坐标轴以t0步长测步长测试，目标函数值均上升，计算机判断试，目标函数值均上升，计算机判断 A 点为最优点。点为最优点。事实上发生错误。事实上发生错误。2021/6/79 鲍威尔方法
6、是直接搜索法中一个十分鲍威尔方法是直接搜索法中一个十分有效的算法。该算法是沿着逐步产生的共有效的算法。该算法是沿着逐步产生的共轭方向进行搜索的，因此本质上是一种共轭方向进行搜索的，因此本质上是一种共轭方向法。轭方向法。4.64.6 鲍威尔方法鲍威尔方法 2021/6/710一、共轭方向的生成一、共轭方向的生成4.64.6 鲍威尔方法鲍威尔方法 为两个极小点为两个极小点 根据梯度与等值面之间关系可知根据梯度与等值面之间关系可知2021/6/711一、共轭方向的生成一、共轭方向的生成4.64.6 鲍威尔方法鲍威尔方法 对对于于二二次次函函数数， 两两点点处处的梯度可表示为的梯度可表示为代入到公式：
7、代入到公式：2021/6/712一、共轭方向的生成一、共轭方向的生成4.64.6 鲍威尔方法鲍威尔方法 结结论论：从从不不同同的的点点出出发发沿沿某某一一方方向向分分别别对对函函数数作作两两次次一一维维搜搜索索，得得到到两两个个极极小小点点，那那么么这这两两个个极极小小点点的的连连线线方方向向与与该该方方向向对对G共轭共轭2021/6/713二、鲍威尔基本算法二、鲍威尔基本算法鲍鲍威威尔尔基基本本算算法法的的搜搜索索过过程程（二二维维）2021/6/714二、鲍威尔基本算法二、鲍威尔基本算法鲍鲍威威尔尔基基本本算算法法的的搜搜索索过过程程（三三维维）2021/6/715 鲍威尔基本算法的步骤：
8、鲍威尔基本算法的步骤： 1） 第一轮基本方向组取单位坐标矢量系第一轮基本方向组取单位坐标矢量系e1、 e2、 e3 、 en，沿这些方向依次作一维搜索，然后将始末两点相，沿这些方向依次作一维搜索，然后将始末两点相连作为新生方向。连作为新生方向。 2）再再沿沿新新生生方方向向作作一一维维搜搜索索，完完成成第第一一轮轮的的迭迭代代。以以后后每每轮轮的的基基本本方方向向组组是是将将上上轮轮的的第第一一个个方方向向淘淘汰汰，上上轮轮的的新新生生方方向向补补入入本本轮轮的最后而构成：的最后而构成： d2k , d3k , dnk , dk2021/6/716 鲍威尔基本算法的缺陷：鲍威尔基本算法的缺陷：
9、 可可能能在在某某一一轮轮迭迭代代中中出出现现基基本本方方向向组组为为线线性性相相关关的的矢矢量系的情况。如第量系的情况。如第k轮中，产生新的方向：轮中，产生新的方向： dk=xnk-x0k= 1kd1k+ 2kd2k + + nkdnk 式式中中， d1k、d2k 、 、 dnk为为第第k轮轮基基本本方方向向组组矢矢量量， 1k 、 2k、 、 nk为各方向的最优步长。为各方向的最优步长。 若若在在第第k轮轮的的优优化化搜搜索索过过程程中中出出现现 1k=0，则则方方向向dk表表示示为为d2k、 d3k 、 、 dnk的的线线性性组组合合，以以后后的的各各次次搜搜索索将将在在降降维维的的空空
10、间间进进行行，无无法法得得到到n维维空空间间的的函函数数极极小小值值，计算将失败。计算将失败。2021/6/717鲍威尔基本算法的退化鲍威尔基本算法的退化x1x2x3 1=0 2e2 3e3S1如图所示为一个如图所示为一个三维优化问题的三维优化问题的示例，设第一轮示例，设第一轮中中 1 =0 ，则新，则新生方向与生方向与e2 、e3共面，随后的各共面，随后的各环方向组中，各环方向组中，各矢量必在该平面矢量必在该平面内，使搜索局限内，使搜索局限于二维空间，不于二维空间，不能得到最优解。能得到最优解。e2e3S12021/6/718三、鲍威尔修正算法三、鲍威尔修正算法 在在某某轮轮已已经经取取得得
11、的的n+1个个方方向向中中，选选取取n个个线线性性无无关关的的并且共轭程度尽可能高的方向作为下一轮的基本方向组并且共轭程度尽可能高的方向作为下一轮的基本方向组 鲍鲍威威尔尔修修正正算算法法的的搜搜索索方方向向的的构构造造：在在第第k轮轮的的搜搜索索中中， x0k 为为初初始始点点，搜搜索索方方向向为为d1k、d2k 、 、 dnk，产产生生的的新新方方向向为为dk ，此此方方向向的的极极小小点点为为xk。沿沿dk方方向向移移动动得得到到点点 xn+1k=2xnk-x0k ， 称之为称之为x0k对对xnk的映射点。的映射点。 计计算算x0k 、 x1k、 、 xnk、xk、xn+1k 各各点点的
12、的函函数数值值，记作：记作： F1=F(x0k) F2=F(xnk) F3=F(xn+1k) = F(xm-1k)-F(xmk) 是第是第k轮轮方向组中，依次沿各方向搜索函数下降值方向组中，依次沿各方向搜索函数下降值2021/6/719鲍鲍威威尔尔算算法法的的方方向向淘淘汰汰(F3)(F2)(F1)反射点反射点函数最大下降量函数最大下降量m始点始点终点终点2021/6/720为了构造第为了构造第k+1轮基本方向组，采用如下判轮基本方向组，采用如下判别式别式： 按照以下两种情况处理按照以下两种情况处理： 1) 上式中至少一个不等式成立，则第上式中至少一个不等式成立，则第k+1轮的轮的基本方向仍用
13、老方向组基本方向仍用老方向组d1k、d2k、 、 dnk。 k+1轮的初始点取轮的初始点取 x0k+1=xnk F2F3 x0k+1=xn+1k F2 F32021/6/7212）两式均不成立，则淘汰函数值下降最大的方向，两式均不成立，则淘汰函数值下降最大的方向，并用第并用第k轮的新生方向补入轮的新生方向补入k+1轮基本方向组的最后，轮基本方向组的最后，即即k+1轮的方向组为轮的方向组为d1k、d2k 、 、 dm-1k、dm+1k 、 、dnk、 dk 。(F3)(F2)(F1)反射点反射点始点始点终点终点函数最大下降量函数最大下降量m2021/6/722k+1轮的初始点取轮的初始点取: x
14、0k+1=xk xk是第是第k轮沿轮沿dk方向搜索的极小点。方向搜索的极小点。 (F3)(F2)(F1)反射点反射点函数下降量函数下降量始点始点终点终点dk方向极小点方向极小点2021/6/723四、四、 修正算法的迭代步骤及流程图修正算法的迭代步骤及流程图Powell算法的步骤如下：算法的步骤如下： 任选初始迭代点任选初始迭代点 ，选定迭代精度，选定迭代精度，取初始基本，取初始基本 方向组为单位坐标矢量系方向组为单位坐标矢量系其中，其中，i=1，2n 然后令然后令k=1（轮数）开始迭代（轮数）开始迭代 沿沿 诸方向依次进行诸方向依次进行n次一维搜索，确定各步长次一维搜索，确定各步长 2021
15、/6/724得到点阵得到点阵 i=1，2n构成新生方向构成新生方向沿沿 方向进行一维搜索求得优化步长方向进行一维搜索求得优化步长(3)计算各迭代点的函数值计算各迭代点的函数值 ，找出相邻点函数值差最大者，找出相邻点函数值差最大者（1mn）及与之相对应的两个点及与之相对应的两个点 和和 ，并以，并以 表示两点表示两点的连线方向。的连线方向。2021/6/725（4）关键点函数值关键点函数值（5） 判断是否满足迭代终止条件。判断是否满足迭代终止条件。则可结束迭代，最优解为则可结束迭代，最优解为停止计算。否则，继续进行下步。停止计算。否则，继续进行下步。2021/6/726检验鲍威尔判别条件是否成立
16、检验鲍威尔判别条件是否成立若至少其中之一成立转下步，否则转步骤若至少其中之一成立转下步，否则转步骤 确定确定k+1轮的基本方向组和起始点轮的基本方向组和起始点（即取老方向组即取老方向组）当当F2F3当当F2F3令令kk+1，返回步骤，返回步骤2021/6/727 确定确定k+1轮的方向组和起始点轮的方向组和起始点令令kk+1，返回步骤，返回步骤2021/6/728例例 试用鲍威尔修正算法求目标函数的最优解。已知试用鲍威尔修正算法求目标函数的最优解。已知 初始点初始点 ，迭代精度，迭代精度=0.001解解：第一轮迭代计算第一轮迭代计算沿第一坐标方向沿第一坐标方向e1进行一维搜索进行一维搜索1=2
17、2021/6/729以以 为起点，改沿第二坐标轴方向为起点，改沿第二坐标轴方向e2进行一维搜索进行一维搜索2=0.5构成新方向构成新方向2021/6/730沿沿d1方向进行一维搜索得极小点与极小值方向进行一维搜索得极小点与极小值计算点距计算点距需进行第二轮迭代计算需进行第二轮迭代计算2021/6/731第二轮迭代计算第二轮迭代计算首先确定上轮中的最大函数下降量及其相应方向首先确定上轮中的最大函数下降量及其相应方向映射点及其函数值映射点及其函数值2021/6/732检查鲍威尔条件检查鲍威尔条件于是可知于是可知鲍威尔条件两式均不成立。第二轮取基本方向组和起始鲍威尔条件两式均不成立。第二轮取基本方向
18、组和起始点为点为2021/6/733沿沿e2方向作一维搜索得方向作一维搜索得以以 为起点沿为起点沿d1方向一维搜索得方向一维搜索得2021/6/734构成新生方向构成新生方向沿沿d2方向一维搜索得方向一维搜索得检查迭代终止条件检查迭代终止条件需再作第三轮迭代计算。需再作第三轮迭代计算。2021/6/735根据具体情况来分析，根据具体情况来分析，d1，d2实际上为共轭方向，见下图。实际上为共轭方向，见下图。本题又是二次函数，有共轭方向的二次收敛性，上面结果本题又是二次函数，有共轭方向的二次收敛性，上面结果就是问题的最优解。可以预料，如果做第三轮迭代，则一就是问题的最优解。可以预料，如果做第三轮迭
19、代，则一定各一维搜索的步长为零，必有定各一维搜索的步长为零，必有故得最优解故得最优解2021/6/736在在不不计计算算导导数数的的情情况况下下，先先算算出出若若干干点点处处的的函函数数值值，从从它它们们之之间间的的大大小小关关系系中中也也可可以以看看出出函函数数变变化化的的大大概概趋趋势势，为寻求函数的下降方向提供依据。，为寻求函数的下降方向提供依据。原原理理：利利用用单单纯纯形形的的顶顶点点，计计算算其其函函数数值值并并加加以以比比较较，从从中中确确定定有有利利的的搜搜索索方方向向和和步步长长，找找到到一一个个较较好好的的点点取取代代单单纯纯形形中中较较差差的的点点，组组成成新新的的单单纯
20、纯形形来来代代替替原原来来的的单单纯纯形形。使使新新单单纯纯形形不不断断的的向向目目标标函函数数的的极极小小点点靠靠近近，直直到搜索到极小点位置到搜索到极小点位置4.74.7 单形替换法单形替换法方法方法 2021/6/7374.74.7 单形替换法单形替换法方法方法 设设x5称为称为x1点相对于点相对于x4点的反射点点的反射点x4为为x2点、点、x3点连线的中点点连线的中点取取2021/6/7384.74.7 单形替换法单形替换法方法方法 五种情况：五种情况：1）如果如果构成新的单纯形构成新的单纯形x2x3x6如果如果构成新的单纯形构成新的单纯形x2x3x52021/6/7394.74.7
21、单形替换法单形替换法方法方法 五种情况：五种情况：2）构成新的单纯形构成新的单纯形x2x3x52021/6/7404.74.7 单形替换法单形替换法方法方法 五种情况：五种情况：3）如果如果构成新的单纯形构成新的单纯形x2x3x7如果如果构成新的单纯形构成新的单纯形x2x3x52021/6/7414.74.7 单形替换法单形替换法方法方法 五种情况：五种情况：4）如果如果构成新的单纯形构成新的单纯形x2x3x82021/6/7424.74.7 单形替换法单形替换法方法方法 五种情况：五种情况：5） ，构成新的单纯形，构成新的单纯形x3x9x11 2021/6/743无约束优化问题的评价准则无约
22、束优化问题的评价准则无约束优化问题的评价准则无约束优化问题的评价准则 为了比较各种优化方法的特性，必须建立合理的评为了比较各种优化方法的特性，必须建立合理的评价准则。价准则。 无约束优化方法评价准则主要包括以下几个方面：无约束优化方法评价准则主要包括以下几个方面： 1、可靠性、可靠性。即在合理的精度要求下，在一定允许时。即在合理的精度要求下，在一定允许时间内能解出各种不同类型问题的成功率。能够解出的问间内能解出各种不同类型问题的成功率。能够解出的问题越多，则算法的可靠性越好。题越多，则算法的可靠性越好。 2、有效性、有效性。即算法的解题效率。它有两个衡量标准。即算法的解题效率。它有两个衡量标准
23、。其一是对同一题目，在相同精度和初始条件下，比较机其一是对同一题目，在相同精度和初始条件下，比较机时多少。其二是在相同精度下，计算同一题目所需要的时多少。其二是在相同精度下，计算同一题目所需要的函数的计算次数。函数的计算次数。 3、简便性、简便性。一方面指实现该算法的准备工作量的大。一方面指实现该算法的准备工作量的大小。另一方面指算法占用存储单元的数量。小。另一方面指算法占用存储单元的数量。2021/6/744 无约束优化方法搜索方向之间的相互联系无约束优化方法搜索方向之间的相互联系搜搜 索索 方方 向向函数梯度修正因子函数梯度修正因子所用目标函数信息所用目标函数信息梯梯 度度 法法I（单位阵
24、）（单位阵）一阶导数一阶导数牛牛 顿顿 法法二阶导数二阶导数共轭梯度法共轭梯度法一阶导数一阶导数 变尺度法变尺度法一阶导数一阶导数方方 法法鲍威尔法鲍威尔法函数值函数值 零阶方法零阶方法单形替换法单形替换法 零阶方法零阶方法函数值函数值 最差点和最好点与最差点和最好点与次好点中点的连线次好点中点的连线2021/6/745 可靠性可靠性：牛顿法较差，因为它对目标函数要求太高，：牛顿法较差，因为它对目标函数要求太高，解题成功率较低。解题成功率较低。 有效性有效性：坐标变换法和梯度法的计算效率较低，因为：坐标变换法和梯度法的计算效率较低，因为它们从理论上不具有二次收敛性。它们从理论上不具有二次收敛性
25、。 简便性简便性：牛顿法和变尺度法的程序编制较复杂，牛顿：牛顿法和变尺度法的程序编制较复杂，牛顿法还占用较多的存储单元。法还占用较多的存储单元。 在选用无约束优化方法时，一方面要考虑优化方法的在选用无约束优化方法时，一方面要考虑优化方法的特点，另一方面要考虑目标函数的情况。特点，另一方面要考虑目标函数的情况。 1、一般而言，对于维数较低或者很难求得导数的目标、一般而言，对于维数较低或者很难求得导数的目标函数，使用坐标轮换法或鲍威尔法较合适。函数，使用坐标轮换法或鲍威尔法较合适。 2、对于二次性较强的目标函数，使用牛顿法效果好。、对于二次性较强的目标函数，使用牛顿法效果好。 3、对于一阶偏导数易求的目标函数，使用梯度法可使、对于一阶偏导数易求的目标函数，使用梯度法可使程序编制简单，但精度不宜过高。程序编制简单，但精度不宜过高。 4、综合而言，鲍威尔法和变尺度法（、综合而言，鲍威尔法和变尺度法（DFP）具有较好）具有较好的性能。的性能。2021/6/746本章结束本章结束Thank YouThank You！2021/6/747部分资料从网络收集整理而来，供大家参考，感谢您的关注！
