第五讲-无约束最优化方法-拟牛顿法new

《第五讲-无约束最优化方法-拟牛顿法new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、MathematicsLaboratory最优化理论与方法阮小娥博士阮小娥教授Spring2011第三章无约束最优化方法---拟牛顿法最速下降法的优缺点：全局收敛，在初始迭代阶段收敛快，在极小点附近收敛慢；Newton法的优缺点：在极小点附近收敛快，但要求计算目标函数的Hesse阵，计算量大。Trade-off：模仿Newton法---拟Newton法11Newton法k1k2kkxxfxfx1、布鲁丹族拟牛顿法迭代序列k1kkk1kxxd

2、xBkfx该算法称为拟牛顿法或变尺度法。kk1dBkfx称为拟牛顿法方向。加强迭代序列k1kkk1kxxkdxkBkfx,其中，Bk满足Bkk1(1)k是正定对称矩阵，以保证dBkfx为下降方向。(2)Bk1是通过校正Bk而得到，即Bk1BkB.k(3)Bk1满足拟牛顿条件，即k11kkkBk1xxfxfx2拟牛顿条件的合理性Newton法fxqxkTT1

3、qxkkkk2kkkfxfxxxxxfxxx2fxqxk12k1k1即kfxfxxx.k令xx则2kk11kkkfxxxfxfx.令2k1Bk1fx则得拟牛顿条件Bkk11kkkykk1Bk1xxfxfx3Bk1BkBk的对称秩1校正公式Bk

4、BBkykkkk由k1kk得BkkyBTkkkkyBkkyBB对称,令B则kkTkkkyBk且rankBk1.称该公式为对称秩1校正公式。TkkkkyBkkyB则BB.kk1TkkkyBkT条件：yBkkk0kT限制：yBkkkk41TT定理1设fxxGxbxc其中，G是正定对称阵。2

5、k1k1k拟牛顿法迭代序列为：xxBkfx,k01,,.TkkkkyBkkyB其中，Bk1BkB,kBkTkkkyBkkk1kkk1kGkxx,yfxfx满足拟牛顿条件：Bkky,k01,,.k101n1如果,,,线性无关，则至多经过n1次迭代，可求得fx的极小点。且BGn证明：首先，用数学归纳法证明遗传性质：jj

6、yB,j01,,,k1.k00（1）当k1时，拟牛顿条件yB成立15（2）假设当k1时，遗传性质成立。即jjyB,j01,,,k1.kTkkkkyBkkyB对于k,1由BBB,Bk1kkkTkkkyBk得,TkkkkjjyBkkyBjBk1BkTkkkyBk当jk1时TkkjkTTjkjk

7、TTjkjyBkyBkGykTTjkjGG0即Bjjy,jj01,,,k1.成立k1Bk当jk时kkkkTyBkkyBkBkkkk1BkTy成立kkkyBk6其次证BGnfxkkGxb,kk由得yG,k01,,由遗传性质，得ykkB,k01,,n1.nk则GBn0,k

8、01,,n1.01n1由题设,,,线性无关，得BnG.n1n1nnn1从而，xxBnfxxGfx(迭代序列)n11nnnGxxfxfx(拟牛顿条件)n1得，fx0即有限步求得驻点，而且也是极小点。对于二次函数来说，这种具有有限步求得精确解的性质称为二次终止性。