无约束优化方法鲍威尔PPT学习教案

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

2、目标函数的导数。 第1页/共47页 任选初始点任选初始点,确定搜索方向确定搜索方向 第一轮的起点第一轮的起点 ，置，置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 坐标轮换法坐标轮换法 第2页/共47页 迭代计算迭代计算 1 kkk iiii xxe k为迭代轮数的序号，取为迭代轮数的序号，取k=1，2，； i为该轮中一维搜索的序号，取为该轮中一维搜索的序号，取i=1，2，n 步长步长一般通过一维优化方法求出其最优步长。一般通过一维优化方法求出其最优步长。 判断是否中止迭代判断

3、是否中止迭代 0 ? kk n xx 如满足，迭代中止如满足，迭代中止 ，并输出最优解，并输出最优解 最优解最优解* k xx*)(*xFF 否则，令否则，令kk+1 返回步骤（返回步骤（2） 4.5 4.5 坐标轮换法坐标轮换法 应该是一轮迭代的始点和终点，不是某搜索方向的前后迭代点。应该是一轮迭代的始点和终点，不是某搜索方向的前后迭代点。 第3页/共47页 坐标轮换法的流程图坐标轮换法的流程图 第4页/共47页 例例:用坐标轮换法求下列目标函数的无约束最优解。用坐标轮换法求下列目标函数的无约束最优解。 给定初始点给定初始点 ，精度要求，精度要求=0.1 60410)( 2121 2 2 2

4、 1 xxxxxxxF 0 0 0 x 解：解：做第一轮迭代计算做第一轮迭代计算 沿沿e1方向进行一维搜索方向进行一维搜索 11 101 1 xxe 式中，式中， 为第一轮的起始点，取为第一轮的起始点，取 1 0 x 10 0 xx 11 11 01 000 x 第5页/共47页 按最优步长原则确定最优步长按最优步长原则确定最优步长1，即极小化，即极小化 12 111 min()1060F x 此问题可由某种一维优化方法求出此问题可由某种一维优化方法求出1: 0102 1 5 1 1 1 5 0 x 以以 为新起点，沿为新起点，沿e2方向一维搜索方向一维搜索 1 1 x 11 212 22 2

5、 550 01 xxe 以最优步长原则确定以最优步长原则确定2，即为极小化，即为极小化 12 122 min()1060F x5 . 4 2 1 2 5 4.5 x 第6页/共47页 对于第一轮按终止条件检验对于第一轮按终止条件检验 1122 20 54.56.7xx 计算计算5轮后，有轮后，有 55 20 0.0413xx 故近似优化解为故近似优化解为 5 2 7.9883 * 5.9981 xx *( *)7.95025ff x 第7页/共47页 3. 方法评价：方法评价： 方法简单，容易实现。方法简单，容易实现。 当维数增加时，效率明显下降。当维数增加时，效率明显下降。 收敛慢，以振荡方

6、式逼近最优点收敛慢，以振荡方式逼近最优点 。 受目标函数的性态影响很大。受目标函数的性态影响很大。 如图如图 a) 所示，二次就收敛到极值点；所示，二次就收敛到极值点； 如图如图 b) 所示，多次迭代后逼近极值点；所示，多次迭代后逼近极值点； 如图如图 c) 所示，目标函数等值线出现山脊（或称陡所示，目标函数等值线出现山脊（或称陡 谷），若搜索到谷），若搜索到 A 点，再沿两个坐标轴以点，再沿两个坐标轴以t0步长步长 测试，目标函数值均上升，计算机判断测试，目标函数值均上升，计算机判断 A 点为最优点为最优 点。事实上发生错误。点。事实上发生错误。 第8页/共47页 4.64.6 鲍威尔方法鲍

7、威尔方法 第9页/共47页 4.64.6 鲍威尔方法鲍威尔方法 0 T j k dg 1 0 T j k dg 为两个极小点为两个极小点 1 , kk xx 1 ()0 T j kk dgg 根据梯度与等值面之间关系可知根据梯度与等值面之间关系可知 第10页/共47页 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 代入到公式：代入到公式： 第11页/共47页 4.64.6 鲍威尔方法鲍威尔方法

8、1 1 ()()0 TT jjkk kk dggdG xx 结论：结论：从不同的点从不同的点 出发沿某一方向分出发沿某一方向分 别对函数作两次一别对函数作两次一 维搜索，得到两个维搜索，得到两个 极小点极小点，那么这两，那么这两 个极小点的连线方个极小点的连线方 向与该方向对向与该方向对G共共 轭轭 第12页/共47页 鲍威尔基本算法的搜索过程（二维）鲍威尔基本算法的搜索过程（二维） 第13页/共47页 鲍威尔基本算法的搜索过程（三鲍威尔基本算法的搜索过程（三 维）维） 第14页/共47页 2）再沿新生方向作一维搜）再沿新生方向作一维搜 索，完成第一轮的迭代索，完成第一轮的迭代 。以后每轮的基

9、本方向。以后每轮的基本方向 组是将上轮的第一个方组是将上轮的第一个方 向淘汰，上轮的新生方向淘汰，上轮的新生方 向补入本轮的最后而构向补入本轮的最后而构 成：成： d2k , d3k , dnk , dk 第15页/共47页 第16页/共47页 鲍威尔基本算法的退化鲍威尔基本算法的退化 x1 x2 x3 1=0 2e2 3e3 S1 如图所示为一如图所示为一 个三维优化问个三维优化问 题的示例，设题的示例，设 第一轮中第一轮中 1 =0 ，则新生方向，则新生方向 与与e2 、e3共面，共面， 随后的各环方随后的各环方 向组中，各矢向组中，各矢 量必在该平面量必在该平面 内，使搜索局内，使搜索局

10、 限于二维空间限于二维空间 ，不能得到最，不能得到最 优解。优解。 e2 e3 S1 第17页/共47页 1 1 max mimm i n ff 第18页/共47页 鲍威尔算法的方向淘汰鲍威尔算法的方向淘汰 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 始点始点 终点终点 第19页/共47页 31 22 1231213 (2)()() 2 m m FF FFFFFFF 第20页/共47页 2）两式均不成立，则淘

11、汰函数值下降最大的方向两式均不成立，则淘汰函数值下降最大的方向 ，并用第，并用第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 d k d (F3) (F2) (F1) 反射点反射点 始点始点 终点终点 函数最大下降量函数最大下降量m 第21页/共47页 k+1轮的初始点取轮的初始点取: x0k+1=xk xk

12、是第是第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方向极小点方向极小点 第22页/共47页 四、四、 修正算法的迭代步骤及流程图修正算法的迭代步骤及流程图 Powell算法的步骤如下：算法的步骤如下： 任选初始迭代点任选初始迭代点 ，选定迭代精度，选定迭代精度，取初始基本，取初始基本 方向组为单位坐标矢量系方向组为单位坐标矢量系 1 0 x

13、1 ii de 其中，其中，i=1，2n 然后令然后令k=1（轮数）开始迭代（轮数）开始迭代 沿沿 诸方向依次进行诸方向依次进行n次一维搜索，确定各步长次一维搜索，确定各步长 k i d 11 ()min() kkkkk iiiiii F xdF xd 第23页/共47页 得到点阵得到点阵 i=1，2n 1 kkkk iiii xxd 构成新生方向构成新生方向 k 0 kk n dxx 沿沿 方向进行一维搜索求得优化步长方向进行一维搜索求得优化步长 k d k kkkk n xxd (3)计算各迭代点的函数值计算各迭代点的函数值 ，找出相邻点函数值差最大者，找出相邻点函数值差最大者 11 ma

14、x()() kk miimm F xF xFF （1mn） 及与之相对应的两个点及与之相对应的两个点 和和 ，并以，并以 表示两点表示两点 的连线方向。的连线方向。 () k i F x 1 k m x k m x k m d 第24页/共47页 （4）关键点函数值关键点函数值 10 2 kkk nn xxx 31 () k n FF x 10 () k FF x 2 () k n FF x （5） 判断是否满足迭代终止条件。判断是否满足迭代终止条件。 0 kk xx 则可结束迭代，最优解为则可结束迭代，最优解为* k xx*)(*xFF 停止计算。否则，继续进行下步。停止计算。否则，继续进行

15、下步。 第25页/共47页 检验鲍威尔判别条件是否成立检验鲍威尔判别条件是否成立 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，返回步骤，返回步骤 第26页/共47页 确定确定k+1轮的方向组和起始点轮的方向组和起始点 1 111 (,) kkkk immk ddddd 1 0 kk xx

16、 令令kk+1，返回步骤，返回步骤 第27页/共47页 例例 试用鲍威尔修正算法求目标函数的最优解。已知试用鲍威尔修正算法求目标函数的最优解。已知 初始点初始点 ，迭代精度，迭代精度=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 第28页/共47页 以以 为起点，改沿第二坐标轴方向为起点，改沿第二坐标轴方向

17、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 第29页/共47页 沿沿d1方向进行一维搜索得极小点与极小值方向进行一维搜索得极小点与极小值 1 19 5 17 10 x 1 ()7.9F x 计算点距计算点距 22 0 1917 112.886 510 kk xx 需进行第二轮迭代计算需进行第二轮迭代计算 第30页/共47页 第二轮迭代计算第二轮迭代计算 首先确定上轮中的最大函数下降量及其相应

18、方向首先确定上轮中的最大函数下降量及其相应方向 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 第31页/共47页 检查鲍威尔条件检查鲍威尔条件 22 1231213 (2)()() 2 m m FFFFFFF 2 12312 (2)()1.25 m FFFFF 2 13 ()32 2 m FF 于是可知于是可知 13 FF 鲍威尔条件两式均不成立。第二轮取基本方向组和起始鲍威尔条件两式均不成立。第二轮取基

19、本方向组和起始 点为点为 1 2 2 (,) i de d 21 0 xx 2 10 ()7.9FF x 31 22 1231213 (2)()() 2 m m FF FFFFFFF 第32页/共47页 沿沿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 第33页/共47页 构成新生方向构成新生方向 222 20 99194 25525 971712 551050 dxx 沿沿d2方向一维搜索得方向一维搜索

20、得 2 4 2 x 2 ()8F x 检查迭代终止条件检查迭代终止条件 22 22 0 1917 420.360 510 xx 需再作第三轮迭代计算。需再作第三轮迭代计算。 第34页/共47页 根据具体情况来分析，根据具体情况来分析，d1，d2实际上为共轭方向，见下图实际上为共轭方向，见下图 。本题又是二次函数，有共轭方向的二次收敛性，上面结。本题又是二次函数，有共轭方向的二次收敛性，上面结 果就是问题的最优解。可以预料，如果做第三轮迭代，则果就是问题的最优解。可以预料，如果做第三轮迭代，则 一定各一维搜索的步长为零，必有一定各一维搜索的步长为零，必有 33 20 0 xx 故得最优解故得最优解 4 * 2 x 8*F 第35页/共47页 4.74.7 单形替换法单形替换法方法方法 第36页/共47页 4.74.7 单形替换法单形替换法方法方法 123 ()()()f xf xf x 544141 ()2xxxxxx x5称为称为x1点相对于点相对于x4点的反射点的反射 点点 x4为为x2点、点、x3点连线的中点点连线的中点 取取 第37页/共47页 4.74.7 单形替换法单形替换法方法方法 53 ()()f xf x 6441 () 1.2 2.0 xxxx 65 ()()f xf x