优化设计4课件.ppt

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

2、题有约束多维问题现代设计方法现代设计方法3.4 3.4 无约束多维问题的优化方法无约束多维问题的优化方法无约束优化方法的核心是无约束优化方法的核心是确定探索方向确定探索方向（能使目标（能使目标函数值下降的方向），有了方向，沿这个方向应该函数值下降的方向），有了方向，沿这个方向应该走多远走多远（最优探索步长）（最优探索步长），则可采用一维搜索方法，则可采用一维搜索方法解决。解决。一、一、 坐标轮换法（变量轮换法）坐标轮换法（变量轮换法）基本原理：基本原理：沿着多维优化设计空间的沿着多维优化设计空间的每一个坐标轴每一个坐标轴作一维探索作一维探索，求得最小值。，求得最小值。现代设计方法现代设计方法坐

3、标轮换法的基本原理坐标轮换法的基本原理( (以二维问题为例以二维问题为例) )x1x2X*X(0,1)X(1)X(2)X(3)X(0)0 x1(0)x1(1)x1(2)x1(3)x1*x2(0)x2(1)x2(2)x2(3)x2*初始点初始点平行于平行于x1轴轴理论极小值理论极小值坐标轮换法的迭代路线是呈锯齿形前进的坐标轮换法的迭代路线是呈锯齿形前进的现代设计方法现代设计方法迭代步骤：迭代步骤：（1）第第1次迭代时，先固定次迭代时，先固定 x2= x2(0) 变量值不动变量值不动，由，由 初始点初始点X(0) 沿沿 x1 轴轴向进行一维探索，得到向进行一维探索，得到该轴方向上该轴方向上的的最优

4、点最优点 X(0,1)=x1(1), x2(0) ；（2）固定固定 x1=x1(1) 变量值变量值不动，由不动，由初始点初始点 X(0,1) 沿沿 x2 轴轴向进行一维探索，得到该轴方向上的向进行一维探索，得到该轴方向上的最优点最优点X(1)=x1(1), x2(1)现代设计方法现代设计方法（3）将将 X (1) 作为第作为第1次迭代的次迭代的改进点改进点，之后，完全，之后，完全依照第依照第1 次的步骤进行第次的步骤进行第2、3、k次的坐标轮换次的坐标轮换迭代，直到满足精度要求后停止迭代。迭代，直到满足精度要求后停止迭代。现代设计方法现代设计方法不同性质目标函数坐标轮换法的求优效能不同性质目标

5、函数坐标轮换法的求优效能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轴平行轴平行等值线为椭圆等值线为椭圆,长、短轴与长、短轴与x1,x2轴不平行轴不平行现代设计方法现代设计方法二、梯度法二、梯度法1.1.基本思想基本思想梯度方向是梯度方向是函数值增加最快的方向函数值增加最快的方向，而，而负梯度方向负梯度方向是函数下降最快的方向是函数下降最快的方向，所以梯度法以，所以梯度法以负梯度方向负梯度方向为搜索方向

6、，每次迭代都沿着负梯度方向进行一维为搜索方向，每次迭代都沿着负梯度方向进行一维搜索，直到满足精度要求为止。因此，梯度法又称搜索，直到满足精度要求为止。因此，梯度法又称为为最速下降法最速下降法。现代设计方法现代设计方法设在某次迭代中已取得迭代点设在某次迭代中已取得迭代点X(k)，从该点出发，取，从该点出发，取负梯度方向负梯度方向为搜索方向为搜索方向S(k)，即，即： )()()()()()()()(kkkkkXfXfSXfS 或或 )( , )(12)(T21)(niiknkxfXfxfxfxfXf其中：其中：现代设计方法现代设计方法以以单位负梯度方向单位负梯度方向为探索方向，第为探索方向，第k

7、+1次迭代计算次迭代计算所得的新点为：所得的新点为：)()()()()()() 1(kkkkkXfXfXX)()()()() 1(kkkkXfXX上式即为上式即为梯度法迭代公式梯度法迭代公式。以以负梯度方向负梯度方向为探索方向，第为探索方向，第k+1次迭代计算所得次迭代计算所得的新点为：的新点为：现代设计方法现代设计方法因为因为X(k)已知，故已知，故 f(X(k) 和和 不难求出，只不难求出，只要知道要知道步长步长 后，就可以得到新点后，就可以得到新点X(k+1)。由于每次。由于每次迭代能保证迭代能保证 f(X(k+1)f(X(k) ( (以负梯度方向为搜索方以负梯度方向为搜索方向向) )，

8、如此反复计算，最后总能达到，如此反复计算，最后总能达到最优点最优点X*。为了使目标函数值在搜索方向为了使目标函数值在搜索方向S(k)上获得最多的下降，上获得最多的下降，每次迭代都进行一维搜索每次迭代都进行一维搜索求最优步长求最优步长，即求，即求 )()(kXf)(min)()()()()()(kkkkkSXfSXf ：步长因子；步长因子； (k) ：最优步长因子最优步长因子现代设计方法现代设计方法2.2.迭代步骤迭代步骤1）任选初始点）任选初始点X(0)，计算精度，计算精度 ，令，令k=0 ；2）计算）计算 f(X(k)和和 ；3）收敛判断，）收敛判断， ( (梯度准则梯度准则) )A. 若若

9、 ，则，则X(k)为近似最优点，停止迭为近似最优点，停止迭代，输出最优解代，输出最优解X*= X(k) 和和 f(X*)= f(X(k) ；B. 若若 ，则转下一步继续迭代；，则转下一步继续迭代；4）令）令)()(kXf?)()(kXf)()(kXf)()(kXf)()()()()(kkkXfXfS 现代设计方法现代设计方法5）确定最优步长因子）确定最优步长因子 (k) ，使，使6）计算）计算 ；7）令）令k=k+1，转，转2）。）。)(min)()()()()()(kkkkkSXfSXf)()()()1(kkkksXX现代设计方法现代设计方法Eg:用梯度法求函数用梯度法求函数 f(X)=(x

10、1-1)2 +(x2-1)2 的极小值，的极小值，初始点初始点X(0)=(0,0)T ，计算精度，计算精度 =0.01 。解解:1):1)22)() 1(2) 1(2)()0(21XfxxXf2)2)22)()0(Xf3)3)令令22)()0()0(XfS则则22)0()0()1 (SXX负梯度方向负梯度方向现代设计方法现代设计方法4)4)222) 1 () 12(2) 12() 12()(Xf5)5)00)()1 (Xf令令0)( ) 1 (Xf得得21即即11) 1 (X6)6)0)()1 (Xf因此因此, ,最优解为最优解为11*X(1,1)x1 1x2 20 判断判断X(1)(1)点是

11、否点是否为极小值点为极小值点梯度准则梯度准则现代设计方法现代设计方法解解:（1） 如果如果 转（转（2），否则转（），否则转（5）。）。 970. 0243. 0)()(492.16)(164)(82)()0()0()0()0()0(21XfXfSXfXfxxXf1)0()(XfEg: 用梯度法求目标函数用梯度法求目标函数 f(X)=x12+4x22 在初始点在初始点 X(0)=2 2T，迭代精度，迭代精度 =10-2 下的最优解。下的最优解。单位负梯度方向单位负梯度方向现代设计方法现代设计方法（2）492.16645. 7)(970. 0243. 022)0()0()1()0()0()0()

12、0()1(dXdfSXX现代设计方法现代设计方法（3） ，并转（，并转（1）。）。（4）第）第7次迭代后，次迭代后， 成立，停止迭代。成立，停止迭代。（5）取）取 时，时， f(X*)=2.59610-60 092. 0476. 1157. 20)()1()0()0()1(XdXdf,000096. 00016. 0)7(TXTXX000096. 00016. 0*)7(01. 00032. 0)(1)7(Xf现代设计方法现代设计方法 初始点位置不同初始点位置不同, ,目标函数等值线形状目标函数等值线形状不同不同, , 搜索效率搜索效率( (算法收敛速度算法收敛速度) )不同。不同。现代设计方

13、法现代设计方法梯度法的特点：梯度法的特点：n 负梯度方向只是函数值在负梯度方向只是函数值在点点X(k)的邻域的邻域内下降最快内下降最快的方向，离开该邻域以后函数值不一定下降最快。的方向，离开该邻域以后函数值不一定下降最快。因此，采用负梯度方向，从局部看函数值下降快，因此，采用负梯度方向，从局部看函数值下降快，从全局看却要走很多弯路。因此，从全局看却要走很多弯路。因此，梯度法的收敛梯度法的收敛速度较慢。速度较慢。n 梯度法的迭代过程，梯度法的迭代过程，每相邻两步的搜索方向是垂每相邻两步的搜索方向是垂直的直的，也就是说，也就是说梯度法的迭代路线是呈锯齿形前梯度法的迭代路线是呈锯齿形前进的进的。（坐

14、标轮换法也是呈锯齿形）（坐标轮换法也是呈锯齿形）现代设计方法现代设计方法n 梯度法迭代过程中，当迭代点离梯度法迭代过程中，当迭代点离理论极小点理论极小点较远较远时，时，一次迭代的函数值下降量比较大一次迭代的函数值下降量比较大。迭代点离。迭代点离极小点越近，极小点越近，函数值下降的速度就越慢函数值下降的速度就越慢。因此，。因此，梯度法常与其它优化方法结合使用。即梯度法常与其它优化方法结合使用。即第一步采第一步采用梯度法用梯度法，后面采用其它的方法确定搜索方向。，后面采用其它的方法确定搜索方向。n 梯度法的收敛速度与目标函数的性质有关。如果梯度法的收敛速度与目标函数的性质有关。如果目标函数的目标函

15、数的等值线（面）等值线（面）为为同心圆（球）同心圆（球），则，则无无论从哪里出发，只需要一次搜索就能达到极小点论从哪里出发，只需要一次搜索就能达到极小点。 （沿着等直线半径方向搜索即可）（沿着等直线半径方向搜索即可）现代设计方法现代设计方法三、牛顿法三、牛顿法1.1.基本牛顿法基本牛顿法设目标函数是设目标函数是连续二阶可微的连续二阶可微的，将函数在，将函数在X(k)点按点按泰勒级数展开后，得到二次项泰勒级数展开后，得到二次项将上式去括号展开，得将上式去括号展开，得)()(21 )()()()()(2)()()()(kkTkkkTkXXXfXXXXXfXfXf现代设计方法现代设计方法对对X求导，

16、设求导，设X(K+1)是极小点，并令一阶导数为是极小点，并令一阶导数为0，得，得0)()()()(1)(2)(kkkkTXXXfXfXXf)()( )()()()(21)(2kTkkkkXfXXfXXf )(21)()(21)()()()()(22)()(2)(2)(2)()()()(kkkkkkTkkTkXfXXfXXXXfXfXXXfXfXf即即现代设计方法现代设计方法)()(1 kkkSXX上式即为上式即为基本牛顿法基本牛顿法的迭代公式，其中的迭代公式，其中S(k)称为称为牛顿方向牛顿方向。则则 令令等式两边同时左乘等式两边同时左乘 2f(X(k) -1,解出解出X(k+1),得到得到)

17、()( )(1)(2)(1kkkkXfXfXX)()()(1)(2)(kkkXfXfS牛顿法步长总为牛顿法步长总为1 1现代设计方法现代设计方法Eg: 用牛顿法求下列函数的极小值。用牛顿法求下列函数的极小值。60410)(21212221xxxxxxXf解：解：(1)(1)取初始点取初始点 (2)(2)计算牛顿方向计算牛顿方向00)0(X41042102)()0(1221XXxxxxXf现代设计方法现代设计方法2112)(2221222122122xfxxfxxfxfXf211231)(12Xf68182431410211231 )()0(1)0(2)0(XfXfST故故(3)(3)极小值极小

18、值8)(min686800)0()0()0(*XfSXX (0)(0)=1=1现代设计方法现代设计方法基本牛顿法的特点：基本牛顿法的特点：n 对于二次函数而言，取到二次项的泰勒展开式就对于二次函数而言，取到二次项的泰勒展开式就是目标函数本身。如果是目标函数本身。如果二阶导数矩阵二阶导数矩阵( (海色矩阵海色矩阵) )正定正定，那么按基本牛顿法求出的，那么按基本牛顿法求出的X(1)就是目标函数就是目标函数的的精确极小点精确极小点。因此，对。因此，对正定二次函数正定二次函数而言，牛而言，牛顿法只需一次迭代就可以达到精确极小点。顿法只需一次迭代就可以达到精确极小点。n 基本牛顿法迭代时步长总是为基本

19、牛顿法迭代时步长总是为1 1，对，对非二次函数非二次函数、非正定函数非正定函数而言，一次迭代并不能达到极小点，而言，一次迭代并不能达到极小点，有时还可能失效（即总是不能收敛）。有时还可能失效（即总是不能收敛）。现代设计方法现代设计方法2.2.阻尼牛顿法阻尼牛顿法基本牛顿法对基本牛顿法对非正定函数非正定函数失效是因为沿牛顿方向搜失效是因为沿牛顿方向搜索时，索时，步长总是为步长总是为1，这，这并不能保证找到的下一个并不能保证找到的下一个迭代点是该方向上的极小点迭代点是该方向上的极小点。为此，增加步长因子。为此，增加步长因子 和一维搜索过程。此时的牛顿法称为和一维搜索过程。此时的牛顿法称为阻尼牛顿法

20、阻尼牛顿法。阻尼牛顿法比基本牛顿法多一个一维搜索过程阻尼牛顿法比基本牛顿法多一个一维搜索过程现代设计方法现代设计方法阻尼牛顿法迭代步骤：阻尼牛顿法迭代步骤：1）选取初始点）选取初始点 X(0)，计算精度，计算精度 ，令，令k=0 ；)()()(1 kkkkSXX 4）一维搜索，求）一维搜索，求 (k),使使)(min)()()()()()(kkkkkSXfSXf)()()(1)(2)(kkkXfXfS3 3）令）令 ) )计算计算 1)(2)(2)()()()(kkkXfXfXf，）按一维搜索结果，计算）按一维搜索结果，计算现代设计方法现代设计方法6）收敛判断，）收敛判断，A. 若若 ，则，则

21、X(k+1)为近似最优点，停止迭为近似最优点，停止迭代，输出最优解代，输出最优解X*=X(k+1) 和和 f(X*)=f(X(k+1) )；B. 若若 ，则令，则令k=k+1，转，转2）继续迭代；）继续迭代；?)()(kXf)()(kXf)()(kXf现代设计方法现代设计方法数学分析表明，数学分析表明，牛顿法具有很好的局部收敛性质牛顿法具有很好的局部收敛性质，对二次函数来说，仅一步就达到优化点，但对一般对二次函数来说，仅一步就达到优化点，但对一般函数来说，在一定条件下，当函数来说，在一定条件下，当初始点的选取初始点的选取充分充分接接近近目标函数的目标函数的极小点极小点时，有很快的收敛速度，但若

22、时，有很快的收敛速度，但若初始点选取离极小点比较远，就难保证收敛；另外，初始点选取离极小点比较远，就难保证收敛；另外，牛顿法必须求牛顿法必须求一阶导数一阶导数、二阶导数矩阵二阶导数矩阵及其及其逆阵逆阵，这对复杂的目标函数来说，是比较困难的。这对复杂的目标函数来说，是比较困难的。现代设计方法现代设计方法四、变尺度法四、变尺度法n梯度法梯度法构造简单，只用到一阶偏导数，计算量小，构造简单，只用到一阶偏导数，计算量小，迭代初期收敛速度快迭代初期收敛速度快，但当迭代点到最优点附近，但当迭代点到最优点附近时收敛速度极慢；时收敛速度极慢；变尺度法是在梯度法和牛顿法的基础上发展起来的变尺度法是在梯度法和牛顿

23、法的基础上发展起来的一种优化方法。用得较多的是一种优化方法。用得较多的是DFP（Davidon-Fletcher-Powell)变尺度法。变尺度法。1.1.基本思想基本思想现代设计方法现代设计方法n牛顿法牛顿法收敛很快，对二次函数只需迭代一次就能收敛很快，对二次函数只需迭代一次就能达到最优点，对非二次函数也能较快达到最优点，达到最优点，对非二次函数也能较快达到最优点，但牛顿法但牛顿法计算量计算量和和存储量存储量偏大。而且某些函数可偏大。而且某些函数可能根本无法计算二阶偏导数矩阵及其逆阵。能根本无法计算二阶偏导数矩阵及其逆阵。为了综合梯度法和牛顿法的优点，扬长避短，为了综合梯度法和牛顿法的优点，

24、扬长避短，产生了变尺度法。产生了变尺度法。现代设计方法现代设计方法变尺度法的搜索方向为变尺度法的搜索方向为变尺度法的基本迭代公式为变尺度法的基本迭代公式为)()()()()()1(kkkkkXfAXX)()()()(kkkXfAS，得到牛顿法。，得到牛顿法。令令，得到梯度法，得到梯度法令令1)(2)()()(kkkXfAIA 式中，式中，A(k)是一个需要构造的是一个需要构造的n 阶方阵，称为阶方阵，称为变变尺尺度矩阵度矩阵，它随迭代点位置的变化而变化，形成，它随迭代点位置的变化而变化，形成一个矩阵序列。一个矩阵序列。搜索方向搜索方向S(k)=- A(k) f (X(k)称为称为拟牛顿方向拟牛

25、顿方向。现代设计方法现代设计方法2.2.变尺度矩阵的构建变尺度矩阵的构建变尺度矩阵变尺度矩阵A(k)的构建是从的构建是从A(0)=I开始，通过迭代公式开始，通过迭代公式 A(k+1) = A(k) + E(k)得到的。得到的。E(k)称为称为修正矩阵修正矩阵，通过它的一步步修正，通过它的一步步修正，使使A(k)逐步逼近逐步逼近 2f(X(k)-1 ，即使变尺度法的迭代方向，即使变尺度法的迭代方向逐步逼近牛顿方向。逐步逼近牛顿方向。修正矩阵取不同的形式，就形成了不同的变尺度法。修正矩阵取不同的形式，就形成了不同的变尺度法。现代设计方法现代设计方法DFP变尺度法修正矩阵变尺度法修正矩阵E(k)的构

26、造公式为的构造公式为)()()()()()()()()()()()()(kkTkkTkkkkTkTkkkkgAgAggAgSSSE)()()()()1()1()()1()(kkkkkkkXfgXfgggg 式中，式中，)()()()(kkkXfAS)()()1(kkkEAAE(0)=? (k)=?现代设计方法现代设计方法3.3.变尺度法的迭代步骤变尺度法的迭代步骤结束；否则转下一步；结束；否则转下一步；为极小点，迭代为极小点，迭代，则，则收敛判断：若收敛判断：若）；计算计算）梯度法）梯度法）（第一步迭代实际就是（第一步迭代实际就是；一维搜索一维搜索）；，计算计算）阶单位方阵）；阶单位方阵）；为

27、为，令令）；，计算精度，计算精度取初始点取初始点） )1()1()1()1()()()()1()0()0()0()0()0()0(6)(54)(3(021kkkkkkkkXgXfgSXXIgSXfgnIIAkX现代设计方法现代设计方法），转步骤，转步骤）令）令新的搜索方向新的搜索方向计算变尺度矩阵，构造计算变尺度矩阵，构造）4187)1()1()1()()()()()()()()()()()()()()()()1()1(kkgASgAgAggAgSSSAEAASkkkkkTkkTkkkkTkTkkkkkkkk 现代设计方法现代设计方法解：解： (1)(1)取初始点：取初始点：00)0(X100

28、1)0(IA41042102)()0(122121)0(XXxxxxxfxfXf4104101001)0()0()0(XfASEg: 用变尺度法求下列函数的极小值。用变尺度法求下列函数的极小值。 01. 0)0 , 0(60410)()0(21212221，TXxxxxxxXf现代设计方法现代设计方法一维搜索最优步长因子的求解一维搜索最优步长因子的求解 TS410410)0(因为：值代入目标函数并求极小将TSXX4 ,10)0()0()1(6011676min60161004016100min()(min2222)0()0(SXf的一维函数为单变量式中 )( )0()0(SXf现代设计方法现代

29、设计方法0)()0()0(SXf令：7631. 038297621160116762 即：7631. 0)0(为：所以一维最优步长因子现代设计方法现代设计方法（2 2）一维搜索）一维搜索052. 3631. 74107631. 000)0()0()0() 1 (SXX526. 5211. 242102)1(122121) 1 () 1 (XXxxxxxfxfXfg526. 1211.12410526. 5211. 2)0() 1 ()0(ggg（3 3）现代设计方法现代设计方法（4）求）求A(1) )()()()()()()()()()()()()()()()1(kkTkkTkkkkTkTkk

30、kkkkkgAgAggAgSSSAEAA现代设计方法现代设计方法0897. 1386. 0386. 0673. 0526. 1211.121001526. 1211.121001526. 1211.12526. 1211.121001526. 1211.124104104107631. 01001) 1 ()0()0()0()0()0()0()0()0()0()0()0()0()0()0()0() 1 (AgAgAggAgSSSAEAATTTTT则有：则有：现代设计方法现代设计方法(5)(5)搜索方向搜索方向169. 5646. 0526. 5211. 20897. 1386. 0386. 0

31、673. 0)1()1()1(XfAS9999. 59999. 7169. 5646. 05701. 0052. 3631. 7) 1 () 1 () 1 ()2(SXX与牛顿法比较，结果非常接近，从本例中可以看出用与牛顿法比较，结果非常接近，从本例中可以看出用近似矩阵代替二阶导数及逆阵是可行的。近似矩阵代替二阶导数及逆阵是可行的。 最优步长因子：(1)=0.5701；方法同前。一维搜索得：现代设计方法现代设计方法（6）判断是否结束搜索）判断是否结束搜索0001. 00001. 042102)2(122121)2()2(XXxxxxxfxfXfg01. 0 )2(g因为：因为：所以所以X(2)点为极小点。点为极小点。解决此类问题的关键是：求解解决此类问题的关键是：求解 (0)、 (1)、 S(1)、 H(1)现代设计方法现代设计方法精品课件精品课件！现代设计方法现代设计方法精品课件精品课件！现代设计方法现代设计方法【本节思考题】【本节思考题】1.1.什么情况下梯度法的收敛速度慢？什么情况下梯度法的收敛速度慢？2.2.什么是牛顿方向？牛顿方向有什么特点？什么是牛顿方向？牛顿方向有什么特点？3.3.梯度法、牛顿法、变尺度法有什么内在的联系？梯度法、牛顿法、变尺度法有什么内在的联系？