现代设计方法课件第4节.

1、1第三章第三章 优化设计优化设计Optimization Design2本章主要内容本章主要内容 优化设计概述优化设计概述 优化问题的数学分析基础优化问题的数学分析基础 一维探索优化方法一维探索优化方法 无约束多维问题的优化方法无约束多维问题的优化方法 约束问题的优化方法约束问题的优化方法 Matlab在优化设计中的应用在优化设计中的应用3优化问题优化问题一维优化问题一维优化问题（1个设计变量）个设计变量）多维优化问题多维优化问题（多个设计变量）（多个设计变量）无约束多维问题无约束多维问题单目标函数的优化问题单目标函数的优化问题多目标函数的优化问题多目标函数的优化问题有约束多维问题有约束多维问

2、题4 4.1 坐标轮换法坐标轮换法 4.2 鲍威尔鲍威尔(Powell)法法4.3 梯度法梯度法4.4 牛顿法牛顿法4.5 DFP变尺度法变尺度法v无约束优化方法的评价准则及选无约束优化方法的评价准则及选用用5任何一次迭代，都是求任何一次迭代，都是求使得使得即即其中：其中： 表示步长因子表示步长因子 (k)表示最优步长因子表示最优步长因子)()()()1(kkkkSXX)(min)()()()1(kkkSXfXf)(min)()()()()()(kkkkkSXfSXf6概述概述(1)( )( )( )kkkkX= X+S基本迭代公式基本迭代公式:?无约束优化问题无约束优化问题12min.Tnn

3、F XXxxxR内容内容: :讨论几个常用无约束优化方讨论几个常用无约束优化方法的基本思想、方法构成、法的基本思想、方法构成、迭代步骤以及终止准则等方迭代步骤以及终止准则等方面问题。面问题。 直接搜索法：只需进行函数值的计算与比较来确定迭代方向和步长直接搜索法：只需进行函数值的计算与比较来确定迭代方向和步长间接法：利用函数的一阶或二阶偏导数矩阵来确定间接法：利用函数的一阶或二阶偏导数矩阵来确定迭代方向和步长迭代方向和步长74.1 4.1 坐标轮换法坐标轮换法2xo1x*X迭代方向迭代方向S取为一系列坐标轴方向，取为一系列坐标轴方向，通常都用单位坐标矢量通常都用单位坐标矢量ei作为这种迭作为这种

4、迭代的方向矢量，则坐标轮换法所取代的方向矢量，则坐标轮换法所取的迭代方向就依次为的迭代方向就依次为:,1,2,.,iein121 0 0 . 00 1 0 . 0. .0 0 0 . 1TTTneee(0)X(1)0X(1)1X(1)2X(2)0X(2)1X(2)2X(3)0X第一轮第一轮: 任取一初始点任取一初始点X(0) (0)X(1)0X121 0 ,0 1TTee(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)

5、(2)2122XXe8迭代步长迭代步长的确定的确定最优步长最优步长利用一维优化方法确定沿该方向上具有最小目标函数值的步长，即: minF(X(k)+(k)S(k)=minF(X(k)+(k)S(k)加速步长加速步长先选择一个不大的初始步长0，在每次一维搜索中都是先沿正向从0开始作试探计算函数值，若函数值下降，则以倍增的速度加大步长，步长序列为0 0、20 0、40 0、80 0、直到函数值保持下降的最后一个步长为止。若试探时函数值已增大，则改沿反向，即取-0后再加速步长。9终止准则终止准则: :( )( )0kknXX*( )knXX2xo1x*X(0)X(1)0X(1)1X(1)2X(2)0

6、X(2)1X(2)2X(3)0X10坐标轮换法的特点坐标轮换法的特点v具有程序结构简单，易于掌握等优点。但是计算效率比较低，这一缺点当优化问题的维数较高时更为突出。v一般认为，此方法应用于n10的低维优化问题比较适宜v收敛速度与等值线的形状有关收敛速度与等值线的形状有关11不同性质目标函数坐标轮换法的求优效能不同性质目标函数坐标轮换法的求优效能x1x2X(1)X*X(0)0 x1x2X*X(0)X(1)X(2)X(3)X(4)0X(0)0 x1x2X*X(1)收敛速度很快收敛速度很快收敛速度很慢收敛速度很慢求优失效求优失效等值线为椭圆等值线为椭圆,长、短轴与长、短轴与x1,x2轴平行轴平行等值

7、线为椭圆等值线为椭圆,长、短轴与长、短轴与x1,x2轴不平行轴不平行124.2 鲍威尔（鲍威尔（Powell）法）法 134.2.1 鲍威尔鲍威尔(Powell)法的基本思想法的基本思想v鲍威尔法是直接搜索法中一个十分有效的算法。该算法是沿着鲍威尔法是直接搜索法中一个十分有效的算法。该算法是沿着逐步产生的逐步产生的共轭方向共轭方向进行搜索的，因此进行搜索的，因此本质上是一种本质上是一种共轭方向共轭方向法，法，鲍威尔法的收敛速率较快。鲍威尔法的收敛速率较快。v以共轭方向作为搜索方向，不只限于鲍威尔法，也用于其他一以共轭方向作为搜索方向，不只限于鲍威尔法，也用于其他一些较为有效的方法，可以统称为些

8、较为有效的方法，可以统称为共轭方向法共轭方向法。因此，共轭方向。因此，共轭方向的概念在优化方法研究中占有重要的地位。的概念在优化方法研究中占有重要的地位。v共轭方向在最优化问题中的应用是基于其具有一个共轭方向在最优化问题中的应用是基于其具有一个重要性质重要性质，即：设即：设 S S1 1、S S2 2、S Sn n是关于是关于A A的的n n个互相共轭的向量，则对于个互相共轭的向量，则对于求正定二次函数求正定二次函数 的极小点，从任意初始的极小点，从任意初始点出发，依次沿点出发，依次沿S Si i i=1 i=1，2 2，n)n)方向进行一维最优化搜索，方向进行一维最优化搜索，至多至多n n步

9、便可以收敛到极小点步便可以收敛到极小点1()2TTF Xcb XX AX142.4.2 共轭方向共轭方向一、共轭方向的基本概念一、共轭方向的基本概念若有两个n维矢量S1、S2，对nn阶对称正定矩阵A能满足:T12S AS = 0称n维空间矢量S1与S2对A共轭共轭矢量所代表的方向称为共轭方向。正交，可以看作是共轭的特例共轭，可以看作是正交的推广121200TTS SS ES例:(1)122111,1211ASS 122111 10,121TS AS1211 101TS S共轭并正交共轭并正交152.5 关于优化方法中搜寻方向的理论基础关于优化方法中搜寻方向的理论基础2.5.2 共轭方向共轭方向

10、例:(2)122111,1202ASS 12211100,122TS AS12110102TS S 共轭但不正交共轭但不正交122110,1201ASS 12210101,121 TS AS1201001 TS S正交但不共轭正交但不共轭例:(3)16设设A A为为n nn n阶实对称正定矩阵，有一组非零的阶实对称正定矩阵，有一组非零的n n维矢量维矢量S S1 1、S S2 2、SqSq，若满足，若满足 ijij 则称矢量系则称矢量系S Si i(i(i1 1，2 2，qnqn) )对于矩阵对于矩阵A A共轭共轭 0jTiASS17一、共轭方向的基本概念一、共轭方向的基本概念二元二次函数二元

11、二次函数 2212112212()(,)abF XF x xxxcdxxxexf1()2TTF XXXCXABH 22abAbc海赛矩阵正定有极小点F(X)的等值线是同心椭圆簇的等值线是同心椭圆簇几何特性几何特性:两条平行的任意方向的切线两条平行的任意方向的切线,其切点的连线必通过椭圆簇其切点的连线必通过椭圆簇的中心。的中心。1xo2x*X2X1X1S1S2S18一、共轭方向的基本概念一、共轭方向的基本概念1()F X2()F X1xo2x*X2X1X1S1S2S1()2TTF XXXCXABS1与与S2是对是对A共轭的一对矢量共轭的一对矢量证明：证明：(2)(1)2SXX(1)(1)()F

12、XAXB(2)(2)()F XAXB(2)(1)(2)(1)()()()F XF XA XX2AS梯度梯度1(1)(2)1()0,()0TTSF XSF X而而1(2)(1)()()0TSF XF X 即：即：120TSA S结论结论:两个平行方向的极小点构成两个平行方向的极小点构成的新方向与原方向相互共轭的新方向与原方向相互共轭对于对于二维正定二次函数只要分别沿两个共轭方向寻优即可二维正定二次函数只要分别沿两个共轭方向寻优即可找到最优点找到最优点.19v与此类似，可以推出对于与此类似，可以推出对于n n维正定二次函数共轭方维正定二次函数共轭方向的一个十分重要的极为有用的性质：从任意初始向的一

13、个十分重要的极为有用的性质：从任意初始点出发，依次沿点出发，依次沿n n个线性无关的与个线性无关的与A A共轭的方向共轭的方向S1S1，S2S2，SnSn各进行一维搜索，那么总能在第各进行一维搜索，那么总能在第n n步或步或n n步步之前就能达到之前就能达到n n维正定二次函数的极小点；并且这维正定二次函数的极小点；并且这个性质与所有的个性质与所有的n n个方向的次序无关。简言之，用个方向的次序无关。简言之，用共轭方向法对于二次函数从理论上来讲，共轭方向法对于二次函数从理论上来讲，n n步就可步就可达到极小点。因而说共轭方向法具有有限步收敛的达到极小点。因而说共轭方向法具有有限步收敛的特性。通

14、常称具有这种性质的算法为特性。通常称具有这种性质的算法为二次收敛算法。二次收敛算法。20二、共轭矢量的几个性质二、共轭矢量的几个性质 共轭矢量之所以引起优化研究者的重视，是因为它的某些性质对提高优化方法的收敛速率极为有用。(1) 矢量S1与S2正交关系，是矢量S1与S2对A共轭的特殊情形。在n维设计空间里，单位坐标矢量系：e1，e2，en为正交矢量系。 (2) 若矢量系S1、S2、Sn，对于对称正定矩阵A共轭，则它必为线性独立(线性无关)矢量系。对于n维设计空间而言，线性独立矢量系中的矢量个数不能超过维数n，即共轭矢量系中矢量个数最多等于n(证明略)。 (3) 关于二次收敛性二次收敛性问题 1

15、xo2x*X2X1X1S1S2S对于一般的n元二次正定函数F(x)，依次按共轭矢量系(S1，S2，Sn)中各矢量方向进行n次一维搜索，就可达到等值线(椭圆)中心理论极小点。二次收敛性二次收敛性是指一种算法，如果对于二次正定函数，从理论上只要进行有限次一维搜索，就可达到理论极小点，把这种算法称为具有二阶收敛性(二次收敛性)或有限步收敛性。21例例2.122121 2( )2F Xxxxx(0)122X 设二维目标函数，给定方向S1e2，初始点，求与S1相共轭的S2，并求函数的极小点。解：(1) 第一个搜索方向101S (2) 函数的海赛矩阵 对称正定 4112H(3) 从(0)1X点沿S1方向求

16、极小点 ，即 1X22例例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*=0 0T 221212()2F Xxxx x2X234.2.1 鲍威尔基本算法鲍威尔基本算法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)

17、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 254.2.1 鲍威尔基本算法鲍威尔基本算法2x1xo3x(0)X(1)0X(1)1X(1)2X(1)3X(1)X1S(2)0X(2)1X(2)2X(2)3X(2

18、)X2S(3)0X(3)1X(3)3X(3)2X(3)X3S第一环第一环: e1, e2, e3 S1第二环第二环: e2, e3 , S1 S2第三环第三环: e3 , S1 , S2 S3第第一一轮轮1123231eeSeS1是是e1, e2, e3 的线性组合的线性组合S2是是e2, e3 , S1的线性组合的线性组合S3是是e3 , S1 , S2的线性组合的线性组合1x3x2xo1033e1S223 3ee新一环方向组新一环方向组: e2, e3 , S1 线性相关线性相关! 降维降维22e26鲍威尔法的基本思想鲍威尔法的基本思想: : 对原始共轭方向法进行修正对原始共轭方向法进行修

19、正, ,即在某即在某环已取得的环已取得的n+1n+1个方向中个方向中, ,选取选取n n 个线性无关个线性无关, ,共轭程度尽可能共轭程度尽可能高的方向作为下一环的基本高的方向作为下一环的基本方向组方向组, ,从而避免出现从而避免出现“退化退化”现现象象. .鲍威尔法与原始共轭方向法的主要区别是：鲍威尔法与原始共轭方向法的主要区别是：在构成在构成K+1K+1环基本方向组时，不再总是淘汰前一环环基本方向组时，不再总是淘汰前一环(K(K环环) )中的第中的第一个方向，而是根据条件式一个方向，而是根据条件式是否得到满足分两种情况来处理。是否得到满足分两种情况来处理。31221231213?(2)()

20、()2FFFFFFFFF 4.2.1 鲍威尔修正算法鲍威尔修正算法274.2.1 鲍威尔修正算法鲍威尔修正算法第第K环方向组环方向组:鲍威尔基本算法鲍威尔基本算法( )( )( )( )121,.,kkkknnSSSS第第K+1环方向组环方向组:(1)(1)(1)(1)121,.kkkknnSSSS( )( )( )23( )1,.,knkkknSSSS新方向新方向( )1knS一、一、Powell 修正算法的搜索方向修正算法的搜索方向 Powell 修正算法修正算法的基本方向组构成是从下面原则出发的： 在某环已取得的n+1个方向中，选取n个线性无关的并且共轭程度尽可能高的方向作为下一环的基本

21、方向组，从而避免出现“退化”现象。 284.2.1 鲍威尔修正算法鲍威尔修正算法( )0kX( )1kX( )2kX( )1kmX( )kmX( )knX( )kX( )1knX( )1kS( )2kS( )kmS( )knS( )1knS映射点1()F2()F3()F( )kS一、一、Powell 修正算法的搜索方向修正算法的搜索方向 ( )( )( )10231(),(),()kkknnFF XFF XFF X( )( )1max()() ,1,2,.,kkiiF XF Xin ( )( )1()()kkmmF XF X ( )( )( )( )( )( )( )10102kkkkkkkn

22、nnnnXXXXXXX31221231213?(2)()()2FFFFFFFFF Powell 判别式判别式294.2.1 鲍威尔修正算法鲍威尔修正算法一、一、Powell 修正算法的搜索方向修正算法的搜索方向 第第K环方向组环方向组:( )( )( )( )121,.,kkkknnSSSS(1)第第K+1环方向组环方向组:(1)(1)(1)(1)121,.?kkkknnSSSS新方向新方向( )1knS(2)第第K+1环初始点环初始点:(1)0?kX情况一：情况一： Powell 判别式判别式中若至少中若至少 有一个不等式成立，则有一个不等式成立，则第第K+1环的方向组环的方向组仍用仍用老方

23、向组老方向组 (1)(1)(1)(1)121,.kkkknnSSSS( )( )( )( )121,.,kkkknnSSSS初始点初始点:(1)( )0knkXX当当F2 F3时时,当当F2F3时时,(10( )1)kknXX情况二：情况二： Powell 判别式判别式中若两个中若两个 不等式均不成立，则不等式均不成立，则第第K+1环的方向组环的方向组(1)(1)(1)(1)121,.kkkknnSSSS初始点初始点:(1)( )0kkXX( )( )12( )1)1( )1,.,.,kknmmkkkknSSSSSS30 以二维为例以二维为例:两条件式至少有一成立且两条件式至少有一成立且F2F

24、3 31两条件式均不成立且两条件式均不成立且m=1 两条件式均不成立且两条件式均不成立且m=2 324.2.1 鲍威尔修正算法鲍威尔修正算法一、一、Powell 修正算法的搜索方向修正算法的搜索方向 终止准则终止准则: :采用了上述产生基本方向组的新方式后，除了第一环以单位坐标矢量系为基本方向组外，以后每以后每轮开始就不必重置单位坐标矢量轮开始就不必重置单位坐标矢量系，只要一环接一环继续进行即系，只要一环接一环继续进行即可。可。随着逐环迭代的继续，各环的基本方向组将渐趋共轭。因此，这个修正了的鲍威尔算法，虽然已不再像基本算法那样具有二次收敛的性质，但修正算法确实克服了退化的不利情形，同时仍能够

25、有效地、越来越快地收敛于无约束最优点x*。 ( )( )0kkXX二、修正算法的迭代步骤及流程图二、修正算法的迭代步骤及流程图( )0kX( )1kX( )2kX( )1kmX( )kmX( )knX( )kX( )1knX( )1kS( )2kS( )kmS( )knS( )1knS映射点1()F2()F3()F( )kS33试用鲍尔修正算法求目标函数 的最优解。迭代精度=0.001。 2212112()242F Xxxxx x已知初始点01 1,TX 解：解：第一环迭代计算第一环迭代计算 沿第一坐标方向e1进行一维搜索沿第二坐标轴方向e2进行一维搜索 (1)(1)0101,()31XFF

26、X (1)2011min()432F Xe (1)(1)101 1(1)11132101()7XXeF X (1)2122min()2270.5F Xe(1)(1)212 2(1)23030.5111.5()7.5XXeF X 构成新方向：(1)(1)1203121.510.5SXX 34沿s1方向一维搜索得极小点与极小值 需进行第二环迭代计算。第二环迭代计算：第二环迭代计算：首先确定上环中的最大函数下降量及其相应方向 映射点及其函数值(1)(1)195,()7.91710XF X 计算点距22( )( )01917112.886510kkXX(1)(1)01121(1)(1)(1)2121(

27、)4max,4()0.5mF XXF XXSe (1)(1)(1)120(1)31315221.512()7nnXXXFF X 35检验鲍尔条件鲍威尔条件两式均不成立。第二环取基本方向组和起始点为沿e2方向作一维搜索得沿S1方向一维搜索得 构成新生方向沿S2方向一维搜索得212312213(2)()1.25()322FFFFFFF31221231213(2)()()2FFFFFFFFF(2)21(2)(1)(2)010(,),()7.9iSe SXXFF X (2)(2)11195()7.981910XF X (2)(2)229925()7.9969750XF X (2)(2)22099194

28、25525971712501050SXX(2)(2)4,()82XF X 去掉函数值下降最大的方向去掉函数值下降最大的方向, ,补上新增的方向补上新增的方向初始点取新增方向的极小点初始点取新增方向的极小点36检查迭代终止条件需再作第三环迭代计算。根据具体情况来分析，S1、S2实际上为共轭方向的（见图4.9）。本题又是二次函数，按共轭方向的二次收敛性质，上面的结果就是问题的最优解。可以预料，如果作第三环迭代，则一定各一维搜索的步长为零，必有故得最优解22(2)(2)01917420.360510XX(3)(3)200XX*4,82XF 37122120( )04 242xxF Xxx 解解: :

29、令令*42X *1 11 22 12 22()2424x xx xx xx xFFH XFF正定正定 用解析法验证用解析法验证 221211 2( )242F Xxxxxx得得: :38?迭代过程、算法框图和迭代过程、算法框图和m文件文件 开始开始输入输入 ,0X k1 i1 kiX1 0X 沿着坐标轴方向计算最优步长沿着坐标轴方向计算最优步长 )eX( fmin)eX( fiik1iikik1ikiXikikieX 1i=n？ii+1,01kknknXXd kknknXXX012 ),X(ffk01)X( ffkn2)X( ffk1n3),X(f)X(f)X(f)X(f maxkmk1mki

30、k1inilmkmkmkmXXd1 Powell条件满足条件满足?32FF )dX(fmin)dX(fk1n1nknk1nk1nkn;110knkXX kikidd 1);(mi kikidd11 )(nim knknknkndXX111 knkXX110 knkXX 10kikidd 1 kknXX0100 kXX1 kk输出输出10* kXX)()(10* kXfXf结束结束ynnyyn?ny?39鲍威尔法的特点鲍威尔法的特点: : 是到目前为止求解无约束优化问题的最有效是到目前为止求解无约束优化问题的最有效的方法。不需求导数的方法。不需求导数, ,只需计算目标函数值。适只需计算目标函数值

31、。适用中、小型问题。用中、小型问题。404.3 梯度法梯度法(1)( )( )( )kkkkX= X+S( )( )( )()kkkSF Xg (1)( )( )( )kkkkX= Xg( )(1)( )( )( )kkkkkgX= Xg或或(1)kX(1)kX( )kX( )kS(1)kS(2)kX*X终止准则终止准则: :( )kg优点：优点：程序结构简单，每次迭代所需的计算量及储存量也小，而且当迭代点离最优点较远时函数值下降速度很快。缺点：缺点：但是这种方法在迭代点到达最优点附近时，进展十分缓慢，而且常常由于一维搜索的步长误差而产生的扰动不可能取得较高的收敛精度。4142例题例题4.3

32、用梯度法求目标函数用梯度法求目标函数F(x)= +25 的最优解。已知初始的最优解。已知初始点点x(0)2 2T，迭代精度取，迭代精度取=0.005。解：函数的梯度解：函数的梯度21x22x第一次迭代：以第一次迭代：以x(0)为起点沿为起点沿- -g(0)方向作一维搜索方向作一维搜索(1)(0)(0)242421002 100 xxg 初始点函数梯度值初始点函数梯度值:第一点函数梯度值第一点函数梯度值:43441220( )500 xF Xx 解解: :令令*00X *1 11 22 12 220()100050 x xx xx xx xFFH XFF正定正定得得: : 用解析法验证用解析法验

33、证 2212( )25F Xxx45(1)kX( )kX( )kS(2)kX*X梯度法的特点梯度法的特点: 几何概念直观几何概念直观,方法和程序简单方法和程序简单,远离极小点时收敛速度快。远离极小点时收敛速度快。 但越接近极小点收敛速度越慢。但越接近极小点收敛速度越慢。464.4 牛顿法牛顿法 4.4.1 原始牛顿法原始牛顿法原始牛顿法的基本思想原始牛顿法的基本思想：在第k次迭代点X(k)邻域内，用一个二次函数(X)去近似代替原目标函数F(X)，然后求出这个二次函数的极小点作为对原目标函数求优的下一个迭代点X(k+1)，通过若干次的重复迭代，使迭代点逐步逼近原目标函数的极小点X* 一元函数一元

34、函数f( (x) )在在x(k)点的泰勒展开式：点的泰勒展开式：( )2( )( )( )( )()( )()().2kkkkknfxf xf xfxxxxxR( )x*x利用原目标函数f(x)1个点的3个信息:函数值fk、一阶导数值fk 、二阶导数值fk构造一个二次函数(x)去近似代替注意：与一维优化方法的注意：与一维优化方法的二次插值法的不同二次插值法的不同47一元函数一元函数f( (x) )的例子的例子( )f x1( )x2( )x3( )x*x*(1)x*(2)x*(3)xxo484.4 牛顿法牛顿法 4.4.1 原始牛顿法原始牛顿法一元函数一元函数f( (x) )在在x(k)点的泰

35、勒展开式：点的泰勒展开式：( )2( )( )( )( )()( )()().2kkkkknfxf xf xfxxxxxRn元函数元函数F( (X) )在在X(k)点的泰勒展开式：点的泰勒展开式：1()2TTkkkF XFgXX HX()X( )( )( )(),(),kkkkkFF XgF XXXX 1 11 21( )2 12 2212.().x xx xx xnkx xx xx xnkxnxxnxxnxnFFFFFFHH XFFF494.4 牛顿法牛顿法 4.4.1 原始牛顿法原始牛顿法1(2)TTkkkFgXX HXX)0(kkgHXX令令*( )()()0kkkXgHXX*( )()

36、kkkHXXg *( )1kkkXXHg *( )1kkkXXHg(1)kX( )1kkkXHg(1)( )( )( )kkkkX= X+S( )1kkkSHg 牛顿方向牛顿方向:( )1k(定步长定步长)504.4 牛顿法牛顿法4.4.1 原始牛顿法原始牛顿法(1)( )1kkkkXXHg牛顿法具有二次收敛性。对于二次正定函数，迭代一次即可到达最优点；对于非二次函数，若函数的二次性态较强或迭代点已进入最优点的较小邻域，则其收敛速度也是很快的。但原始牛顿法还存在一个问题：由于在全部迭代过程中，取步长(k)1，这种定步长有时造成函数值反而有所增大 。514.4 牛顿法牛顿法4.4.1 原始牛顿法

37、原始牛顿法4.4.2 阻尼牛顿法阻尼牛顿法(1)( )1kkkkXXHg(1)( )(1)kkkkkXXHg(1) 对目标函数有较严格的要求。除了函数具有连续的一二阶导数以外，为了保证函数的稳定下降，海赛矩阵必须正定；为了能求逆阵又要求海赛矩阵必须非奇异。(2) 计算相当复杂，除了求梯度以外还需计算二阶偏导数矩阵和它的逆矩阵，占用机器的贮存量也很大。所以，它在工程优化设计中的应用受到一定的限制。 52梯度法和牛顿法对比梯度法和牛顿法对比方方 法法梯梯 度度 法法牛牛 顿顿 法法迭代公式迭代公式迭代方向迭代方向稳定下降性稳定下降性肯定能保证稳定下降须H(X)处处正定才能稳定下降收敛速度收敛速度离

38、X*远时下降速度较快,离近时下降很慢离X*近时收敛很快二次收敛性二次收敛性不具有二次收敛性具有二次收敛性(1)( )( )1kkkkkXXHg(1)( )( )kkkkXXgkg1kkHg53例题例题4.5 用牛顿法求函数用牛顿法求函数F(x)4(x11)22(x21)2x1x210的最优解。初始点的最优解。初始点x(0)0 0T，105。解：函数的梯度解：函数的梯度海赛矩阵及其逆海赛矩阵及其逆在在x(0)点处点处41008180043211*1HHH128943xgx8004H(0)10190988313044SHg 54沿沿S(0)方向一维搜索求最优步长得方向一维搜索求最优步长得代入函数解

39、得：代入函数解得： (0)=1故新迭代点为故新迭代点为该点的梯度该点的梯度满足终止条件，迭代即可结束满足终止条件，迭代即可结束(0)(1)(0)(0)(0)(0)(0)9908803344kxxS 55牛顿法的特点：牛顿法的特点：牛顿法具有二次收敛性，对正定二次函数一次迭代即可达牛顿法具有二次收敛性，对正定二次函数一次迭代即可达到极小点。对目标函数性态较好或当初始点取在极小点附到极小点。对目标函数性态较好或当初始点取在极小点附近时收敛速度快。近时收敛速度快。但对目标函数有较高的要求，必须存在一阶、二阶偏导但对目标函数有较高的要求，必须存在一阶、二阶偏导数，数，H（ x(k) ）需正定且非奇异。

40、计算复杂，计算量大。）需正定且非奇异。计算复杂，计算量大。564.5 DFP变尺度法变尺度法(1)( )( )kkkkXXg梯度法梯度法:(1)( )( )1kkkkkXXHg牛顿法牛顿法:(1)( )( )kkkkXXEgDavidon于1959年提出: (1)( )( )kkkkkXXA g拟牛顿公式拟牛顿公式( )kkkSA g 拟牛顿方向拟牛顿方向Ak是根据需要构造的nn阶对称矩阵，它是随着迭代点位置的变化而变化的。若AkE(单位矩阵)，上式为梯度方向；若Ak为目标函数二阶导数矩阵的逆矩阵H (x(k) )-1，则为牛顿方向。 尺度矩阵尺度矩阵4.5.1 变尺度法的基本思想变尺度法的基

41、本思想57 变尺度法的基本思想变尺度法的基本思想：设法构造一个对称正定阵：设法构造一个对称正定阵Ak代替代替 ,并在选代计算中，使其逐渐逼近并在选代计算中，使其逐渐逼近 。因此，一旦达到极值。因此，一旦达到极值点附近，就可望达到牛顿法的收敛速度，同时又避免了矩阵点附近，就可望达到牛顿法的收敛速度，同时又避免了矩阵的求逆计算。的求逆计算。 其选代公式：其选代公式： Ak是根据需要构造的是根据需要构造的nn阶对称矩阵，它是随着迭代点位置阶对称矩阵，它是随着迭代点位置的变化而变化的。的变化而变化的。 4.5 DFP变尺度法变尺度法(1)( )( )kkkkkXXA g1kH1kH1()()lim()

42、KKkAH X58 4.5.2 变尺度法构造矩阵的产生变尺度法构造矩阵的产生,1, 2,.kAk 递推方法产生递推方法产生:01002111.kkkAEAAAAAAAAA :kA校正矩阵校正矩阵 变尺度法采用构造矩阵来代替牛顿法中海赛矩阵的逆阵，其主要目的之一是为了避免计算二阶偏导数和计算它的逆矩阵，力图仅用梯度和其他一些易于获得的信息来确定迭代方向。 分析一下海赛矩阵与梯度之间的关系。59 4.5.2 变尺度法构造矩阵的产生变尺度法构造矩阵的产生海赛矩阵与梯度之间的关系海赛矩阵与梯度之间的关系1()2TTkkkF XFgXX HX()kkF XgHX( )()kkkgHXX(1)( )1()kkkkkggHXX即即(1)( )1()kkkkkggHXX(1)( )11()kkkkkXXHgg1kkkHy位移矢量梯度矢量差1kkkAy拟牛顿条件拟牛顿条件( 拟牛顿方程拟牛顿方程 ) ()kkkkAAy ?kAP116(1)11kkkSAg DFP公式公式604.5.3 对对DFP法几个问