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

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

2、又称这种方法为变量轮换又称这种方法为变量轮换 法。此种方法只需目标函法。此种方法只需目标函 数的数值信息而不需要目数的数值信息而不需要目 标函数的导数。标函数的导数。 计算步骤计算步骤: 任选初始点任选初始点,确定搜索方向确定搜索方向 第一轮的起点第一轮的起点 ，置，置n个坐标轴方向矢量为单位坐标矢量个坐标轴方向矢量为单位坐标矢量 1 0 x 0 0 0 1 1 e 0 0 1 0 2 e 1 0 0 0 n e 4.5 4.5 坐标轮换法坐标轮换法 迭代计算迭代计算 1 kkk iiii xxe k为迭代轮数的序号，取为迭代轮数的序号，取k=1，2，； i为该轮中一维搜索的序号，取为该轮中一

3、维搜索的序号，取i=1，2，n 步长步长一般通过一维优化方法求出其最优步长。一般通过一维优化方法求出其最优步长。 判断是否中止迭代判断是否中止迭代 0 ? kk n xx 如满足，迭代中止，如满足，迭代中止， 并输出最优解并输出最优解 最优解最优解* k xx*)(*xFF 否则，令否则，令kk+1 返回步骤（返回步骤（2） 4.5 4.5 坐标轮换法坐标轮换法 应该是一轮迭代应该是一轮迭代 的始点和终点，的始点和终点， 不是某搜索方向不是某搜索方向 的前后迭代点。的前后迭代点。 坐标轮换法的流程图坐标轮换法的流程图 例例:用坐标轮换法求下列目标函数的无约束最优解。用坐标轮换法求下列目标函数的

4、无约束最优解。 给定初始点给定初始点 ，精度要求，精度要求=0.1 60410)( 2121 2 2 2 1 xxxxxxxF 0 0 0 x 解：解：做第一轮迭代计算做第一轮迭代计算 沿沿e1方向进行一维搜索方向进行一维搜索 11 101 1 xxe 式中，式中， 为第一轮的起始点，取为第一轮的起始点，取 1 0 x 10 0 xx 11 11 01 000 x 按最优步长原则确定最优步长按最优步长原则确定最优步长1，即极小化，即极小化 12 111 min()1060F x 此问题可由某种一维优化方法求出此问题可由某种一维优化方法求出1: 0102 1 5 1 1 1 5 0 x 以以 为

5、新起点，沿为新起点，沿e2方向一维搜索方向一维搜索 1 1 x 11 212 22 2 550 01 xxe 以最优步长原则确定以最优步长原则确定2，即为极小化，即为极小化 12 122 min()1060F x5 . 4 2 1 2 5 4.5 x 对于第一轮按终止条件检验对于第一轮按终止条件检验 1122 20 54.56.7xx 计算计算5轮后，有轮后，有 55 20 0.0413xx 故近似优化解为故近似优化解为 5 2 7.9883 * 5.9981 xx *( *)7.95025ff x 4.54.5 坐标轮换坐标轮换 法法 3. 方法评价：方法评价： 方法简单，容易实现。方法简单

6、，容易实现。 当维数增加时，效率明显下降。当维数增加时，效率明显下降。 收敛慢，以振荡方式逼近最优点收敛慢，以振荡方式逼近最优点。 受目标函数的性态影响很大。受目标函数的性态影响很大。 如图如图 a) 所示，二次就收敛到极值点；所示，二次就收敛到极值点； 如图如图 b) 所示，多次迭代后逼近极值点；所示，多次迭代后逼近极值点； 如图如图 c) 所示，目标函数等值线出现山脊（或称陡所示，目标函数等值线出现山脊（或称陡 谷），若搜索到谷），若搜索到 A 点，再沿两个坐标轴以点，再沿两个坐标轴以t0步长步长 测试，目标函数值均上升，计算机判断测试，目标函数值均上升，计算机判断 A 点为最优点为最优

7、点。事实上发生错误。点。事实上发生错误。 鲍威尔方法是直接搜索法中一个十鲍威尔方法是直接搜索法中一个十 分有效的算法。该算法是沿着逐步产生的分有效的算法。该算法是沿着逐步产生的 共轭方向进行搜索的，因此本质上是一种共轭方向进行搜索的，因此本质上是一种 共轭方向法。共轭方向法。 4.64.6 鲍威尔方法鲍威尔方法 一、共轭方向的生成一、共轭方向的生成 4.64.6 鲍威尔方法鲍威尔方法 0 T j k dg 1 0 T j k dg 为两个极小点为两个极小点 1 , kk xx 1 ()0 T j kk dgg 根据梯度与等值面之间关系可知根据梯度与等值面之间关系可知 一、共轭方向的生成一、共轭

8、方向的生成 4.64.6 鲍威尔方法鲍威尔方法 对于二次函数，对于二次函数， 两点处两点处 的梯度可表示为的梯度可表示为 1 , kk xx k k gGxb 1 1 k k gGxb 1 1 () kk kk ggG xx 1 ()0 T j kk dgg 代入到公式：代入到公式： 一、共轭方向的生成一、共轭方向的生成 4.64.6 鲍威尔方法鲍威尔方法 1 1 ()()0 TT jjkk kk dggdG xx 结论：结论：从不同的点出从不同的点出 发沿某一方向分别对发沿某一方向分别对 函数作两次一维搜索函数作两次一维搜索 ，得到两个，得到两个极小点极小点， 那么这两个极小点的那么这两个极

9、小点的 连线方向与该方向对连线方向与该方向对 G共轭共轭 二、鲍威尔基本算法二、鲍威尔基本算法 鲍威尔基本算法的搜索过程（二维）鲍威尔基本算法的搜索过程（二维） 二、鲍威尔基本算法二、鲍威尔基本算法 鲍威尔基本算法的搜索过程（三鲍威尔基本算法的搜索过程（三 维）维） 鲍威尔基本算法的步骤：鲍威尔基本算法的步骤： 1） 第一轮基本方向组取单位坐标矢量系第一轮基本方向组取单位坐标矢量系e1、 、 e2、 e3 、 、 、 en，沿这些方向依次作一维搜索，然后将始末两点相，沿这些方向依次作一维搜索，然后将始末两点相 连作为新生方向。连作为新生方向。 2）再沿新生方向作一维搜）再沿新生方向作一维搜 索

10、，完成第一轮的迭代索，完成第一轮的迭代 。以后每轮的基本方向。以后每轮的基本方向 组是将上轮的第一个方组是将上轮的第一个方 向淘汰，上轮的新生方向淘汰，上轮的新生方 向补入本轮的最后而构向补入本轮的最后而构 成：成： d2k , d3k , dnk , dk 鲍威尔基本算法的缺陷：鲍威尔基本算法的缺陷： 可能在某一轮迭代中出现基本方向组为线性相关的可能在某一轮迭代中出现基本方向组为线性相关的 矢量系的情况。如第矢量系的情况。如第k轮中，产生新的方向：轮中，产生新的方向： dk=xnk-x0k= 1kd1k+ 2kd2k + + nkdnk 式中，式中， d1k、d2k 、 、 dnk为第为第k

11、轮基本方向组矢轮基本方向组矢 量，量， 1k 、 2k、 、 nk为各方向的最优步长。为各方向的最优步长。 若在第若在第k轮的优化搜索过程中出现轮的优化搜索过程中出现 1k=0，则方向，则方向dk表表 示为示为d2k、 d3k 、 、 dnk的线性组合，以后的各次搜索的线性组合，以后的各次搜索 将在降维的空间进行，无法得到将在降维的空间进行，无法得到n维空间的函数极小值，维空间的函数极小值， 计算将失败。计算将失败。 鲍威尔基本算法的退化鲍威尔基本算法的退化 x1 x2 x3 1=0 2e2 3e3 S1 如图所示为一个如图所示为一个 三维优化问题的三维优化问题的 示例，设第一轮示例，设第一轮

12、 中中 1 =0 ，则新，则新 生方向与生方向与e2 、e3 共面，随后的各共面，随后的各 环方向组中，各环方向组中，各 矢量必在该平面矢量必在该平面 内，使搜索局限内，使搜索局限 于二维空间，不于二维空间，不 能得到最优解。能得到最优解。 e2 e3 S1 三、鲍威尔修正算法三、鲍威尔修正算法 在某轮已经取得的在某轮已经取得的n+1个方向中，选取个方向中，选取n个线性无关的个线性无关的 并且共轭程度尽可能高的方向作为下一轮的基本方向组并且共轭程度尽可能高的方向作为下一轮的基本方向组 鲍威尔修正算法的搜索方向的构造：在第鲍威尔修正算法的搜索方向的构造：在第k轮轮的搜索中的搜索中 ， x0k 为

13、初始点，搜索方向为为初始点，搜索方向为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轮轮方向组中，依次沿各方向搜索函数下降值方向组中，依次沿各方向搜索函数下降值 1 1 max mimm i n

14、ff 鲍威尔算法的方向淘汰鲍威尔算法的方向淘汰 1 k n x k x k n x k n d 0 k x 1 k m x k m x 3 k d 2 k x 1 k x 1 k d 2 k d k d (F3) (F2) (F1) 反射点反射点 函数最大下降量函数最大下降量m 始点始点 终点终点 为了构造第为了构造第k+1轮基本方向组，采用如下判轮基本方向组，采用如下判 别式别式： 按照以下两种情况处理按照以下两种情况处理： 1) 上式中至少一个不等式成立，则第上式中至少一个不等式成立，则第k+1轮的轮的 基本方向仍用老方向组基本方向仍用老方向组d1k、d2k、 、 dnk。 k+1轮的初始

15、点取轮的初始点取 x0k+1=xnk F2F3 x0k+1=xn+1k F2 F3 31 22 1231213 (2)()() 2 m m FF FFFFFFF 2）两式均不成立，则淘汰函数值下降最大的方向，两式均不成立，则淘汰函数值下降最大的方向， 并用第并用第k轮的新生方向补入轮的新生方向补入k+1轮基本方向组的最轮基本方向组的最 后，即后，即k+1轮的方向组为轮的方向组为d1k、d2k 、 、 dm-1k、 dm+1k 、 、dnk、 dk 。 1 k n x k x k n x k n d 0 k x 1 k m x k m x 3 k d 2 k x 1 k x 1 k d 2 k

16、d k d (F3) (F2) (F1) 反射点反射点 始点始点 终点终点 函数最大下降量函数最大下降量m k+1轮的初始点取轮的初始点取: x0k+1=xk xk是第是第k轮沿轮沿dk方向搜索的极小点。方向搜索的极小点。 1 k n x k x k n x k n d 0 k x 1 k m x k m x 3 k d 2 k x 1 k x 1 k d 2 k d k d (F3) (F2) (F1) 反射点反射点 函数下降量函数下降量 始点始点 终点终点 dk方向极小点方向极小点 四、四、 修正算法的迭代步骤及流程图修正算法的迭代步骤及流程图 Powell算法的步骤如下：算法的步骤如下：

17、 任选初始迭代点任选初始迭代点 ，选定迭代精度，选定迭代精度，取初始基本，取初始基本 方向组为单位坐标矢量系方向组为单位坐标矢量系 1 0 x 1 ii de 其中，其中，i=1，2n 然后令然后令k=1（轮数）开始迭代（轮数）开始迭代 沿沿 诸方向依次进行诸方向依次进行n次一维搜索，确定各步长次一维搜索，确定各步长 k i d 11 ()min() kkkkk iiiiii F xdF xd 得到点阵得到点阵 i=1，2n 1 kkkk iiii xxd 构成新生方向构成新生方向 k 0 kk n dxx 沿沿 方向进行一维搜索求得优化步长方向进行一维搜索求得优化步长 k d k kkkk

18、n xxd (3)计算各迭代点的函数值计算各迭代点的函数值 ，找出相邻点函数值差最大者，找出相邻点函数值差最大者 11 max ()() kk miimm F xF xFF （1mn） 及与之相对应的两个点及与之相对应的两个点 和和 ，并以，并以 表示两点表示两点 的连线方向。的连线方向。 () k i F x 1 k m x k m x k m d （4）关键点函数值关键点函数值 10 2 kkk nn xxx 31 () k n FF x 10 () k FF x 2 () k n FF x （5） 判断是否满足迭代终止条件。判断是否满足迭代终止条件。 0 kk xx 则可结束迭代，最优解

19、为则可结束迭代，最优解为* k xx*)(*xFF 停止计算。否则，继续进行下步。停止计算。否则，继续进行下步。 检验鲍威尔判别条件是否成立检验鲍威尔判别条件是否成立 31 22 1231213 (2)()() 2 m m FF FFFFFFF 若至少其中之一成立转下步，否则转步骤若至少其中之一成立转下步，否则转步骤 确定确定k+1轮的基本方向组和起始点轮的基本方向组和起始点 1kk ii dd （即取老方向组即取老方向组） 1 0 0 2 k n k kk n x x xx 当当F2F3 当当F2F3 令令kk+1，返回步骤，返回步骤 确定确定k+1轮的方向组和起始点轮的方向组和起始点 1

20、111 (,) kkkk immk ddddd 1 0 kk xx 令令kk+1，返回步骤，返回步骤 例例 试用鲍威尔修正算法求目标函数的最优解。已知试用鲍威尔修正算法求目标函数的最优解。已知 初始点初始点 ，迭代精度，迭代精度=0.001 T x 11 0 1 0 1 1 x 1 10 ()3FF x 211 2 2 2 1 242)(xxxxxxF 解解：第一轮迭代计算第一轮迭代计算 沿第一坐标方向沿第一坐标方向e1进行一维搜索进行一维搜索 12 01 111 min()43F xe1=2 11 101 1 113 2 101 xxe 1 1 ()7F x 以以 为起点，改沿第二坐标轴方向

21、为起点，改沿第二坐标轴方向e2进行一维搜索进行一维搜索 1 1 x 12 12222 min()227F xe2=0.5 11 212 2 303 0.5 111.5 xxe 1 22 ()7.5FF x 构成新方向构成新方向 1 11 20 312 1.510.5 dxx 沿沿d1方向进行一维搜索得极小点与极小值方向进行一维搜索得极小点与极小值 1 19 5 17 10 x 1 ()7.9F x 计算点距计算点距 22 0 1917 112.886 510 kk xx 需进行第二轮迭代计算需进行第二轮迭代计算 第二轮迭代计算第二轮迭代计算 首先确定上轮中的最大函数下降量及其相应方向首先确定上

22、轮中的最大函数下降量及其相应方向 11 101 ()()4F xF x 11 212 ()()0.5F xF x 12 max,4 m 1 1m de 映射点及其函数值映射点及其函数值 111 120 315 22 1.512 n xxx 1 31 ()7 n FF x 检查鲍威尔条件检查鲍威尔条件 22 1231213 (2)()() 2 m m FFFFFFF 2 12312 (2)()1.25 m FFFFF 2 13 ()32 2 m FF 于是可知于是可知 13 FF 鲍威尔条件两式均不成立。第二轮取基本方向组和起始鲍威尔条件两式均不成立。第二轮取基本方向组和起始 点为点为 1 2

23、2 (,) i de d 21 0 xx 2 10 ()7.9FF x 31 22 1231213 (2)()() 2 m m FF FFFFFFF 沿沿e2方向作一维搜索得方向作一维搜索得 2 1 19 5 19 10 x 2 1 ()7.98F x 以以 为起点沿为起点沿d1方向一维搜索得方向一维搜索得 2 1 x 2 2 99 25 97 50 x 2 22 ()7.996FF x 构成新生方向构成新生方向 222 20 99194 25525 971712 551050 dxx 沿沿d2方向一维搜索得方向一维搜索得 2 4 2 x 2 ()8F x 检查迭代终止条件检查迭代终止条件 2

24、2 22 0 1917 420.360 510 xx 需再作第三轮迭代计算。需再作第三轮迭代计算。 根据具体情况来分析，根据具体情况来分析，d1，d2实际上为共轭方向，见下图。实际上为共轭方向，见下图。 本题又是二次函数，有共轭方向的二次收敛性，上面结果本题又是二次函数，有共轭方向的二次收敛性，上面结果 就是问题的最优解。可以预料，如果做第三轮迭代，则一就是问题的最优解。可以预料，如果做第三轮迭代，则一 定各一维搜索的步长为零，必有定各一维搜索的步长为零，必有 33 20 0 xx 故得最优解故得最优解 4 * 2 x 8*F 在不计算导数的情况下，先算出若干点处的函数值，在不计算导数的情况下

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

26、近，直到搜索到极小点位置 4.74.7 单形替换法单形替换法方法方法 4.74.7 单形替换法单形替换法方法方法 设设 123 ()()()f xf xf x 544141 ()2xxxxxx x5称为称为x1点相对于点相对于x4点的反射点点的反射点 x4为为x2点、点、x3点连线的中点点连线的中点 取取 4.74.7 单形替换法单形替换法方法方法 五种情况：五种情况： 1） 如果如果 构成新的单纯形构成新的单纯形 x2x3x6 如果如果 构成新的单纯形构成新的单纯形 x2x3x5 53 ()()f xf x 6441 () 1.2 2.0 xxxx 65 ()()f xf x 65 ()()

27、f xf x 4.74.7 单形替换法单形替换法方法方法 五种情况：五种情况： 2） 构成新的单纯形构成新的单纯形 x2x3x5 352 ()()()f xf xf x 4.74.7 单形替换法单形替换法方法方法 五种情况：五种情况： 3） 如果如果 构成新的单纯形构成新的单纯形 x2x3x7 如果如果 构成新的单纯形构成新的单纯形 x2x3x5 251 ()()()f xf xf x 7454 (),0.5xxxx 71 ()()f xf x 71 ()()f xf x 4.74.7 单形替换法单形替换法方法方法 五种情况：五种情况： 4） 如果如果 构成新的单纯形构成新的单纯形 x2x3x

28、8 51 ()()f xf x 8441 ()xxxx 81 ()()f xf x 4.74.7 单形替换法单形替换法方法方法 五种情况：五种情况： 5） ，构成新的单纯形，构成新的单纯形x3x9x11 1 ( )()f xf x 无约束优化问题的评价准则无约束优化问题的评价准则 为了比较各种优化方法的特性，必须建立合理的评为了比较各种优化方法的特性，必须建立合理的评 价准则。价准则。 无约束优化方法评价准则主要包括以下几个方面：无约束优化方法评价准则主要包括以下几个方面： 1、可靠性、可靠性。即在合理的精度要求下，在一定允许时。即在合理的精度要求下，在一定允许时 间内能解出各种不同类型问题的成功率。能够解出的问间内能解出各种不同类型问题的成功率。能够解出的问 题越多，则算法的可靠性越好。题越多，则算法的可靠性越好。 2、有效性、有效性。即算法的解题效率。它有两个衡量标准。即算法的解题效率。它有两个衡量标准 。其一是对同一题目，在相同精度和初始条件下，比较。其一是对同一题目，在相同精度和初始条件下，比较 机时多少。其二是在相同精度下，计算同一题目所需要机时多少。其二是在相同精度下，计算同一题目所需要 的函数的计算次数。的函数的计算次数。 3、简便性、简便性。一方面指实现该算法的准备工作量的大。一方面指实现该算法的准备工作量的大 小