1、机械优化设计机械优化设计太原科技大学张学良第1页，共40页。第五章 无约束优化的间接搜索法 间搜索法是指搜索方向间搜索法是指搜索方向S(k)的构建利的构建利用目标函数的一阶或二阶导数信息的无用目标函数的一阶或二阶导数信息的无约束优化方法，如梯度法、牛顿法、共约束优化方法，如梯度法、牛顿法、共轭梯度法、变尺度法。轭梯度法、变尺度法。X(k+1)=X(k)+(k)S(k)(k=0,1,2,)第2页，共40页。基本思想基本思想 5.1 梯度法梯度法（最速下降法、负梯度法）（最速下降法、负梯度法）利用负梯度方向作为迭代计算的搜索方向，即利用负梯度方向作为迭代计算的搜索方向，即S(k)=f(X(k)或或
2、 S(k)=f(X(k)/|f(X(k)|迭代计算公式迭代计算公式 X(k+1)=X(k)+(k)f(X(k)或或 X(k+1)=X(k)+(k)f(X(k)第3页，共40页。举例：举例：用梯度法求目标函数用梯度法求目标函数 f(X)=x12+4x22 的无约束最优解。初始点的无约束最优解。初始点X1(0)=0 0 T，X2(0)=2 2 T。第4页，共40页。基本思想和基本算法基本思想和基本算法 5.2 牛顿法牛顿法 在点在点X(k)的邻域内，用一个二次函数的邻域内，用一个二次函数(X)来来近似代替原目标函数，并以近似代替原目标函数，并以 (X)的极小点作为的极小点作为原目标函数的极小点的近
3、似值，若不满足收敛原目标函数的极小点的近似值，若不满足收敛精度要求，则将该近似极小点作为下一次迭代精度要求，则将该近似极小点作为下一次迭代的初始点。如此反复迭代，直到所求的近似极的初始点。如此反复迭代，直到所求的近似极小点满足收敛精度要求为止。小点满足收敛精度要求为止。第5页，共40页。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)正定且有逆阵时，上式两
4、边同时正定且有逆阵时，上式两边同时左乘左乘 2 f(X(k)-1，得得X =X(k)-2 f(X(k)-1 f(X(k)第6页，共40页。牛顿法的迭代公式为牛顿法的迭代公式为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)第7页，共40页。计算步骤及算法框图计算步骤及算法框图 1）任
5、选初始点任选初始点 X(0)，给定收敛精度，给定收敛精度 0，k=0；2）计算计算X(k)点的梯度点的梯度 f(X(k)及其模；及其模；3）检验终止条件：检验终止条件：|f(X(k)|？若满足，则输出最优解：若满足，则输出最优解：X*=X(k)，f*=f(X*)，并终止迭代计算，并终止迭代计算；否则，继续下一步迭代计算；否则，继续下一步迭代计算；第8页，共40页。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、；6）令）令X(k+1)=X(k)+(k)S(k)，并令，并令k k+1，转，转2），重复上述迭代计算过程。），重复上述迭代计算过程。第9页，共40页。举例：举例：用牛顿法求目标函数用牛顿法求目标函数 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
7、 T 第10页，共40页。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)=0 0 T 就是目标函数就是目标函数的理论极小点，仅仅迭代了一次，与初始点的的理论极小点，仅仅迭代了一次，与初始点的选择无关。选择无关。由于一般函数在极小点附近呈现出较强的由于一般函数在极小点附近呈现出较强的二次性，所以牛顿法在极小点附近收敛速度较二次性，所以牛顿法在极小点附近收敛速度较快。但无论是牛顿法还是修正牛顿法在每次迭快。但无论是牛顿法还是修正牛顿法在每次迭代 计 算 时 都 要 计 算 目 标 函 数
8、的 海 赛代 计 算 时 都 要 计 算 目 标 函 数 的 海 赛第11页，共40页。矩阵及其逆阵，因此计算工作量很大，特别是矩阵及其逆阵，因此计算工作量很大，特别是矩阵求逆，当维数高时工作量更大，且当海赛矩阵求逆，当维数高时工作量更大，且当海赛矩阵为奇异阵时，其逆阵不存在，无法使用牛矩阵为奇异阵时，其逆阵不存在，无法使用牛顿法，所以在实际使用中受到一定限制。另外，顿法，所以在实际使用中受到一定限制。另外，从计算机存储方面考虑，牛顿法所需要的存储从计算机存储方面考虑，牛顿法所需要的存储量是很大的。量是很大的。若能设法构造一个矩阵来逼近海赛矩阵的逆阵若能设法构造一个矩阵来逼近海赛矩阵的逆阵而避
9、免计算海赛矩阵及其逆阵，这样的方法统称为而避免计算海赛矩阵及其逆阵，这样的方法统称为拟牛顿法。如只用梯度信息但比梯度法快的共轭梯拟牛顿法。如只用梯度信息但比梯度法快的共轭梯度法，以及针对牛顿法提出的变尺度法等。度法，以及针对牛顿法提出的变尺度法等。第12页，共40页。基本思想基本思想5.3 共轭梯度法共轭梯度法 共轭梯度法属于共轭方向法中的一种方法。共轭梯度法属于共轭方向法中的一种方法。它是利用目标函数在迭代点它是利用目标函数在迭代点X(k)的梯度来构造共的梯度来构造共轭搜索方向的，具有二次收敛性。轭搜索方向的，具有二次收敛性。共轭梯度法搜索的第一步沿负梯度方向，以共轭梯度法搜索的第一步沿负梯
10、度方向，以后各步沿与上次搜索方向相共轭的方向进行搜索。后各步沿与上次搜索方向相共轭的方向进行搜索。共轭梯度法的关键是如何在迭代过程中不断生成共轭梯度法的关键是如何在迭代过程中不断生成共轭搜索方向共轭搜索方向第13页，共40页。共轭梯度法共轭搜索方向的生成共轭梯度法共轭搜索方向的生成 考虑二次函数考虑二次函数 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)两点处的梯度表示并记作两点处的梯度表
11、示并记作 g(k)=f(X(k)=H X(k)+B （2）g(k+1)=f(X(k+1)=H X(k+1）+B （3）第14页，共40页。（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)=(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)进行一维搜
12、索，其终点进行一维搜索，其终点X(k+1)与始点与始点X(k)梯 度 之 差梯 度 之 差(g(k+1)g(k)与与 S(k)的 共 轭的 共 轭第15页，共40页。方向方向S(j)与正交。共轭梯度法就是利用这个性质与正交。共轭梯度法就是利用这个性质做到不必计算矩阵做到不必计算矩阵H就能求得共轭方向的。就能求得共轭方向的。1）设初始点）设初始点X(0)，第一个搜索方向，第一个搜索方向S(0)取取X(0)点的点的负梯度方向负梯度方向-g(0)。即。即 S(0)=-g(0)沿沿S(0)进行一维搜索，得进行一维搜索，得 X(1)=X(0)+(0)S(0)，并，并计算计算X(1)点的梯度点的梯度 g(
13、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)构成平面正交系。构成平面正交系。第16页，共40页。2）在）在S(0)与与g(1)构成的平面正交系中求构成的平面正交系中求S(0)的共轭的共轭方向方向S(1)，以此作为下一步迭代计算的搜索方向。取，以此作为下一步迭代计算的搜索方向。取S(1)为为S(0)与与g(1)的线性组合，即的线性组合，即 S(1)=-g(1)+(0)S(0)其中，其中，(0)为待定常数，可以利用为待定常数，可以利
14、用共轭方向与梯度之共轭方向与梯度之间的关系求得。间的关系求得。由由 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 第17页，共40页。所以所以 -g(1)Tg(1)-(0)S(0)Tg(0)=0所以所以 (0)=-g(1)Tg(1)/S(0)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)
15、=X(1)+(1)S(1)，并，并计算计算X(2)点的梯度点的梯度 g(2)，则有，则有S(1)Tg(2)=0第18页，共40页。故有故有 -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 由式（由式（6）得）得 g(1)T g(2)=0 可见，可见，g(0)、g(1)、g(2)构成一个空间正交系。构成一个空间正交系。第19页，共40页。3）在）在g(0)、g(1)
16、、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)T g(1)g(0)=0 S(2)T g(2)g(1)=0第20页，共40页。即即 -g(2)+(1)g(1)+(0)g(0)T g(1)g(0)=0 -g(
17、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)第21页，共40页。因此因此 S(2)=-g(2)+(1)g(1)+(0)g(0)=-g(2)-(1)g(1)-(1)(0)g(0)=-g(2)+(1)-g(1)-(0)g(0)=-g(2)+(1)S(1)故故 S(2)=-g
18、(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)第22页，共40页。沿着这些共轭搜索方向一直搜索下去，直到沿着这些共轭搜索方向一直搜索下去，直到最后迭代点处梯度的模小于给定的允许值为止。最后迭代点处梯度的模小于给定的允许值为止。若目标函数为非二次函数，经若目标函数为非二次函数，经n次搜索还未达到次搜索还未达到最优点时，则以最后
19、得到的点作为初始点，重新最优点时，则以最后得到的点作为初始点，重新计算共轭方向，一直到满足精度要求为止。计算共轭方向，一直到满足精度要求为止。共轭梯度法的计算步骤及算法框图共轭梯度法的计算步骤及算法框图 1）给定初始点）给定初始点X(0)及收敛精度及收敛精度 0，k=0；2）取）取 S(0)=f(X(0)；第23页，共40页。3）X(k+1)=X(k)+(k)S(k)(k=0,1,2,n)(k)为一维搜索所得的最佳步长。为一维搜索所得的最佳步长。4）判断判断|f(X(k+1)|?若满足，则输出若满足，则输出 X*=X(k+1)和和 f*=f(X*)否则，转下一步；否则，转下一步；5）判断判断
20、k+1=n?若若 k+1=n，令，令X(0)=X(k+1)，转，转 2）；）；若若 k+1n，则计算，则计算 (k)=|f(X(k+1)|2/|f(X(k)|2第24页，共40页。S(k+1)=-f(X(k+1)+(k)S(k)并令并令 k k+1，转，转3）。）。1）尽管理论上可以证明目标函数为）尽管理论上可以证明目标函数为n维正定二维正定二次函数时，共轭梯度法只需要次函数时，共轭梯度法只需要n次迭代就可以达到次迭代就可以达到最优点，但由于计算机的舍入误差，实际计算往往最优点，但由于计算机的舍入误差，实际计算往往要多进行若干次才能得到满足精度要求的结果；而要多进行若干次才能得到满足精度要求的
21、结果；而对于一般的目标函数，迭代次数将更多。对于一般的目标函数，迭代次数将更多。关于共轭梯度法的说明关于共轭梯度法的说明第25页，共40页。2）由于）由于n维设计空间中最多只能有维设计空间中最多只能有n个线性无个线性无关的向量，所以关的向量，所以n维优化问题的共轭方向最多只有维优化问题的共轭方向最多只有n个。因此，共轭梯度法进行个。因此，共轭梯度法进行n步搜索后，若仍不步搜索后，若仍不满足精度要求，继续产生共轭方向满足精度要求，继续产生共轭方向S(n+1)进行迭代进行迭代搜索是没有意义的（效果很差），而应令搜索是没有意义的（效果很差），而应令X(0)=X(n)，重新开始新一轮的共轭梯度法迭代搜
22、，重新开始新一轮的共轭梯度法迭代搜索。实践证明，这样处理一般都可以取得较好索。实践证明，这样处理一般都可以取得较好的效果。的效果。第26页，共40页。举例：举例：用共轭梯度法求目标函数用共轭梯度法求目标函数 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(0)=0 得得 (0)=0
23、.13076923 X(1)=1.476923077 -0.09230768 T 第27页，共40页。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第28页，共40页。据据
24、 df(X(2)/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）；）；第39页，共40页。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）。）。第40页，共40页。
