第六节_无约束优化方法鲍威尔

1、 第四章 无约束优化方法4.1 最速下降法4.2 牛顿型方法4.3 共轭梯度法4.6 鲍威尔方法4.4 变尺度法4.5 坐标轮换法4.7 单形替换法4.5 4.5 坐标轮换法坐标轮换法一一. . 坐标轮换法：坐标轮换法：1. 1. 基本思想：基本思想：每次搜索只允许一个变量每次搜索只允许一个变量变化，其余变量保持不变，变化，其余变量保持不变，即沿坐标方向轮流进行搜即沿坐标方向轮流进行搜索的寻优方法。它把多变索的寻优方法。它把多变量的优化问题轮流地转化量的优化问题轮流地转化成单变量（其余变量视为成单变量（其余变量视为常量）的优化问题，因此常量）的优化问题，因此又称这种方法为变量轮换又称这种方法为

2、变量轮换法。此种方法只需目标函法。此种方法只需目标函数的数值信息而不需要目数的数值信息而不需要目标函数的导数。标函数的导数。计算步骤计算步骤:任选初始点任选初始点,确定搜索方向确定搜索方向第一轮的起点第一轮的起点 ，置，置n个坐标轴方向矢量为单位坐标矢量个坐标轴方向矢量为单位坐标矢量10 x00011e00102e1000ne4.5 4.5 坐标轮换法坐标轮换法迭代计算迭代计算1kkkiiiixxek为迭代轮数的序号，取为迭代轮数的序号，取k=1，2，；i为该轮中一维搜索的序号，取为该轮中一维搜索的序号，取i=1，2，n步长步长一般通过一维优化方法求出其最优步长。一般通过一维优化方法求出其最优

3、步长。判断是否中止迭代判断是否中止迭代0?kknxx如满足，迭代中止，如满足，迭代中止，并输出最优解并输出最优解最优解最优解*kxx*)(*xFF 否则，令否则，令kk+1返回步骤（返回步骤（2）4.5 4.5 坐标轮换法坐标轮换法 应该是一轮迭代应该是一轮迭代的始点和终点，的始点和终点，不是某搜索方向不是某搜索方向的前后迭代点。的前后迭代点。坐标轮换法的流程图坐标轮换法的流程图例例:用坐标轮换法求下列目标函数的无约束最优解。用坐标轮换法求下列目标函数的无约束最优解。 给定初始点给定初始点 ，精度要求，精度要求=0.160410)(21212221xxxxxxxF000 x 解：解：做第一轮迭

4、代计算做第一轮迭代计算沿沿e1方向进行一维搜索方向进行一维搜索11101 1xxe式中，式中， 为第一轮的起始点，取为第一轮的起始点，取10 x100 xx111101000 x 按最优步长原则确定最优步长按最优步长原则确定最优步长1，即极小化，即极小化12111min()1060F x此问题可由某种一维优化方法求出此问题可由某种一维优化方法求出1: 01021511150 x 以以 为新起点，沿为新起点，沿e2方向一维搜索方向一维搜索11x11212 22255001xxe 以最优步长原则确定以最优步长原则确定2，即为极小化，即为极小化12122min()1060F x5 . 421254.

5、5x对于第一轮按终止条件检验对于第一轮按终止条件检验11222054.56.7xx计算计算5轮后，有轮后，有55200.0413xx故近似优化解为故近似优化解为527.9883*5.9981xx*( *)7.95025ff x4.54.5 坐标轮换坐标轮换法法 3. 方法评价：方法评价： 方法简单，容易实现。方法简单，容易实现。 当维数增加时，效率明显下降。当维数增加时，效率明显下降。 收敛慢，以振荡方式逼近最优点收敛慢，以振荡方式逼近最优点。 受目标函数的性态影响很大。受目标函数的性态影响很大。 如图如图 a) 所示，二次就收敛到极值点；所示，二次就收敛到极值点； 如图如图 b) 所示，多次

6、迭代后逼近极值点；所示，多次迭代后逼近极值点； 如图如图 c) 所示，目标函数等值线出现山脊（或称陡所示，目标函数等值线出现山脊（或称陡谷），若搜索到谷），若搜索到 A 点，再沿两个坐标轴以点，再沿两个坐标轴以t0步长步长测试，目标函数值均上升，计算机判断测试，目标函数值均上升，计算机判断 A 点为最优点为最优点。事实上发生错误。点。事实上发生错误。 鲍威尔方法是直接搜索法中一个十鲍威尔方法是直接搜索法中一个十分有效的算法。该算法是沿着逐步产生的分有效的算法。该算法是沿着逐步产生的共轭方向进行搜索的，因此本质上是一种共轭方向进行搜索的，因此本质上是一种共轭方向法。共轭方向法。4.64.6 鲍威

7、尔方法鲍威尔方法 一、共轭方向的生成一、共轭方向的生成4.64.6 鲍威尔方法鲍威尔方法 0Tjkdg 10Tjkdg 为两个极小点为两个极小点 1,kkxx1()0Tjkkdgg根据梯度与等值面之间关系可知根据梯度与等值面之间关系可知一、共轭方向的生成一、共轭方向的生成4.64.6 鲍威尔方法鲍威尔方法 对于二次函数，对于二次函数， 两点处两点处的梯度可表示为的梯度可表示为1,kkxxkkgGxb11kkgGxb11()kkkkggG xx1()0Tjkkdgg代入到公式：代入到公式：一、共轭方向的生成一、共轭方向的生成4.64.6 鲍威尔方法鲍威尔方法 11()()0TTjjkkkkdgg

8、dG xx结论：结论：从不同的点出从不同的点出发沿某一方向分别对发沿某一方向分别对函数作两次一维搜索函数作两次一维搜索，得到两个，得到两个极小点极小点，那么这两个极小点的那么这两个极小点的连线方向与该方向对连线方向与该方向对G共轭共轭二、鲍威尔基本算法二、鲍威尔基本算法鲍威尔基本算法的搜索过程（二维）鲍威尔基本算法的搜索过程（二维）二、鲍威尔基本算法二、鲍威尔基本算法鲍威尔基本算法的搜索过程（三鲍威尔基本算法的搜索过程（三维）维） 鲍威尔基本算法的步骤：鲍威尔基本算法的步骤： 1） 第一轮基本方向组取单位坐标矢量系第一轮基本方向组取单位坐标矢量系e1、 e2、 e3 、 en，沿这些方向依次作

9、一维搜索，然后将始末两点相，沿这些方向依次作一维搜索，然后将始末两点相连作为新生方向。连作为新生方向。 2）再沿新生方向作一维搜）再沿新生方向作一维搜索，完成第一轮的迭代索，完成第一轮的迭代。以后每轮的基本方向。以后每轮的基本方向组是将上轮的第一个方组是将上轮的第一个方向淘汰，上轮的新生方向淘汰，上轮的新生方向补入本轮的最后而构向补入本轮的最后而构成：成： d2k , d3k , dnk , dk 鲍威尔基本算法的缺陷：鲍威尔基本算法的缺陷： 可能在某一轮迭代中出现基本方向组为线性相关的可能在某一轮迭代中出现基本方向组为线性相关的矢量系的情况。如第矢量系的情况。如第k轮中，产生新的方向：轮中，

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

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

12、方向的构造：在第鲍威尔修正算法的搜索方向的构造：在第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轮轮方向组中，依次沿各方向搜

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

14、1=xnk F2F3 x0k+1=xn+1k F2 F331221231213(2)()()2mmFFFFFFFFF2）两式均不成立，则淘汰函数值下降最大的方向，两式均不成立，则淘汰函数值下降最大的方向，并用第并用第k轮的新生方向补入轮的新生方向补入k+1轮基本方向组的最轮基本方向组的最后，即后，即k+1轮的方向组为轮的方向组为d1k、d2k 、 、 dm-1k、dm+1k 、 、dnk、 dk 。1knxkxknxknd0kx1kmxkmx3kd2kx1kx1kd2kdkd(F3)(F2)(F1)反射点反射点始点始点终点终点函数最大下降量函数最大下降量mk+1轮的初始点取轮的初始点取: x0

15、k+1=xk xk是第是第k轮沿轮沿dk方向搜索的极小点。方向搜索的极小点。 1knxkxknxknd0kx1kmxkmx3kd2kx1kx1kd2kdkd(F3)(F2)(F1)反射点反射点函数下降量函数下降量始点始点终点终点dk方向极小点方向极小点四、四、 修正算法的迭代步骤及流程图修正算法的迭代步骤及流程图Powell算法的步骤如下：算法的步骤如下： 任选初始迭代点任选初始迭代点 ，选定迭代精度，选定迭代精度，取初始基本，取初始基本 方向组为单位坐标矢量系方向组为单位坐标矢量系10 x1iide其中，其中，i=1，2n 然后令然后令k=1（轮数）开始迭代（轮数）开始迭代 沿沿 诸方向依次

16、进行诸方向依次进行n次一维搜索，确定各步长次一维搜索，确定各步长 kid11()min()kkkkkiiiiiiF xdF xd得到点阵得到点阵 i=1，2n1kkkkiiiixxd构成新生方向构成新生方向k0kkndxx沿沿 方向进行一维搜索求得优化步长方向进行一维搜索求得优化步长kdkkkkknxxd(3)计算各迭代点的函数值计算各迭代点的函数值 ，找出相邻点函数值差最大者，找出相邻点函数值差最大者11max ()()kkmiimmF xF xFF（1mn）及与之相对应的两个点及与之相对应的两个点 和和 ，并以，并以 表示两点表示两点的连线方向。的连线方向。()kiF x1kmxkmxkm

17、d（4）关键点函数值关键点函数值102kkknnxxx31()knFF x10()kFF x2()knFF x（5） 判断是否满足迭代终止条件。判断是否满足迭代终止条件。0kkxx则可结束迭代，最优解为则可结束迭代，最优解为*kxx*)(*xFF 停止计算。否则，继续进行下步。停止计算。否则，继续进行下步。检验鲍威尔判别条件是否成立检验鲍威尔判别条件是否成立31221231213(2)()()2mmFFFFFFFFF 若至少其中之一成立转下步，否则转步骤若至少其中之一成立转下步，否则转步骤 确定确定k+1轮的基本方向组和起始点轮的基本方向组和起始点1kkiidd（即取老方向组即取老方向组）10

18、02knkkknxxxx当当F2F3当当F2F3令令kk+1，返回步骤，返回步骤 确定确定k+1轮的方向组和起始点轮的方向组和起始点1111(,)kkkkimmkddddd10kkxx令令kk+1，返回步骤，返回步骤例例 试用鲍威尔修正算法求目标函数的最优解。已知试用鲍威尔修正算法求目标函数的最优解。已知 初始点初始点 ，迭代精度，迭代精度=0.001Tx 11 01011x 110()3FF x 2112221242)(xxxxxxF解解：第一轮迭代计算第一轮迭代计算沿第一坐标方向沿第一坐标方向e1进行一维搜索进行一维搜索1201 111min()43F xe1=211101 1113210

19、1xxe 11()7F x 以以 为起点，改沿第二坐标轴方向为起点，改沿第二坐标轴方向e2进行一维搜索进行一维搜索11x1212222min()227F xe2=0.511212 23030.5111.5xxe 122()7.5FF x 构成新方向构成新方向111203121.510.5dxx 沿沿d1方向进行一维搜索得极小点与极小值方向进行一维搜索得极小点与极小值11951710 x 1()7.9F x 计算点距计算点距2201917112.886510kkxx需进行第二轮迭代计算需进行第二轮迭代计算第二轮迭代计算第二轮迭代计算首先确定上轮中的最大函数下降量及其相应方向首先确定上轮中的最大函

20、数下降量及其相应方向11101()()4F xF x 11212()()0.5F xF x 12max,4m 11mde映射点及其函数值映射点及其函数值111120315221.512nxxx 131()7nFF x 检查鲍威尔条件检查鲍威尔条件221231213(2)()()2mmFFFFFFF 212312(2)()1.25mFFFFF213()322mFF于是可知于是可知13FF 鲍威尔条件两式均不成立。第二轮取基本方向组和起始鲍威尔条件两式均不成立。第二轮取基本方向组和起始点为点为122(,)ide d210 xx210()7.9FF x 31221231213(2)()()2mmFF

21、FFFFFFF沿沿e2方向作一维搜索得方向作一维搜索得211951910 x 21()7.98F x 以以 为起点沿为起点沿d1方向一维搜索得方向一维搜索得21x2299259750 x 222()7.996FF x 构成新生方向构成新生方向222209919425525971712551050dxx沿沿d2方向一维搜索得方向一维搜索得242x 2()8F x 检查迭代终止条件检查迭代终止条件222201917420.360510 xx需再作第三轮迭代计算。需再作第三轮迭代计算。根据具体情况来分析，根据具体情况来分析，d1，d2实际上为共轭方向，见下图。实际上为共轭方向，见下图。本题又是二次函

22、数，有共轭方向的二次收敛性，上面结果本题又是二次函数，有共轭方向的二次收敛性，上面结果就是问题的最优解。可以预料，如果做第三轮迭代，则一就是问题的最优解。可以预料，如果做第三轮迭代，则一定各一维搜索的步长为零，必有定各一维搜索的步长为零，必有33200 xx故得最优解故得最优解4*2x 8*F在不计算导数的情况下，先算出若干点处的函数值，在不计算导数的情况下，先算出若干点处的函数值，从它们之间的大小关系中也可以看出函数变化的大概从它们之间的大小关系中也可以看出函数变化的大概趋势，为寻求函数的下降方向提供依据。趋势，为寻求函数的下降方向提供依据。原理：原理：利用单纯形的顶点，计算其函数值并加以比

23、较利用单纯形的顶点，计算其函数值并加以比较，从中确定有利的搜索方向和步长，找到一个较好的，从中确定有利的搜索方向和步长，找到一个较好的点取代单纯形中较差的点，组成新的单纯形来代替原点取代单纯形中较差的点，组成新的单纯形来代替原来的单纯形。使新单纯形不断的向目标函数的极小点来的单纯形。使新单纯形不断的向目标函数的极小点靠近，直到搜索到极小点位置靠近，直到搜索到极小点位置4.74.7 单形替换法单形替换法方法方法 4.74.7 单形替换法单形替换法方法方法 设设123()()()f xf xf x544141()2xxxxxxx5称为称为x1点相对于点相对于x4点的反射点点的反射点x4为为x2点、

24、点、x3点连线的中点点连线的中点取取4.74.7 单形替换法单形替换法方法方法 五种情况：五种情况：1）如果如果构成新的单纯形构成新的单纯形x2x3x6如果如果构成新的单纯形构成新的单纯形x2x3x553()()f xf x6441()1.2 2.0 xxxx65()()f xf x65()()f xf x4.74.7 单形替换法单形替换法方法方法 五种情况：五种情况：2）构成新的单纯形构成新的单纯形x2x3x5352()()()f xf xf x4.74.7 单形替换法单形替换法方法方法 五种情况：五种情况：3）如果如果构成新的单纯形构成新的单纯形x2x3x7如果如果构成新的单纯形构成新的单

25、纯形x2x3x5251()()()f xf xf x7454(),0.5xxxx71()()f xf x71()()f xf x4.74.7 单形替换法单形替换法方法方法 五种情况：五种情况：4）如果如果构成新的单纯形构成新的单纯形x2x3x851()()f xf x8441()xxxx81()()f xf x4.74.7 单形替换法单形替换法方法方法 五种情况：五种情况：5） ，构成新的单纯形，构成新的单纯形x3x9x11 1( )()f xf x无约束优化问题的评价准则无约束优化问题的评价准则 为了比较各种优化方法的特性，必须建立合理的评为了比较各种优化方法的特性，必须建立合理的评价准则。

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