现代设计方法课件第4节

1本章主要内容优化设计概述优化问题的数学分析基础一维探索优化方法无约束多维问题的优化方法约束问题的优化方法Matlab在优化设计中的应用2优化问题一维优化问题（1个设计变量）多维优化问题（多个设计变量）无约束多维问题单目标函数的优化问题多目标函数的优化问题有约束多维问题3第四节常用的无约束优化方法4.1坐标轮换法4.2鲍威尔(Powell)法4.3梯度法4.4牛顿法4.5DFP变尺度法无约束优化方法的评价准则及选用4任何一次迭代，都是求使得即其中：表示步长因子(k)表示最优步长因子)()()()1(kkkkSXX)(min)()()()1(kkkSXfXf)(min)()()()()()(kkkkkSXfSXf5概述(1)()()()kkkkX=X+S基本迭代公式:?无约束优化问题12min...TnnFXXxxxR内容:讨论几个常用无约束优化方法的基本思想、方法构成、迭代步骤以及终止准则等方面问题。无约束优化方法直接法：坐标轮换法、鲍威尔(Powell)法间接法：梯度法、牛顿法、变尺度法直接搜索法：只需进行函数值的计算与比较来确定迭代方向和步长间接法：利用函数的一阶或二阶偏导数矩阵来确定迭代方向和步长64.1坐标轮换法2xo1x*X迭代方向S取为一系列坐标轴方向，通常都用单位坐标矢量ei作为这种迭代的方向矢量，则坐标轮换法所取的迭代方向就依次为:,1,2,...,iein12100...0010...0............000...1TTTneee(0)X(1)0X(1)1X(1)2X(2)0X(2)1X(2)2X(3)0X第一轮:任取一初始点X(0)(0)X(1)0X1210,01TTee(1)(1)(1)1011XXe(1)1一维搜索求得(1)1X(1)(1)(1)2122XXe(1)2一维搜索求得(1)2X第二轮:(1)(2)20XX(2)(2)(2)1011XXe(2)(2)(2)2122XXe7迭代步长α的确定①最优步长利用一维优化方法确定沿该方向上具有最小目标函数值的步长，即:min{F(X(k)+α(k)S(k))}=min{F(X(k)+α(k)S(k))}②加速步长先选择一个不大的初始步长α0，在每次一维搜索中都是先沿正向从α←α0开始作试探计算函数值，若函数值下降，则以倍增的速度加大步长，步长序列为α0、2α0、4α0、8α0、…直到函数值保持下降的最后一个步长为止。若试探时函数值已增大，则改沿反向，即取α←-α0后再加速步长。8终止准则:()()0kknXX*()knXX2xo1x*X(0)X(1)0X(1)1X(1)2X(2)0X(2)1X(2)2X(3)0X9坐标轮换法的特点具有程序结构简单，易于掌握等优点。但是计算效率比较低，这一缺点当优化问题的维数较高时更为突出。一般认为，此方法应用于n10的低维优化问题比较适宜收敛速度与等值线的形状有关10不同性质目标函数坐标轮换法的求优效能x1x2X(1)X*X(0)0x1x2X*X(0)X(1)X(2)X(3)X(4)0X(0)0x1x2X*X(1)收敛速度很快收敛速度很慢求优失效等值线为椭圆,长、短轴与x1,x2轴平行等值线为椭圆,长、短轴与x1,x2轴不平行114.2鲍威尔（Powell）法124.2.1鲍威尔(Powell)法的基本思想鲍威尔法是直接搜索法中一个十分有效的算法。该算法是沿着逐步产生的共轭方向进行搜索的，因此本质上是一种共轭方向法，鲍威尔法的收敛速率较快。以共轭方向作为搜索方向，不只限于鲍威尔法，也用于其他一些较为有效的方法，可以统称为共轭方向法。因此，共轭方向的概念在优化方法研究中占有重要的地位。共轭方向在最优化问题中的应用是基于其具有一个重要性质，即：设S1、S2、…、Sn是关于A的n个互相共轭的向量，则对于求正定二次函数的极小点，从任意初始点出发，依次沿Sii=1，2，…，n)方向进行一维最优化搜索，至多n步便可以收敛到极小点．1()2TTFXcbXXAX132.4.2共轭方向一、共轭方向的基本概念若有两个n维矢量S1、S2，对n×n阶对称正定矩阵A能满足:T12SAS=0称n维空间矢量S1与S2对A共轭共轭矢量所代表的方向称为共轭方向。正交，可以看作是共轭的特例共轭，可以看作是正交的推广121200TTSSSES例:(1)122111,,1211ASS12211110,121TSAS1211101TSS共轭并正交142.5关于优化方法中搜寻方向的理论基础2.5.2共轭方向例:(2)122111,,1202ASS12211100,122TSAS12110102TSS共轭但不正交122110,,1201ASS12210101,121TSAS1201001TSS正交但不共轭例:(3)15设A为n×n阶实对称正定矩阵，有一组非零的n维矢量S1、S2、…、Sq，若满足i≠j则称矢量系Si(i＝1，2，…，q≤n)对于矩阵A共轭0jTiASS16一、共轭方向的基本概念二元二次函数2212112212()(,)abFXFxxxxcdxxxexf1()2TTFXXXCXABH22abAbc海赛矩阵正定有极小点F(X)的等值线是同心椭圆簇几何特性:两条平行的任意方向的切线,其切点的连线必通过椭圆簇的中心。1xo2x*X2X1X1S1S2S17一、共轭方向的基本概念1()FX2()FX1xo2x*X2X1X1S1S2S1()2TTFXXXCXABS1与S2是对A共轭的一对矢量证明：(2)(1)2SXX(1)(1)()FXAXB(2)(2)()FXAXB(2)(1)(2)(1)()()()FXFXAXX2AS梯度1(1)(2)1()0,()0TTSFXSFX而1(2)(1)()()0TSFXFX即：120TSAS结论:两个平行方向的极小点构成的新方向与原方向相互共轭对于二维正定二次函数只要分别沿两个共轭方向寻优即可找到最优点.18与此类似，可以推出对于n维正定二次函数共轭方向的一个十分重要的极为有用的性质：从任意初始点出发，依次沿n个线性无关的与A共轭的方向S1，S2，…Sn各进行一维搜索，那么总能在第n步或n步之前就能达到n维正定二次函数的极小点；并且这个性质与所有的n个方向的次序无关。简言之，用共轭方向法对于二次函数从理论上来讲，n步就可达到极小点。因而说共轭方向法具有有限步收敛的特性。通常称具有这种性质的算法为二次收敛算法。19二、共轭矢量的几个性质共轭矢量之所以引起优化研究者的重视，是因为它的某些性质对提高优化方法的收敛速率极为有用。(1)矢量S1与S2正交关系，是矢量S1与S2对A共轭的特殊情形。在n维设计空间里，单位坐标矢量系：e1，e2，…，en为正交矢量系。(2)若矢量系S1、S2、…、Sn，对于对称正定矩阵A共轭，则它必为线性独立(线性无关)矢量系。对于n维设计空间而言，线性独立矢量系中的矢量个数不能超过维数n，即共轭矢量系中矢量个数最多等于n(证明略)。(3)关于二次收敛性问题1xo2x*X2X1X1S1S2S对于一般的n元二次正定函数F(x)，依次按共轭矢量系(S1，S2，…，Sn)中各矢量方向进行n次一维搜索，就可达到等值线(椭圆)中心——理论极小点。二次收敛性是指一种算法，如果对于二次正定函数，从理论上只要进行有限次一维搜索，就可达到理论极小点，把这种算法称为具有二阶收敛性(二次收敛性)或有限步收敛性。20例2.1221212()2FXxxxx(0)122X设二维目标函数，给定方向S1＝e2，初始点，求与S1相共轭的S2，并求函数的极小点。解：(1)第一个搜索方向101S(2)函数的海赛矩阵对称正定4112H(3)从(0)1X点沿S1方向求极小点，即1X21例2.1解：(4)任取初始点(0)211X沿S1方向一维搜索求得该方向极小点(2)10.5X(5)求与S1相共轭的方向S2S2=X(2)-X(1)=5.01核验计算矢量S1与S2确为对A矩阵共轭。(6)从X(1)点出发，沿S2方向作一维搜索，得极小点X*=[00]T221212()2FXxxxx2X224.2.1鲍威尔基本算法234.2.1鲍威尔基本算法2x1xo3x(0)X(1)0X(1)1X(1)2X(1)3X(1)X1S(2)0X(2)1X(2)2X(2)3X(2)X2S(3)0X(3)1X(3)3X(3)2X(3)X3S任取一初始点X(0)→X0(1)第一环:e1,e2,e3→S1第二环:e2,e3,S1→S2第三环:e3,S1,S2→S3第一轮S1,S2,S3两两共轭结论:两个平行方向的极小点构成的新方向与原方向相互共轭(1)1301()XXS(2)2302()XXS(3)3303()XXS244.2.1鲍威尔基本算法2x1xo3x(0)X(1)0X(1)1X(1)2X(1)3X(1)X1S(2)0X(2)1X(2)2X(2)3X(2)X2S(3)0X(3)1X(3)3X(3)2X(3)X3S第一环:e1,e2,e3→S1第二环:e2,e3,S1→S2第三环:e3,S1,S2→S3第一轮1123231eeSeS1是e1,e2,e3的线性组合S2是e2,e3,S1的线性组合S3是e3,S1,S2的线性组合1x3x2xo1033e1S2233ee新一环方向组:e2,e3,S1线性相关!降维22e25鲍威尔法的基本思想:对原始共轭方向法进行修正,即在某环已取得的n+1个方向中,选取n个线性无关,共轭程度尽可能高的方向作为下一环的基本方向组,从而避免出现“退化”现象.鲍威尔法与原始共轭方向法的主要区别是：在构成K+1环基本方向组时，不再总是淘汰前一环(K环)中的第一个方向，而是根据条件式是否得到满足分两种情况来处理。31221231213?(2)()()2FFFFFFFFF4.2.1鲍威尔修正算法264.2.1鲍威尔修正算法第K环方向组:鲍威尔基本算法()()()()121,,......,kkkknnSSSS第K+1环方向组:(1)(1)(1)(1)121,,......kkkknnSSSS()()()23()1,,......,knkkknSSSS新方向()1knS一、Powell修正算法的搜索方向Powell修正算法的基本方向组构成是从下面原则出发的：在某环已取得的n+1个方向中，选取n个线性无关的并且共轭程度尽可能高的方向作为下一环的基本方向组，从而避免出现“退化”现象。274.2.1鲍威尔修正算法()0kX()1kX()2kX()1kmX()kmX()knX()kX()1knX()1kS()2kS()kmS()knS()1knS映射点1()F2()F3()F()kS一、Powell修正算法的搜索方向()()()10231(),(),()kkknnFFXFFXFFX()()1max()(),1,2,...,kkiiFXFXin()()1()()kkmmFXFX()()()()()()()10102kkkkkkknnnnnXXXXXXX31221231213?(2)()()2FFFFFFFFF