车辆优化设计理论与实践第3章课件.ppt

1、车辆优化设计理论与实践江苏大学江苏大学汽车与交通工程学院汽车与交通工程学院 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件第第3章章 无约束优化方法无约束优化方法n 3.1 概述n 3.2 坐标轮换法n 3.3 鲍威尔方法n 3.4 最速下降法n 3.5 牛顿型方法n 3.6 共轭梯度法n 3.7 变尺度法n 3.8无约束优化方法的选用 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.1 概述o 当机械优化设计的很多问题，都是在一定的限制条件下追求某一指标为最小，所以它们都属于约束优化问题。但是，也有些实际问题，其数学模型本身数学模型本身就是一个无约束优化问题就是

2、一个无约束优化问题，或者除了在非常接近最终极小点的情况下，都可以按无约束问题来处理。o 另外研究无约束优化问题的另一个原因是，通过熟悉它的解法可以为研究约束优化问题打下良好的基础。除此以外，约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优化问题的无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方解法是优化设计方法的基本组成部分，也是优化方法的基础。法的基础。车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.1 概述o 按下述公式不断进行，形成迭代的下降算法。o 各种无约束优化方法的区别就在于确定其搜索方向的方法不同。所以，搜索方向 的构成问题乃是无约束

3、优化方法的关键。 o 根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。一类是只利用目标函数值的无约束优化方法，如坐标轮换法，鲍威尔（Powell）法等。另一类是利用目标函数的一阶或二阶导数的无约束优化方法，如最速下降法、共轭梯度法、牛顿法及变尺度法等。 ( )(1)( )kkkkSXX( )kS车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.1 概述o 对于无约束优化问题的求解，可以直接应用第2章讲述的极值条件来确定极值点位置。 o 除了一些特殊情况外，一般说来非线性方程组的求解与求无约束极值一样也是一个困难问题，甚至前者比后者更困难。一般用数值计算方法直接

4、求解无约束极值问题。 o 数值计算方法最常用的是搜索方法，其基本思想是从给定的初始点出发，沿某一搜索方向进行搜索，确定最佳步长使函数值沿方向下降最大。车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.2 坐标轮换法3.2.1 坐标轮换法的算法原理o 1基本思想 将一个n维问题转化为一系列的一维优化问题来求解，是一个降维的思想，具体来说，就是沿着坐标方向轮流搜索，每次n1个变量固定，只对一个变量作一维搜索，首先沿第一个坐标轴方向 进行一维搜索，求出该方向上目标函数最小的点或函数值有所下降的点 ，再以为起点，沿第二坐标轴方向 进行一维搜索，找到点 ，依次进行至 ，得到迭代点 ，到此完

5、成一轮迭代 。1= 1 00TE， ，2=1 00TE0， ， ，(1)1X(1)2X=01TnE0， ，(1)nX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.2 坐标轮换法o 图3-1 坐标轮换法的迭代过程车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.2 坐标轮换法o2步长的确定 步长的选择可有下面三种方法。 1）随即选择法 随机选择步长，只要保证函数值下降。 2）最优步长法 利用一维搜索来完成该方向上的最优步长，该方法的每一步均可最大限度地减小目标函数值，故可期望收敛得更快些，但程序稍微复杂。 3）加速步长法 这方法是开始选一个不大的初始步长，在每一次

6、搜索中，都是以 开始，随后在函数值下降的情况下以 ， ， 倍增的速度加大步长，直至函数值不再下降，取其前步长为最终步长，这种办法较简单，程序易编制。 000204车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.2 坐标轮换法例3-1 求min ，o 初始点为o 解：从 出发，沿 方向搜索，得 点：o 由 得 42112( )=2+2f Xxxx(0)03X (0)X1E(1)1X0130111)0()1(1EXX21411)6()2()(13. 31车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.2 坐标轮换法o 得：o 从 出发，沿 方向搜索，求得o 由 得(

7、1)13.13=3X(1)1X2E(1)2X10313. 3222)1(1)1(2EXX2242)287. 2()13. 1 ()(44. 12(1)23.13=1.56X车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.2 坐标轮换法o 将 ，进行第二轮迭代，按此法迭代下去，经7步（14次）迭代，可得到点 ，目标函数值为0.002，此问题的最优解应为， (1)(0)2XX2.221.11TX *2,1TX *0fX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.2 坐标轮换法3迭代步骤o 取初始点，判别收敛精度，维数n。o 求单变量极值问题的最优解，以求出 。

8、min o 判别是否满足 ，若 ，则转；若in，则令 ，转到。o 检验是否满足精度要求 若满足判别准则，则迭代停止，即所求；否则 转。1)()()()(1)()(1kiikikikiEXfEXf)()(1)(kiikikiEXX( )( )( )1kkkiiiiXXEinin1ii ( )(0)nXX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.2 坐标轮换法4坐标轮换法讨论o坐标轮换法具有程序简单，易于掌握的优点，但它的计算效率较低，因此它虽然步步在登高，但相当于沿两个垂直方向在爬山，路途迂回曲折，收敛很慢，因此它适用于维数较低（一般10）的目标函数求优。o另外对于如图3-

9、2所示的有“脊线”的目标函数等值线的情形，如果迭代点出现在脊线上点时，沿两个坐标轴方向均不能使函数值下降，而只有在一定范围内的方向才能使函数值下降，这就出现了病态而导致迭代失效。车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.2 坐标轮换法 3.2.2 算法的MATLAB实现o在在MATLAB中编程实现的坐标轮换法函数为：中编程实现的坐标轮换法函数为：minZB。o 功用：用坐标轮换法求解函数的极值。功用：用坐标轮换法求解函数的极值。o 调用格式：调用格式：x,minf = minZB(f,x0, delta,gama,sita,var,eps) 其中，其中，f: 目标函数目标

10、函数;o x0: 初始点；初始点；o delta: 初始步长；初始步长；ogama: 加速系数；加速系数；osita:收缩系数；收缩系数；ovar：自变量向量；：自变量向量；o eps: 精度；精度；车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.2 坐标轮换法o 3.2.3 算法举例例例3-2用坐标轮换法求下列函数的极小值。用坐标轮换法求下列函数的极小值。 sttsststf3423),(22车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.3 鲍威尔法3.3.1 鲍威尔法的基本原理o鲍威尔法是直接利用函数值来构造共轭方向的一种共轭方向法。其基本思想是在不用导数

11、的前提下，在迭代中逐次构造共轭方向。鲍威尔的基本算法是：在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和个线性独立的搜索方向。o从始点出发顺次沿个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。用这个方向替换原来个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。o此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。因为这种方法在迭代中逐次生成共轭方向，而共轭方向是较好的搜索方向，所以鲍威尔法又称作方向加速法。车辆优化设计理论与实践车辆优化设计理论与实践教学

12、课件教学课件3.3 鲍威尔法o鲍威尔法的寻优过程如图所示。鲍威尔法的寻优过程如图所示。 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.3 鲍威尔法例3-3 用Powell法求解。o 解：由o 得o 由 221212131222fXxxx xx(0)24TX 0142111)0()1(EXX41(1)24X 1042222)1()2(EXX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.3 鲍威尔法o 得o 得22(2)22X (3)(2)(0)224242SXX 1723(3)26173817X 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.

13、3 鲍威尔法o 第一轮迭代结束。以 作为新的起始点， 作为新的起始方向进行下一轮迭代。o 由o 得o 由 得)3(X)2(S(0)(3)XX(2)(1)SS17121(1)26173817X (3)(2)SS289182(2)370289478289X 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.3 鲍威尔法o 由o 得o 本例中 (3)(2)(0)3702672289172894783816828917289SXX983(3)*11XX (3)(3)723128942012168289TSHS车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.3 鲍威尔法o把

14、二维情况的基本算法扩展到维，则鲍威尔基本算法的要点是：在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和个线性独立的搜索方向。从始点出发顺次沿个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。用这个方向替换原来个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。o在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出得搜索方向去替换原向量组中得第一个向量，而不管它的“好坏”，这是产生向量组线性相关的原因所在。因此在改进的算法中首先判断原向量组是否需要替换。如果需要替换，还要进一步判断原向量组中哪个向量最坏，然后再用新产生

15、的向量替换这个最坏的向量，以保证逐次生成共轭方向。车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.3 鲍威尔法3.3.2 算法的MATLAB实现o在MATLAB中编程实现的Powell法函数为：minPowell。o 功用：用Powell法求解函数的极值。o 调用格式：x,minf = minPowell(f,x0, P,var,eps)o 其中，f: 目标函数;o x0: 初始点；o P: 线性无关的初始向量组；o var：自变量向量；o eps: 精度；o

16、 x: 目标函数最小值时的自变量值；o minf：目标函数的最小值。车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.3 鲍威尔法3.3.3 算法举例o 例例3-5用坐标轮换法求下列函数的极小值。用坐标轮换法求下列函数的极小值。 sttsststf3423),(22车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.4 最速下降法最速下降法 3.4.1最速下降法的算法原理o 如前所述，函数的梯度方向是函数上升最快的方向，也就是说，函数的负梯度方向是函数下降最快的方向。因此，将搜索方向取该点的负梯度方向（最速下降方向），就能使函数值在该点附近的范围内下降最快。按此规律不

17、断走步，就形成了最速下降法迭代公式：(1)( )( )()kkkkfXXX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.4 最速下降法最速下降法 3.4.1最速下降法的算法原理o 由于最速下降法是以负梯度方向作为搜索方向，所以最速下降法又称梯度法。为了使目标函数值沿搜索方向 能获得最大的下降值，其步长因子应取一维搜索的最佳步长。o 在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这就是说在最速下降法中，迭代点向函数极小点靠近的过程，走的是曲折的路线。这一次的搜索方向与前一次的搜索方向互相垂直，形成“之”字形的锯齿现象

18、。从直观上可以看到，在远离极小点的位置，每次迭代可使函数值有较多的下降。 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.4 最速下降法最速下降法 最速下降法的搜索过程 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.4 最速下降法最速下降法例 3-6 用最速下降法求目标函数 的极小点。o 解： 取初始点 o 则初始点处函数值及梯度分别为2212()25f Xxx(0)2,2TX(0)()104fX(0)1(0)224()50100 xfXxX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.4 最速下降法最速下降法o 沿负梯度方向进行一维搜索，有

19、o 为一维搜索最佳步长o 第一次迭代设计点位置和函数值 0(1)(0)(0)0002424()21002 100fXXX 006260.02003072312520(1)0241.9198772 1000.003071785X(1)()3.686164fX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.4 最速下降法最速下降法o 从而完成了最速下降法的第一次迭代。继续作下去，经10次迭代后，得到最优解*0 0TX，*()0fX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.4 最速下降法最速下降法 3.4.2 算法的MATLAB实现o在在MATLAB中编程实现的

20、最速下降法函数为：中编程实现的最速下降法函数为：minZSXJ。o 功用：用最速下降法法求解函数的极值。功用：用最速下降法法求解函数的极值。o 调用格式：调用格式：x,minf = minZSXJ(f,x0,var,eps)o 其中，其中，f: 目标函数目标函数;o x0: 初始点；初始点；o var：自变量向量；：自变量向量；o eps: 精度；精度；o x: 目标函数最小值时的自变量值；目标函数最小值时的自变量值；o minf：目标函数的最小值。：目标函数的最小值。车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.4 最速下降法最速下降法 3.4.3 算法举例o 例例3-7

21、用最速下降法求下列函数的极小值。用最速下降法求下列函数的极小值。1)2()4(),(22ststf车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.5 牛顿型方法3.5.1 牛顿法的算法原理o 牛顿方法和最速下降法一样，也是求解极值问题古老的算法之一。o 在第2章中我们已讨论过一维搜索的牛顿方法。对于一元函数，假定已给出极小点的一个较好的近似点，则在处将函数 进行泰勒展开到二次项，得二次函数。按极值条件得 的极小点，用它作为的第一个近似点。然后再在处进行泰勒展开，并求得第二个近似点。如此迭代下去，得到一维情况下的牛顿迭代公式+1kkkkfxxxfx车辆优化设计理论与实践车辆优化设

22、计理论与实践教学课件教学课件3.5 牛顿型方法3.5.1 牛顿法的算法原理o 对于多元函数 o 多元函数求极值的牛顿法迭代公式 ()f X()()f XX2( )( )( )( )( )( )1()()()()()()2TTkkkkkkffXfXXXXXXXX(1)()0kX2( )( )(1)( )()()()0kkkkffXXXX12(1)( )( )( )()()kkkkffXXXX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.5 牛顿型方法例3-8 用牛顿法求 的极小值。o 解： 取初始点 ，则初始点处的函数梯度、海赛矩阵及其逆阵分别是221212(,)25f x x

23、xx(0)2 2TX，1(0)224()50100 xfXx12(0)102()1050fX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.5 牛顿型方法o 代入牛顿法迭代公式，得o 从而经过一次迭代即求得极小点 及函数极小值 。 12(1)(0)(0)(0)102402()()121000050ffXXXX *0,0X*()0fX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.5 牛顿型方法o 3.5.1 牛顿法的算法原理o 对于多元函数 o 多元函数求极值的牛顿法迭代公式 ()f X()()f XX2( )( )( )( )( )( )1()()()()()

24、()2TTkkkkkkffXfXXXXXXXX(1)()0kX2( )( )(1)( )()()()0kkkkffXXXX12(1)( )( )( )()()kkkkffXXXX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.5 牛顿型方法3.5.2 算法的MATLAB实现o 在MATLAB中编程实现的修正牛顿法函数为：minXNT。o 功用：用最速下降法法求解函数的极值。o 调用格式：x,minf = minXNT(f,x0,var,eps)o 其中，f: 目标函数;o x0: 初始点；o var：自变量向量；o eps: 精度；o x: 目标函数最小值时的自变量值；o mi

25、nf：目标函数的最小值。车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.5 牛顿型方法3.5.3 算法举例o 例3-8 用修正牛顿法求函数的极小值。2),(22stststf车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.6 共轭梯度法o 3.6.1 共轭梯度法的算法原理o 共轭梯度法是共轭方向法中的一种，因为在该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.6 共轭梯度法o 3.6.1 共轭梯度法的算法原理o 为了利用梯度求共轭方向，我们首先来研究共轭方向与梯度

26、之间的关系。o 考虑二次函数o 从 点出发，沿G的某一共轭方向 作一维搜索，到达 点，即1()2TTf XGXXcbX( )kX( )kS(1)kX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.6 共轭梯度法o 有：o 而在 点处的梯度 、 分别为( )(1)( )+kkkkSXX( )(1)( )kkkkSXX( )kX(1)kX kg1kg( )kkGbgX(1)1kkGbgX( )(1)( )1()kkkkkkGGggSXX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.6 共轭梯度法o 若 和 对G是共轭的，则有o 即得o 这就是共轭方向与梯度之间的关

27、系。此式表明沿方向进行一维搜索，其终点与始点的梯度之差与的共轭方向正交。共轭梯度法就是利用这个性质做到不必计算矩阵就能求得共轭方向的。( ) jS( )kS( )( )0TjkGSS( )1)0(TjkkggS车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.6 共轭梯度法o共轭梯度法的几何说明车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件o 共轭梯度法的计算过程如下：o 1） 设初始点，第一个搜索方向取点的负梯度。即 o 沿 进行一维搜索， ，并算出 点处的梯度 。 是以 为切线和某等值曲线的切点。根据梯度和该点等值面的切面相垂直的性质，因此 和 正交，从而 和

28、正交，即 和 组成平面正交系。(0)0gS (0)S(1)(0)(0)0=+xxS(1)x1g(1)x(0)S1g(0)S1g1g0g0g车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.6 共轭梯度法o 2）在 、 所构成的平面正交系中求的共轭方向，作为下一步的搜索方向。0g1g(1)(0)10gSS 202100110ggggggTT21(1)(0)120ggSSg 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.6 共轭梯度法o 沿 方向进行一维搜索，得 ，并算出该点梯度 ，有o 即 o 根据共轭方向与梯度的关系式可知： 构成一个正交系。(1)S(2)(1)

29、(1)1xxS2g(0)1020TggS(1)20TgS0g1g2g车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.6 共轭梯度法o 3）在所构成的正交系中，求 与 及均共轭的方向 。o 根据共轭方向与梯度的关系，可求出： (0)S(1)S(2)S(2)21100gggS 2122112211ggggggTT01001110ggggTT22(2)(1)221ggSSg 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.6 共轭梯度法o 如此继续下去可求得共轭方向的递推公式为o 沿着这些共轭方向一直搜索下去，直到最后迭代点处梯度的模小于给定允许值为止。若目标函数为非

30、二次函数，经次搜索还未达到最优点时，则以最后得到的点作为初始点，重新计算共轭方向，一直到满足精度要求为止。 21(1)( )12kkkkkggSSg 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.6 共轭梯度法例3-9 用共轭梯度法求二次函数o 的极小点及极小值。o 解： 取初始点o 则 o 取 211222121242,xxxxxxxf(0)= 1,1TX(0)12(0)0212244422xxgfXxxX(0)042gS 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.6 共轭梯度法o 沿 方向进行一维搜索，得o 其中的 为最佳步长o 求得： (0)S0(

31、0)(1)(0)0001 4141 212SXX 04100(1)021411 22X 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.6 共轭梯度法o 为建立第二个共轭方向 ，需计算 点处的梯度及系数 值，得 o 从而求得第二个共轭方向0(1)X(1)S(1)12(1)1212241422xxgfXxxX 4120522210gg(1)(0)10214132242gSS 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.6 共轭梯度法o 再沿 进行一维搜索，得o 其中的 为最佳步长，o 求得o 则 (1)S1(1)(2)(1)111222213132222SXX

32、 1111(2)122413222X 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.6 共轭梯度法o 计算 点处的梯度 o 说明 点满足极值必要条件，再根据点的海赛矩阵o o 是正定的，可知满足极值充分必要条件。故 为极小点，即o 而函数极小值为 (2)X(2)12(2)22122400420 xxgfXxxX (2)X(2)2224GX(2)X*(2)42XX *8fX 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.6 共轭梯度法3.6.2 算法的MATLAB实现o在MATLAB中编程实现的共轭梯度法函数为：minGETD。o 功用：用共轭梯度法求解函数的

33、极值。o 调用格式：x,minf = minGETD(f,x0,var,eps)o 其中，f: 目标函数;o x0: 初始点；o var：自变量向量；o eps: 精度；o x: 目标函数最小值时的自变量值；o minf：目标函数的最小值。车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.6 共轭梯度法3.6.3 算法举例o 例例3-10 用共轭梯度法求函数的最小值用共轭梯度法求函数的最小值 22)3(),(ststf车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法3.7.1 变尺度法的算法原理o1变尺度法的基本概念o对于一般二次函数 o o如果进行尺度

34、变换o o则在新的坐标系中，函数的二次项变为o o选择这样变换的目的，是为了减低二次项的偏心程度。若矩阵是正定的，则总存在矩阵使o （单位矩阵）12TTfXX GXb XcXQX1122TTTX GXX Q GQXIGQQT车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法3.7.1 变尺度法的算法原理o 1变尺度法的基本概念o 所以 o 这说明二次函数矩阵的逆阵，可以通过尺度变换矩阵来求得。这样，牛顿法迭代过程中得牛顿方向便可写成o o 牛顿迭代公式变为o 1GQQT1( )( )( )TkkkGfQQfSXX ( )(1)( )( )( )TkkkkkkkQQfSX

35、XXX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法o 比较牛顿法迭代公式和梯度法迭代公式 o 可以看出，差别在于牛顿法中多了 部分。 实际上 是在空间内测量距离大小的一种度量，称作尺度矩阵(1)( )( )TkkkkQQfXXX(1)( )( )kkkkfXXXTQQTQQTQQH 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法o 既然牛顿法迭代公式可用尺度变换矩阵表示出来，即o 它和梯度法迭代公式只差一个尺度矩阵，那么牛顿法就可看成是经过尺度变换后的梯度法。经过尺度变换，使函数偏心率减小到零，函数的等值面变为球面（或超球面），使设计空

36、间中任意点处函数的梯度都通过极小点，用最速下降法只需一次迭代就可达到极小点。 (1)( )( )kkkkH fXXX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法o 为了避免在迭代公式中计算海赛矩阵的逆阵，可用在迭代中逐步建立的变尺度矩阵o 来替换，即构造一个矩阵序列 来逼近海赛逆矩阵序列。每迭代一次，尺度就改变一次，这正是“变尺度”的含义。这样，上式变为 o 其中 作一维搜索而得到的最佳步长。 ( )kkHHXkH(1)( )kkkkkH gXXk车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法o 这个迭代公式代表面很广，例如当 （单位矩

37、阵）时，它就变成最速下降法。以上就是变尺度法的基本思想。 o 为了使变尺度矩阵确实与近似，并具有容易计算的特点，必须对附加某些条件。 1）为保证迭代公式具有下降性质，要求 中得每一个矩阵都是对称正定的。 2）要求之间的迭代具有简单的形式。IHkkH车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法o 为最简单的形式，其中 为校正矩阵。上式称作校正公式。o 3）要求 必须满足拟牛顿条件。 kkkEHH1kEkH(1)( )11kkkkkHggXX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法车辆优化设计理论与实践车辆优化设计理论与实践教学课件教

38、学课件3.7变尺度法o 对于校正矩阵，可由具体的公式来计算，不同的公式对应不同的变尺度法，在下面进行讨论。但不论哪种变尺度法， 必须满足拟牛顿条件， 即：o 或 o 满足上式的有无穷多个，因此上述变尺度法（属于拟牛顿法）构成一族算法。kEkkkksyEHkkkkkyHsyE车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法o 3DEP算法和BFGS算法 DEP算法中的尺度矩阵取下列形式：kkTkkTkkkkTkTkkkkyHyHyyHysssHH1车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法o DEP算法由舍入误差和一维搜索不精确，有可能导

39、致奇异，而使数值稳定性方面不够理想。BFGS算法的校正公式为kTkkTkkkTkkkTkkkTkkkHyssyHssysyHyHH11车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法例 3-11 用DEP算法求下列函数的极值解。o 解： 1）取初始点， o 计算初始点处的梯度 211222121242,xxxxxxxf(0)1,1TX(0)12(0)0212244422xxgfXxxX 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法o 并取初始变尺度矩阵为单位矩阵，则第一次搜寻方向为o 沿 方向进行一维搜索 (0)0010440122H g

40、S (0)S0(0)(1)(0)00014141 212SXX 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法o 其中 为一维搜索最佳步长 o 得o 2）再按DEP法构造点 处的搜寻方向 ，需计算025. 00(1)20.5X(1)121212241422xxgxxX(1)X(1)S432421010ggy(0)(1)02110.510.5sXX 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法o 代入校正公式 0000000000001yHyHyyHysssHHTTTT43434343435 . 015 . 015 . 011001162

41、12925125. 05 . 05 . 0151100110041501950192521车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法o 则第二次搜寻方向为o 再沿方向进行一维搜索，得(1)1121198125505194126501005H gS 1(1)(2)(1)1118822550.5660.555SXX 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法o 其中 为一维搜索最佳步长，应满足o 得：o 3）为了判断点是否为极值点，需计算点处的梯度及海赛矩阵1451(2)42X (2)122212240420 xxgxxX 2(2)2

42、224fX车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法o 梯度为零向量，海赛矩阵正定。可见 点满足极值充要条件，因此为极小点。此函数的极值解为(2)X*(2)4,2TXX*8fX 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.7变尺度法3.7.2 算法的MATLAB实现o在MATLAB中编程实现的变尺度法函数为：minDFP。o 功用：用变尺度法求解函数的极值。o 调用格式：x,minf = minDFP(f,x0,var,eps)o 其中，f: 目标函数;o x0: 初始点；o var：自变量向量；o eps: 精度；o x: 目标函数最小值时

43、的自变量值；o minf：目标函数的最小值。车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.8 无约束优化方法的选用3.8.1算法的评价准则o1.可靠性o所谓可靠性是指算法在合理精度要求下，在一定的计算时间和一定的迭代次数内，求解最优化问题的计算成功率，能解出的问题越多，则算法的可靠性越好。所以有的文献也称它为通用性。o往往一种算法在一定计算时间，一定迭代次数，一定精度范围内不能求出最优解，而延长计算时间，增加迭代次数或降低精度要求则可能收敛，因此，可以根据情况，规定当产生下列情况之一时为计算失败，这些情况是：o在一定计算时间内不能求出最优解；o在给定最大迭代次数内不能求出最优

44、解；o解的精度达不到要求；o在非最优点停机。车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.8 无约束优化方法的选用3.8.1算法的评价准则o 2.有效性o 有效性指某种算法解题的效率。常有衡量标准：其一是在同一题目、同一精度要求和同一初始点的情况下所用计算机的机时数；其二是在同样条件下的函数求值次数，包括目标函数的求值和导数求值的总次数。o 3.准备工作的难易程度o 这条是考虑使用者准备工作的难易程度，如求函数的导数和编写计算程序的难易程度等。显然准备工作越简易越好。至于一个低效而易于准备的程序同一个高效却难于准备的程序，究竟哪一个好，这要在人力和拥有计算机存储量之间 权衡才

45、能确定。 车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.8 无约束优化方法的选用3.8.1算法的评价准则o 4.收敛性o 每种算法必须具有收敛性，否则，该算法在理论上就不能成立，当然也就根本不能用于解题。o 比较不同算法时，常用的一种收敛性判据是它们有效地进行二次函数优化的能力。因为在最优点附近，可用二次型很好地近似取代一般函数，不能很好地完成二次函数最优化算法，当搜索接近于最优点时，也不太可能很好地完成求一般非线性函数极值点的搜索。车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.8 无约束优化方法的选用3.8.2无约束优化方法的特点及应用范围o 通常认为牛顿

46、法在收敛条件下，其迭代次数少于变尺度法，变尺度法的迭代次数又少于共轨梯度法，而共轨梯度法的迭代次数又少于共轨方向法及Powell法，而后者的迭代次数又少于单纯变形或最速下降法、坐标轮换法。但是从计算程序的复杂程度来看，恰好与这一次序相反，因此，实际应用中，应选用哪种方法。如何将几种方法结合起来，扬长避短是很重要的。车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.8 无约束优化方法的选用o 坐标轮换法o 不需求导数，程序编制简单，存储量少，但计算效率低，可靠性也差，当目标函数的等值线具有脊线性态时，可能失败。适用于n10的小型优化问题，当函数等值线为圆或长短轴都平行于坐标轴的椭圆

47、时此法很有效。车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.8 无约束优化方法的选用o Powell 法o 具有二次收敛性，收敛速度较快，可靠性也较好，具有直接法的共同优点，一般认为存储量少，程序编制相对复杂一些。适用于中小型优化问题，对于多维问题收敛速度较慢。车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.8 无约束优化方法的选用o 最速下降法o 属间接法，要计算一阶导数，方法简单，可靠性较好，能稳定地使函数值下降。对初始点要求不高，存储量少，缺点是初始几步收敛快，后面收敛缓慢，愈靠近极值点愈慢。适用于精度要求不高或用于复杂函数寻找一个好的初始点。车辆优化设计理论与实践车辆优化设计理论与实践教学课件教学课件3.8 无约束优化方法的选用o 牛顿法o 当初始点选得合适时是目前收敛速度最快的算法。但当初始点选得不当时，会影响收敛导致失败。需计算一、二阶偏导数及Hessain 矩阵的逆阵，准备工作量大，程序复杂，存储量多，故当函数变量较多和因次较高时不宜采用此法。