第五章无约束优化的间接搜索法-资料课件.ppt

1、机械优化设计机械优化设计太原科技大学张学良第五章 无约束优化的间接搜索法 间搜索法是指搜索方向间搜索法是指搜索方向S(k)的构的构建利用目标函数的一阶或二阶导数信建利用目标函数的一阶或二阶导数信息的无约束优化方法，如梯度法、牛息的无约束优化方法，如梯度法、牛顿法、共轭梯度法、变尺度法。顿法、共轭梯度法、变尺度法。X(k+1)=X(k)+(k)S(k)(k=0,1,2,)基本思想基本思想 5.1 梯度法梯度法（最速下降法、负梯度法）（最速下降法、负梯度法）利用负梯度方向作为迭代计算的搜索方利用负梯度方向作为迭代计算的搜索方向，即向，即S(k)=f(X(k)或或 S(k)=f(X(k)/|f(X(

2、k)|迭代计算公式迭代计算公式 X(k+1)=X(k)+(k)f(X(k)或或 X(k+1)=X(k)+(k)f(X(k)举例：举例：用梯度法求目标函数用梯度法求目标函数 f(X)=x12+4x22 的无约束最优解。初始的无约束最优解。初始点点X1(0)=0 0 T，X2(0)=2 2 T。基本思想和基本算法基本思想和基本算法 5.2 牛顿法牛顿法 在点在点X(k)的邻域内，用一个二次函数的邻域内，用一个二次函数(X)来近似代替原目标函数，并以来近似代替原目标函数，并以 (X)的极小点的极小点作为原目标函数的极小点的近似值，若不满作为原目标函数的极小点的近似值，若不满足收敛精度要求，则将该近似

3、极小点作为下足收敛精度要求，则将该近似极小点作为下一次迭代的初始点。如此反复迭代，直到所一次迭代的初始点。如此反复迭代，直到所求的近似极小点满足收敛精度要求为止。求的近似极小点满足收敛精度要求为止。f(X)f(X(k)+T f(X(k)(X-X(k)+0.5(X-X(k)T 2 f(X(k)(X-X(k)=(X)(X)的极小点应满足：的极小点应满足：(X)=0 即即 f(X(k)+2 f(X(k)(X-X(k)=0 2 f(X(k)(X-X(k)=-f(X(k)当当 2 f(X(k)正定且有逆阵时，上式两边正定且有逆阵时，上式两边同时左乘同时左乘 2 f(X(k)-1，得得X =X(k)-2

4、f(X(k)-1 f(X(k)牛顿法的迭代公式为牛顿法的迭代公式为X(k+1)=X(k)-2 f(X(k)-1 f(X(k)X(k+1)=X(k)+(k)S(k)牛顿方向：牛顿方向：S(k)=-2 f(X(k)-1 f(X(k)迭代步长：迭代步长：(k)=1 修正牛顿法（又称阻尼牛顿法）的迭代修正牛顿法（又称阻尼牛顿法）的迭代公式为公式为X(k+1)=X(k)-(k)2 f(X(k)-1 f(X(k)阻尼因子：阻尼因子：(k)计算步骤及算法框图计算步骤及算法框图 1）任选初始点任选初始点 X(0)，给定收敛精度，给定收敛精度 0，k=0；2）计算计算X(k)点的梯度点的梯度 f(X(k)及其模

5、；及其模；3）检验终止条件：检验终止条件：|f(X(k)|？若满足，则输出最优解：若满足，则输出最优解：X*=X(k)，f*=f(X*)，并终止迭代计算，并终止迭代计算；否则，继续下一步迭代计算；否则，继续下一步迭代计算；4）计算）计算X(k)点的海赛矩阵点的海赛矩阵 2 f(X(k)及其逆及其逆矩阵矩阵 2 f(X(k)-1 5）沿牛顿方向）沿牛顿方向S(k)=-2 f(X(k)-1 f(X(k)进行一维搜索，求最佳步长进行一维搜索，求最佳步长(k)；6）令）令X(k+1)=X(k)+(k)S(k)，并令，并令k k+1，转转2），重复上述迭代计算过程。），重复上述迭代计算过程。举例：举例：

6、用牛顿法求目标函数用牛顿法求目标函数 f(X)=x12+4x22 的无约束最优解。初始的无约束最优解。初始点点X1(0)=0 0 T，X2(0)=2 2 T。解：解：f(X)=2x1 8x2 T 2 f(X)=0 0 8 2 f(X)-1=0.5 00 0.125 f(X1(0)=0 0 T f(X2(0)=4 16 TX1(1)=X1(0)-2f(X1(0)-1 f(X1(0)=0 0 T-0.5 00 0.125 0 0=0 0 T X2(1)=X2(0)-2f(X2(0)-1 f(X2(0)=2 2 T-0.5 00 0.125 4 16=0 0 T 可见，可见，X2(1)=X1(0)=

7、0 0 T 就是目标函就是目标函数的理论极小点，仅仅迭代了一次，与初始数的理论极小点，仅仅迭代了一次，与初始点的选择无关。点的选择无关。由于一般函数在极小点附近呈现出较强由于一般函数在极小点附近呈现出较强的二次性，所以牛顿法在极小点附近收敛速的二次性，所以牛顿法在极小点附近收敛速度较快。但无论是牛顿法还是修正牛顿法在度较快。但无论是牛顿法还是修正牛顿法在每次迭代计算时都要计算目标函数的海赛每次迭代计算时都要计算目标函数的海赛矩阵及其逆阵，因此计算工作量很大，特别矩阵及其逆阵，因此计算工作量很大，特别是矩阵求逆，当维数高时工作量更大，且当是矩阵求逆，当维数高时工作量更大，且当海赛矩阵为奇异阵时，

8、其逆阵不存在，无法海赛矩阵为奇异阵时，其逆阵不存在，无法使用牛顿法，所以在实际使用中受到一定限使用牛顿法，所以在实际使用中受到一定限制。另外，从计算机存储方面考虑，牛顿法制。另外，从计算机存储方面考虑，牛顿法所需要的存储量是很大的。所需要的存储量是很大的。若能设法构造一个矩阵来逼近海赛矩阵若能设法构造一个矩阵来逼近海赛矩阵的逆阵而避免计算海赛矩阵及其逆阵，这样的逆阵而避免计算海赛矩阵及其逆阵，这样的方法统称为拟牛顿法。如只用梯度信息但的方法统称为拟牛顿法。如只用梯度信息但比梯度法快的共轭梯度法，以及针对牛顿法比梯度法快的共轭梯度法，以及针对牛顿法提出的变尺度法等。提出的变尺度法等。基本思想基本

9、思想5.3 共轭梯度法共轭梯度法 共轭梯度法属于共轭方向法中的一种方共轭梯度法属于共轭方向法中的一种方法。它是利用目标函数在迭代点法。它是利用目标函数在迭代点X(k)的梯度来的梯度来构造共轭搜索方向的，具有二次收敛性。构造共轭搜索方向的，具有二次收敛性。共轭梯度法搜索的第一步沿负梯度方向，共轭梯度法搜索的第一步沿负梯度方向，以后各步沿与上次搜索方向相共轭的方向进以后各步沿与上次搜索方向相共轭的方向进行搜索。共轭梯度法的关键是如何在迭代过行搜索。共轭梯度法的关键是如何在迭代过程中不断生成共轭搜索方向程中不断生成共轭搜索方向 共轭梯度法共轭搜索方向的生成共轭梯度法共轭搜索方向的生成 考虑二次函数考

10、虑二次函数 f(X)=0.5 XT H X +BT X+C 从从 X(k)出发，沿出发，沿H的某一共轭方向的某一共轭方向S(k)作一维作一维搜索得到搜索得到 X(k+1)，即，即 X(k+1)X(k)=(k)S(k)（1）将将f(X)在在 X(k)和和 X(k+1)两点处的梯度表示并记作两点处的梯度表示并记作 g(k)=f(X(k)=H X(k)+B （2）g(k+1)=f(X(k+1)=H X(k+1）+B （3）（3）-（2）得）得 g(k+1)g(k)=H(X(k+1)X(k)=(k)H S(k)（4）（4）式两边同时左乘）式两边同时左乘S(j)T，有，有S(j)Tg(k+1)g(k)=

11、(k)S(j)TH S(k)=0 若若S(j)和和S(k)关于关于H共轭，则有共轭，则有S(j)T H S(k)=0即即 S(j)T g(k+1)g(k)=0 （5）式（式（5）就是共轭方向与梯度之间的关系。）就是共轭方向与梯度之间的关系。它表明沿方向它表明沿方向S(k)进行一维搜索，其终点进行一维搜索，其终点X(k+1)与始点与始点X(k)梯度之差梯度之差(g(k+1)g(k)与与 S(k)的共轭的共轭方向方向S(j)与正交。共轭梯度法就是利用这个性质与正交。共轭梯度法就是利用这个性质做到不必计算矩阵做到不必计算矩阵H就能求得共轭方向的。就能求得共轭方向的。1）设初始点）设初始点X(0)，第

12、一个搜索方向，第一个搜索方向S(0)取取X(0)点的负梯度方向点的负梯度方向-g(0)。即。即 S(0)=-g(0)沿沿S(0)进行一维搜索，得进行一维搜索，得 X(1)=X(0)+(0)S(0)，并计算并计算X(1)点的梯度点的梯度 g(1)。那么，那么，g(1)与与S(0)有什么关系呢？有什么关系呢？X(0)g(1)-g(0)X(1)二者正交，即二者正交，即 g(1)TS(0)=0 或或 S(0)Tg(1)=0 因此，因此，S(0)与与g(1)构成平面正交系。构成平面正交系。2）在）在S(0)与与g(1)构成的平面正交系中求构成的平面正交系中求S(0)的共的共轭方向轭方向S(1)，以此作为

13、下一步迭代计算的搜索方，以此作为下一步迭代计算的搜索方向。取向。取S(1)为为S(0)与与g(1)的线性组合，即的线性组合，即 S(1)=-g(1)+(0)S(0)其中，其中，(0)为待定常数，可以利用为待定常数，可以利用共轭方向与梯共轭方向与梯度之间的关系求得。度之间的关系求得。由由 S(1)T g(1)g(0)=0 有有 -g(1)+(0)S(0)T g(1)g(0)=0 展开，得展开，得-g(1)Tg(1)+g(1)Tg(0)+(0)S(0)Tg(1)-(0)S(0)Tg(0)=0 所以所以 -g(1)Tg(1)-(0)S(0)Tg(0)=0所以所以 (0)=-g(1)Tg(1)/S(0

14、)Tg(0)=g(1)Tg(1)/g(0)Tg(0)=|g(1)|2/|g(0)|2S(1)=-g(1)+|g(1)|2/|g(0)|2 S(0)沿沿S(1)进行一维搜索，得进行一维搜索，得 X(2)=X(1)+(1)S(1)，并计算并计算X(2)点的梯度点的梯度 g(2)，则有，则有S(1)Tg(2)=0 故有故有 -g(1)+(0)S(0)T g(2)=0 （6）因为因为S(0)和和S(1)共轭，所以有共轭，所以有S(0)T g(2)g(1)=0 因为因为 S(0)T g(1)=0 所以所以 S(0)T g(2)=0 即即 g(2)与与g(0)正交。正交。所以所以 S(0)T g(2)=0

15、 由式（由式（6）得）得 g(1)T g(2)=0 可见，可见，g(0)、g(1)、g(2)构成一个空间正交系。构成一个空间正交系。3）在）在g(0)、g(1)、g(2)构成的空间正交系中求与构成的空间正交系中求与S(0)及及S(1)均共轭的方向均共轭的方向S(2)，以此作为下一步迭代，以此作为下一步迭代计算的搜索方向。仍取计算的搜索方向。仍取S(2)为为g(0)、g(1)、g(2)的线的线性组合，即性组合，即 S(2)=-g(2)+(1)g(1)+(0)g(0)其中，其中，(1)、(0)为待定常数，可以利用为待定常数，可以利用共轭方共轭方向与梯度之间的关系求得。向与梯度之间的关系求得。S(2

16、)T g(1)g(0)=0 S(2)T g(2)g(1)=0 即即 -g(2)+(1)g(1)+(0)g(0)T g(1)g(0)=0 -g(2)+(1)g(1)+(0)g(0)T g(2)g(1)=0 所以所以 (1)g(1)Tg(1)-(0)g(0)T g(0)=0 -g(2)T g(2)-(1)g(1)Tg(1)=0 令令 (1)=-(1)得得 (1)=-(1)=g(2)T g(2)/g(1)Tg(1)=|g(2)|2/|g(1)|2 (0)=(1)g(1)T g(1)/g(0)Tg(0)=-(1)(0)因此因此 S(2)=-g(2)+(1)g(1)+(0)g(0)=-g(2)-(1)g

17、(1)-(1)(0)g(0)=-g(2)+(1)-g(1)-(0)g(0)=-g(2)+(1)S(1)故故 S(2)=-g(2)+|g(2)|2/|g(1)|2 S(1)再沿再沿S(2)进行一维搜索，得进行一维搜索，得 X(3)=X(2)+(2)S(2)，如此继续下去，可以求得共轭方向的递推公式如此继续下去，可以求得共轭方向的递推公式为为 S(k+1)=-g(k+1)+|g(k+1)|2/|g(k)|2 S(k)(k=0,1,2,n-1)沿着这些共轭搜索方向一直搜索下去，直沿着这些共轭搜索方向一直搜索下去，直到最后迭代点处梯度的模小于给定的允许值为到最后迭代点处梯度的模小于给定的允许值为止。若

18、目标函数为非二次函数，经止。若目标函数为非二次函数，经n次搜索还未次搜索还未达到最优点时，则以最后得到的点作为初始点，达到最优点时，则以最后得到的点作为初始点，重新计算共轭方向，一直到满足精度要求为止。重新计算共轭方向，一直到满足精度要求为止。共轭梯度法的计算步骤及算法框图共轭梯度法的计算步骤及算法框图 1）给定初始点）给定初始点X(0)及收敛精度及收敛精度 0，k=0；2）取）取 S(0)=f(X(0)；3）X(k+1)=X(k)+(k)S(k)(k=0,1,2,n)(k)为一维搜索所得的最佳步长。为一维搜索所得的最佳步长。4）判断判断|f(X(k+1)|?若满足，则输出若满足，则输出 X*

19、=X(k+1)和和 f*=f(X*)否则，转下一步；否则，转下一步；5）判断判断 k+1=n?若若 k+1=n，令，令X(0)=X(k+1)，转，转 2）；）；若若 k+1n，则计算，则计算 (k)=|f(X(k+1)|2/|f(X(k)|2 S(k+1)=-f(X(k+1)+(k)S(k)并令并令 k k+1，转，转3）。）。1）尽管理论上可以证明目标函数为）尽管理论上可以证明目标函数为n维正定维正定二次函数时，共轭梯度法只需要二次函数时，共轭梯度法只需要n次迭代就可以次迭代就可以达到最优点，但由于计算机的舍入误差，实际达到最优点，但由于计算机的舍入误差，实际计算往往要多进行若干次才能得到满

20、足精度要计算往往要多进行若干次才能得到满足精度要求的结果；而对于一般的目标函数，迭代次数求的结果；而对于一般的目标函数，迭代次数将更多。将更多。关于共轭梯度法的说明关于共轭梯度法的说明 2）由于）由于n维设计空间中最多只能有维设计空间中最多只能有n个个线性无关的向量，所以线性无关的向量，所以n维优化问题的共轭维优化问题的共轭方向最多只有方向最多只有n个。因此，共轭梯度法进行个。因此，共轭梯度法进行n步搜索后，若仍不满足精度要求，继续产步搜索后，若仍不满足精度要求，继续产生共轭方向生共轭方向S(n+1)进行迭代搜索是没有意义进行迭代搜索是没有意义的（效果很差），而应令的（效果很差），而应令X(0

21、)=X(n)，重新，重新开始新一轮的共轭梯度法迭代搜索。实践开始新一轮的共轭梯度法迭代搜索。实践证明，这样处理一般都可以取得较好的效证明，这样处理一般都可以取得较好的效果。果。举例：举例：用共轭梯度法求目标函数用共轭梯度法求目标函数 f(X)=x12+4x22 的无约束最优解。初始的无约束最优解。初始点点X(0)=2 2 T，=0.01。解：解：f(X)=2x1 8x2 TS(0)=-f(X(0)=-4 -16 T X(1)=X(0)-(0)f(X(0)=2 2 T-(0)4 16T =2-4(0)2-16(0)T f(X(1)=(2-4(0)2+4(2-16(0)2据据 df(X(1)/d(

22、0)=0 得得 (0)=0.13076923 X(1)=1.476923077 -0.09230768 T f(X(1)=2.953846154 -0.73846144 T(0)=|f(X(1)|2/|f(X(0)|2 =0.034082837 S(1)=-f(X(1)+(0)S(0)=-2.953846154 -0.73846144 T +0.034082837-4 -16 T =-3.09017751 0.193136016 TX(2)=X(1)+(1)S(1)=1.476923077 -0.09230768 T +(1)-3.09017751 0.193136016 T据据 df(X(2

23、)/d(1)=0 得得 (1)=0.477941179 X(2)=610-9 -2.410-8 T 0 0T|f(X(2)|0 0，k=0；2）置）置 k=0，A(0)=I；3）沿搜索方向）沿搜索方向 S(k)=-A(k)f(X(k)作一维作一维搜索，得搜索，得 X(k+1)=X(k)+(k)S(k)；4）计算）计算 g(k+1)=f(X(k+1)若若|g(k+1)|，则输出最优解：，则输出最优解：X*=X(k+1)f*=f(X*)X(k)否则，转否则，转 5）；）；5）若）若 k=n，则，则 X(0)=X(k+1)，转，转 2）；）；若若 k n，转，转 6）；）；6）计算）计算 X(k)=X(k+1)-X(k)g(k)=g(k+1)-g(k)A(k)=(X(k)X(k)T)/(X(k)T g(k)-(A(k)g(k)g(k)T A(k)/(g(k)T A(k)g(k)A(k+1)=A(k)+A(k)令令 k k+1，转，转3）。）。