现代设计方法第14章 优化设计-多维无约束优化

1、第第14讲讲 最优化设计最优化设计多维无约束优化多维无约束优化 现代设计方法最优化设计nnRXxxxfXf)()(min21，求解这类问题的方法，称为求解这类问题的方法，称为。的的为：为：有很多种，但归纳可以分为有很多种，但归纳可以分为： 解析法解析法 直接法直接法 现代设计方法最优化设计 解析法解析法 这类方法这类方法是需要利用函数的一阶偏导数甚至二阶偏导数是需要利用函数的一阶偏导数甚至二阶偏导数构造搜构造搜索方向索方向，如梯度法、牛顿法和变尺度法等。，如梯度法、牛顿法和变尺度法等。由于需要计算偏导数，故这类方法计算量大，但收敛较快。由于需要计算偏导数，故这类方法计算量大，但收敛较快。 直接

2、法直接法 这类方法这类方法是仅利用迭代点的函数值来是仅利用迭代点的函数值来构造搜索方向构造搜索方向，如坐标轮换，如坐标轮换法、法、powell 共轭梯度法和单纯形法等。共轭梯度法和单纯形法等。由于只需要由于只需要计算函数值计算函数值，对于无法求导或求导困难的函数，则这，对于无法求导或求导困难的函数，则这类方法就有突出的优越性，但是其收敛速度较慢。类方法就有突出的优越性，但是其收敛速度较慢。 现代设计方法最优化设计14.1 坐标轮换法坐标轮换法 是求解多维无约束优化问题的一种是求解多维无约束优化问题的一种直接法直接法，它不需求它不需求函数导数函数导数而直接搜索目标函数的最优解。而直接搜索目标函数

3、的最优解。该法又称该法又称降维法降维法。该法将一个该法将一个多维无约束优化问题多维无约束优化问题转化为转化为一系列一系列一维优化问题一维优化问题来求解，来求解，即依次沿着即依次沿着坐标轴的方向坐标轴的方向进行进行一维搜索一维搜索，求得，求得极小点极小点。当对当对 n 个变量个变量 x1, x2 , xn 依次进行过一次搜索之后，依次进行过一次搜索之后，即即完成一轮计算完成一轮计算。若未收敛到极小点，若未收敛到极小点，则又从则又从前一轮的最末点前一轮的最末点开始，再作开始，再作下一轮搜索下一轮搜索，如此继续下去，直至收敛到如此继续下去，直至收敛到最优点最优点为止。为止。坐标轮换法坐标轮换法，就是

4、由此而得名的。，就是由此而得名的。 现代设计方法最优化设计现以现以（图图1）为例，说明为例，说明该法的搜索过程该法的搜索过程。图图1 坐标轮换法搜索过程坐标轮换法搜索过程 现代设计方法最优化设计先以先以 为为初始点初始点， 沿着沿着坐标轴坐标轴 方向方向进行一维搜索，求得进行一维搜索，求得极小点极小点 ， 然后固定然后固定 不变，改沿着不变，改沿着坐标轴坐标轴 方向方向进行一维搜索，求得进行一维搜索，求得极小点极小点 ，至此完成了，至此完成了该二维问题该二维问题的的一轮计算一轮计算。由于未得到问题的最优点，需进行由于未得到问题的最优点，需进行第二论迭代第二论迭代，即从前一轮的最末点即从前一轮的

5、最末点 出发，重复前面的过程求得出发，重复前面的过程求得 点。点。如此继续下去，直到找到问题的如此继续下去，直到找到问题的 。 1X(0)X2X(1)1X(1)2X(2)(2)12XX、*12,TXXX(1)1X(1)2X现以现以二维优化问题二维优化问题（图图1）为例，说明为例，说明。根据上述原理，对于第根据上述原理，对于第k 轮计算，轮计算，为：为： ( )( )( )1(1,2,., )kkkiiiXXSin 现代设计方法最优化设计其中，其中，是轮流取是轮流取 的的：( )1 (1, 2, , )kiiSein( )kiS即即12100010, , , 000001neee 现代设计方法最

6、优化设计关于坐标轮换法的迭代步长关于坐标轮换法的迭代步长，常用如下，常用如下两种取法两种取法： 即在每一维，先选择一个即在每一维，先选择一个初始步长初始步长，若沿，若沿该维正向该维正向第一步第一步搜索搜索成功成功(即该点函数搜索时值下降即该点函数搜索时值下降)，则以，则以倍增的步长倍增的步长继续沿该维向前继续沿该维向前搜索，搜索，步长的序列步长的序列为为, 2, 4, 8, iiii坐标轮换法的特点坐标轮换法的特点： 计算简单，概念清楚；计算简单，概念清楚； 但搜索线路较长，计算效率低；但搜索线路较长，计算效率低； 所以它只能用于所以它只能用于低维低维（n10）优化问题优化问题的求解。的求解。

7、直到函数值出现上升时，则取直到函数值出现上升时，则取前一点前一点为为本维极小点本维极小点，然后改换为沿下，然后改换为沿下一维方向进行搜索，依次循环继续前进，直至到达一维方向进行搜索，依次循环继续前进，直至到达收敛精度收敛精度为止。为止。 现代设计方法最优化设计求最优步长求最优步长 举例举例：*1. 最优步长的几何意义最优步长的几何意义 已知：已知：以以二维优化问题二维优化问题为例，为例，最优步长最优步长 的几何意义的几何意义如如右图右图所示。所示。2. 最优步长的计算最优步长的计算22( )( )1211211()242, 10kkf Xxxxx xXS 以及点和图图2-a 最优步长的几何意义

8、最优步长的几何意义 现代设计方法最优化设计*(1)221211222221()242 1 (1)2 14(1)2(1) 1 (1)6(1)2 43kf Xfxxxx x 求：求：在在给定点给定点处沿处沿给定方向给定方向搜索的搜索的最优步长最优步长 。( )kX( )kS解：解： 根据根据基本迭代公式基本迭代公式，有，有(1)( )( )( )111 10 1kkkkXXS 则则由上可见，原本由上可见，原本 函数函数这时成为这时成为 的函数的函数，即，即 。 ()f X ( )f 现代设计方法最优化设计*422为求得为求得最优步长最优步长，可令可令( )0dfd2( )(43) 240dfddd

9、即即故得故得最优步长最优步长： 现代设计方法最优化设计14.2 鲍威尔法鲍威尔法 在上述在上述中，之所以收敛很慢，中，之所以收敛很慢，其其其其搜索方向搜索方向总是平行于坐标轴，不适应函数的变总是平行于坐标轴，不适应函数的变化情况。化情况。（powell 法法，又称，又称共轭方向法共轭方向法）:是鲍威尔于是鲍威尔于1964年提出的，它是在年提出的，它是在坐标轮换法坐标轮换法的基础上，的基础上，通过构造通过构造共轭方向共轭方向，以达到快速收敛的目的。并通过改进后，是一种，以达到快速收敛的目的。并通过改进后，是一种比较有效的算法比较有效的算法。 现代设计方法最优化设计如如图图3所所示：若把示：若把上

10、一轮的搜索末点上一轮的搜索末点 （即这一轮搜索的起（即这一轮搜索的起点点 ）和）和本轮搜索的末点本轮搜索的末点 连接起来，形成连接起来，形成一一新的搜索方向新的搜索方向( )2kX(1)0kX(1)2kX(2)(1)( )22kkSXX图图3 共轭方向共轭方向 并沿并沿此方向此方向进行一维搜索，则由进行一维搜索，则由此图此图可看到，它能极大地加快可看到，它能极大地加快收敛速收敛速度度，鲍威尔法鲍威尔法正是利用正是利用这种原理这种原理来构成来构成搜索方向搜索方向并进行并进行迭代迭代计算计算的。的。(1)0()kX 现代设计方法最优化设计采用采用坐标轮换法坐标轮换法进行进行第一轮迭代第一轮迭代。然

11、后然后以以第一轮迭代第一轮迭代的最末一个的最末一个极小点极小点和和初始点初始点，构成一个构成一个新的方向新的方向，并以此，并以此新的方向新的方向作为最末一个方向，作为最末一个方向，而去掉第一个方向，而去掉第一个方向，得到得到第二轮迭代第二轮迭代的的 n 个方向。个方向。仿此进行下去，直至求得问题的仿此进行下去，直至求得问题的极小点极小点。现以现以二二维优化问题维优化问题为例，来说明为例，来说明。1. 基本鲍威尔法基本鲍威尔法 现代设计方法最优化设计图图4 基本鲍威尔法的迭代过程基本鲍威尔法的迭代过程 取取初始点初始点作为迭代计算的作为迭代计算的出发点出发点，即令，即令，先沿先沿坐标轴坐标轴 的

12、方向的方向作作一维搜索一维搜索，求得此方向上的求得此方向上的极小点极小点 。 (1)(0)0XX(0)X1X(1)1X2X(1)111,0TSe)1(2X(1)220,1TSe作作一维搜索一维搜索，求得该方向上的求得该方向上的极小点极小点 。然后，再沿然后，再沿 坐标方向坐标方向的的，如如图图4所所示。示。 现代设计方法最优化设计然后利用然后利用两次搜索两次搜索得到的得到的极小点极小点 及及 构成一个构成一个新的迭代方新的迭代方向向 ，即，即(1)0X)1(2X(1)S(1)(1)(1)20SXX进行进行第二轮迭代第二轮迭代时，时， 去掉去掉第一个方向，将第一个方向，将方向方向 作为最末一个迭

13、代方向，作为最末一个迭代方向，即从即从 出发，出发，依次沿着依次沿着方向方向 及及(1)11Se)1(X(2)(1)122SSe)1(S(2)0X)2(2X(2)1X)2(S并沿并沿此方向此方向作一维搜索，得到该方向上作一维搜索，得到该方向上一维极小点一维极小点 ，至此完成，至此完成第第一轮搜索一轮搜索。(1)(2)0XX(2)(1)(1)(1)220SSXX(2)(2)(2)20SXX(2)2X并并沿此方向搜索沿此方向搜索得到得到 。 )2(X进行进行一维搜索一维搜索，得到，得到极小点极小点： 、 ；然后利用、然后利用、 构成构成另一个迭代方向另一个迭代方向 ，即，即 现代设计方法最优化设计

14、为形成为形成第三轮第三轮迭代的方向，迭代的方向，将将 加到加到第二轮方向组第二轮方向组之中，并去掉之中，并去掉第二轮第二轮迭代的第一个方向迭代的第一个方向 ，即令，即令 )2(S(2)12Se(3)(2)(1)12(3)(2)(2)(2)220SSSSSXX即即第三轮的迭代方向第三轮的迭代方向实际上是实际上是 和和 ，由于由于 是连接两个平行线的方向是连接两个平行线的方向 搜索得到的二极小点搜索得到的二极小点 、 所构成的，根据共轭方向的概念可知，所构成的，根据共轭方向的概念可知， 和和 是是互为共轭的方向互为共轭的方向。)2(S)2(S)1(S)1(S)2(2X)2(0X)1(S)2(S如果

15、所考察的如果所考察的二维函数二维函数是二次的，即对于是二次的，即对于二维二次函数二维二次函数， 经过沿经过沿共轭方向共轭方向 、 的两次一维搜索所得到的的两次一维搜索所得到的极小点极小点 就是该目标函数的就是该目标函数的极小点极小点 （即椭圆的中心）。（即椭圆的中心）。)2(S)1(S)2(X*X 现代设计方法最优化设计而对于而对于二维非二次函数二维非二次函数，这个，这个极小点极小点还不是还不是该函数该函数的的极小点极小点，需要继续按照上述方向进行进一步搜索。需要继续按照上述方向进行进一步搜索。 )2(X由上述可知，由上述可知，共轭方向共轭方向是在更替搜索方向反复作一维搜索中逐是在更替搜索方向

16、反复作一维搜索中逐步形成的。步形成的。对于对于二元函数二元函数，经过二轮搜索，就产生了，经过二轮搜索，就产生了两个两个互相共轭的方向互相共轭的方向。对于对于三元函数三元函数经过三轮搜索以后，就可以得到经过三轮搜索以后，就可以得到三个三个互相共轭的互相共轭的方向方向。 现代设计方法最优化设计而对于而对于n 元函数元函数，经过，经过n 轮搜索以后，一共可产生轮搜索以后，一共可产生 n 个互相共轭个互相共轭的方向的方向：(1)(2)( ), , , nSSS上述基本鲍威尔法的基本要求上述基本鲍威尔法的基本要求：各轮迭代中的各轮迭代中的应该是应该是线性无关的线性无关的。然而很不理想的是，然而很不理想的

17、是，上述方法每次迭代所产生的上述方法每次迭代所产生的新方向新方向可能出现可能出现线性相关线性相关，故使搜索运算故使搜索运算蜕化蜕化到一个较低维的空间进行，到一个较低维的空间进行，从而导致计算不能收敛而无法求得真正的从而导致计算不能收敛而无法求得真正的极小点极小点。为了提高沿共轭方向搜索的效果，为了提高沿共轭方向搜索的效果，针对针对上述算法上述算法提出了改进，提出了改进，则改进后的算法则改进后的算法 称为称为。 现代设计方法最优化设计2. 修正鲍威尔法修正鲍威尔法放弃了放弃了原算法原算法中不加分析地用中不加分析地用新形成的方向新形成的方向替换上一轮搜索方向组中的替换上一轮搜索方向组中的第一个方向

18、第一个方向的作法的作法 。)(kS)(kS该算法规定该算法规定：在在每一轮迭代每一轮迭代完成产生完成产生共轭方向共轭方向后，后，在组成新的方向组时不一律舍去上一轮的在组成新的方向组时不一律舍去上一轮的第一个方向第一个方向，而是先对而是先对的好坏的好坏进行判别进行判别，检验它是否与其他方向检验它是否与其他方向线性相关线性相关或接近或接近线性相关线性相关。)(1kS若若共轭方向不好共轭方向不好，则不用它作为下一轮的迭代方向，则不用它作为下一轮的迭代方向，而仍采用而仍采用原来的一组迭代方向原来的一组迭代方向；若若共轭方向好共轭方向好，则可用它则可用它替换替换前轮迭代中使目标函数值下降最多的一个方向，

19、前轮迭代中使目标函数值下降最多的一个方向，而不一定是而不一定是替换替换第一个迭代方向。第一个迭代方向。这样得到的这样得到的方向组方向组，其，其收敛性收敛性更好。更好。 现代设计方法最优化设计31( )2( )212312131(2)()()2kkmmFFFFFFFFF)(kS)(kS)(kmS对于是否用新的方向来对于是否用新的方向来替换替换原方向组的某一方向原方向组的某一方向的的判别条件判别条件为：为：在第在第 k 轮搜索中，轮搜索中，若若同时成立同时成立，则表明，则表明 与原方向组线性无关，因此可将新方向与原方向组线性无关，因此可将新方向 作为下一轮的迭代方向，并作为下一轮的迭代方向，并去掉

20、方向去掉方向 而构成而构成第第k+1轮迭代的轮迭代的搜索方向组；搜索方向组；否则否则，仍用，仍用原来的方向组原来的方向组进行进行第第k+1轮轮迭代。迭代。 上式中上式中： 为第为第 k 轮起始点函数值；轮起始点函数值； 为第为第 k 轮方向组一维搜索终点函数值；轮方向组一维搜索终点函数值； ( )10()kFf X( )2()knFf X( )( )30(2)kknFfXX)(0kX)( km)(knX)(kmS 为对的映射点函数值；为对的映射点函数值； 为第为第 k 轮方向组中沿诸方向一维搜索所得的轮方向组中沿诸方向一维搜索所得的各各函函数值下降量数值下降量中之中之最大者最大者，其，其相对应

21、的方向相对应的方向记为记为 。(1) 现代设计方法最优化设计上式中上式中各符号意义各符号意义，如，如图图5所所示。示。图图5 修正鲍威尔法的方向淘汰修正鲍威尔法的方向淘汰 实践证明，上述实践证明，上述保证了非线性函数寻优计算可靠保证了非线性函数寻优计算可靠的收敛性。的收敛性。 现代设计方法最优化设计如下：如下： (1)给定给定初始点初始点 X(o) 和收敛精度和收敛精度； (2)取取 n 个坐标轴的个坐标轴的单位向量单位向量 ei ( i =1, ,2, , ,n )为初始搜索方向为初始搜索方向Si(k) = ei ，置，置 k=1 ( k为迭代轮数为迭代轮数) ； (3)从出发，依次沿从出发

22、，依次沿 进行进行 n 次一维搜索，次一维搜索，得到得到 n 个一维极小点个一维极小点)(0kX( )(1,2, )kiSin( )( )( )( )1 (1,2, )kkkkiiiiXXSin(4)连接、连接、 ，构成新的，构成新的共轭方向共轭方向 ，即，即( )( )( )0kkknSXX)(0kX)(knX)(kS沿沿共轭方向共轭方向 计算计算 的的映射点映射点( )( )( )102kkknnXXX)(kS)(0kX 现代设计方法最优化设计( )( )( )11 m n( )( )( )1= ()() (1,2, )maxkkkmiikkkmmmf Xf XinSXX(5)计算第计算第k 轮中各轮中各相邻极小点相邻极小点目标函数的差值目标函数的差值，并找出其中的，并找出其中的最最大差值大差值及其及其相应的方向相应的方