第五章无约束优化的间接搜索法2

《第五章无约束优化的间接搜索法2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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))/

2、

3、▽f(X(k))

4、

5、迭代计算公式X(k+1)=X(k)+(k)[－▽f(X(k))]或X(k+1)=X(k)+(k)[－▽f(X(k))]举例：用梯度法求目标函数f(X)=x12+4x22的无约

6、束最优解。初始点X1(0)=[00]T，X2(0)=[22]T。基本思想和基本算法§5.2牛顿法在点X(k)的邻域内，用一个二次函数(X)来近似代替原目标函数，并以(X)的极小点作为原目标函数的极小点的近似值，若不满足收敛精度要求，则将该近似极小点作为下一次迭代的初始点。如此反复迭代，直到所求的近似极小点满足收敛精度要求为止。f(X)f(X(k))+Tf(X(k))(X-X(k))+0.5(X-X(k))T2f(X(k))(X-X(k))=(X)(X)的极小点应满足：(X)=0即f(X(k))+2f(X(k))(X-X(k))=02f(X(k))(X-X(k))=-f

7、(X(k))当2f(X(k))正定且有逆阵时，上式两边同时左乘[2f(X(k))]-1，得X=X(k)-[2f(X(k))]-1f(X(k))牛顿法的迭代公式为X(k+1)=X(k)-[2f(X(k))]-1f(X(k))X(k+1)=X(k)+(k)S(k)牛顿方向：S(k)=-[2f(X(k))]-1f(X(k))迭代步长：(k)=1修正牛顿法（又称阻尼牛顿法）的迭代公式为X(k+1)=X(k)-(k)[2f(X(k))]-1f(X(k))阻尼因子：(k)计算步骤及算法框图(图4-6)1）任选初始点X(0)，给定收敛精度>0，并置k=0；2）计算X(k)点的

8、梯度f(X(k))及其模；3）检验终止条件：

9、

10、f(X(k))

11、

12、≤？若满足，则输出最优解：X*=X(k)，f*=f(X*)，并终止迭代计算；否则，继续下一步迭代计算；4）计算X(k)点的海赛矩阵2f(X(k))及其逆矩阵[2f(X(k))]-15）沿牛顿方向S(k)=-[2f(X(k))]-1f(X(k))进行一维搜索，求最佳步长(k)；6）令X(k+1)=X(k)+(k)S(k)，并令kk+1，转2），重复上述迭代计算过程。举例：用牛顿法求目标函数f(X)=x12+4x22的无约束最优解。初始点X1(0)=[02]T，X2(0)=[22]T。解：f(X)=[2x18x

13、2]T2f(X)=008[2f(X)]-1=0.5000.125f(X1(0))=[016]Tf(X2(0))=[416]TX1(1)=X1(0)-[2f(X1(0))]-1f(X1(0))=[02]T-0.5000.125[016]T=[00]TX2(1)=X2(0)-[2f(X2(0))]-1f(X2(0))=[22]T-0.5000.125[416]T=[00]T可见，X2(1)=X1(0)=[00]T就是目标函数的理论极小点，仅仅迭代了一次，与初始点的选择无关。由于一般函数在极小点附近呈现出较强的二次性，所以牛顿法在极小点附近收敛速度较快。但无论是牛顿法还是修正牛顿法在

14、每次迭代计算时都要计算目标函数的海赛矩阵及其逆阵，因此计算工作量很大，特别是矩阵求逆，当维数高时工作量更大，且当海赛矩阵为奇异阵时，其逆阵不存在，无法使用牛顿法，所以在实际使用中受到一定限制。另外，从计算机存储方面考虑，牛顿法所需要的存储量是很大的。若能设法构造一个矩阵来逼近海赛矩阵的逆阵而避免计算海赛矩阵及其逆阵，这样的方法统称为拟牛顿法。如只用梯度信息但比梯度法快的共轭梯度法，以及针对牛顿法提出的变尺度法等。举例(作业)：用牛顿法求目标函数f(X)=x12+25x22的无约束最优解。初始点X1(0)=[02]T，X2(0)=[22]T。基本思想§5.3共轭梯度法共轭梯度法属于共轭方向法中的

15、一种方法。它是利用目标函数在迭代点X(k)的梯度来构造共轭搜索方向的，具有二次收敛性。共轭梯度法搜索的第一步沿负梯度方向，以后各步沿与上次搜索方向相共轭的方向进行搜索。共轭梯度法的关键是如何在迭代过程中不断生成共轭搜索方向共轭梯度法共轭搜索方向的生成考虑二次函数f(X)=0.5XTHX+BTX+C从X(k)出发，沿H的某一共轭方向S(k)作一维搜索得到X(k+1)，即X(k+1)－X(k)=(k