优化设计-牛顿法 变变尺度法.pdf

《优化设计-牛顿法 变变尺度法.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2.常见的优化方法介绍2.1牛顿法2.2变尺度法2.3（Powell）法2.4鲍威尔修正算法2.5共轭梯度法2.6单纯形法2.1牛顿法2.1.1基本思想和基本算法在点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

2、(X(k))+2f(X(k))(X-X(k))=02f(X(k))(X-X(k))=-f(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))阻

3、尼因子：(k)2.1.2计算步骤及算法框图1）任选初始点X(0)，给定收敛精度>0，k=0；2）计算X(k)点的梯度f(X(k))及其模；3）检验终止条件：

4、

5、f(X(k))

6、

7、≤？若满足，则输出最优解：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），重复上述迭代计算过程。开始

8、选定X0ff(X)00gg(X)00GG(X)Newton0法的流求解方程GPg0XX程图0f0fXXP0gg0ff(X)gg(X)NH准则满足YX,f结束Newton法22例试用Newton法求f(x1，x2)x14x2的极小点,初始点取为X[1,1]．T0Tg(X)f(X)[2x，8x].解:梯度为12200.50Hesse矩阵为G(X)其逆矩阵为G(X)10800.125由迭代公式得第1迭代点为110.5020XXGX()gX()．100010

9、0.12580由于此时

10、

11、f(X)

12、

13、0106，停止迭代得X*X[0,0]T11因此，它就是极小点．2.1.3Newton法有关说明Newton法收敛速度非常快具有二次收敛的优点，但它存在下面四个严重的缺点：（1）尽管每次迭代不会使目标函数f(X)上升，但仍不能保证f(X)下降．当Hesse矩阵非正定时，Newton法的搜索将会失败．（2）对初始点要求严格．一般要求比较接近或有利于接近极值点，而这在实际计算中是比较难办的．（3）在进行某次迭代时可能求不出搜索方向．由于搜索方向为P[2f(X)]12f(X)kkk若目标函数在X点Hesse

14、矩阵为奇异，则求不出[2f(X)]1，因而不有构kk成牛顿方向，从而使迭代无法进行．（4）牛顿方向构造困难，计算相当复杂，除了求梯度以外还需计算Hesse矩阵及其逆矩阵，占用机器内存相当大．2.2变尺度法它是基于牛顿法的思想，并对其做了重要的改进后的一类方法。它不需要计算二阶导数矩阵及其逆阵，又比共轭梯度法有更好的收敛性，对较高维数的无约束优化问题有明显的优越性。2.2.1DFP变尺度法的基本思想梯度法远离最优点时，对突破函数的非二次性极为有利（即收敛速度快），但迭代点接近最优点时收敛速度慢；而牛顿法则正好相反，它具有二次收敛性，接近最优点时收敛极快，但它需要计

15、算海赛矩阵及其逆阵，计算工作量比梯度法大为增加。若能构造一种算法，它兼有梯度法和牛顿法各自的优点，那么这种算法一定比梯度法和牛顿法更有效，于是便产生了变尺度法。梯度法：X(k+1)=X(k)-(k)f(X(k))牛顿法：X(k+1)=X(k)-(k)[2f(X(k))]-1f(X(k))变尺度法的迭代公式:X(k+1)=X(k)-(k)A(k)f(X(k))A(k)为人为构造的对称方阵，称为构造矩阵，它迭代点位置的变化而变化。变尺度法的迭代公式:X(k+1)=X(k)-(k)A(k)f(X(k))若在迭代初始时，A(k)=I，则上式与梯度法的迭