第四章-无约束最优化方法

第四章无约束最优化方法§4.1最速下降法问题提出问题：在点kx处，沿什么方向,kdxf下降最快?分析：0kkTkkkkdodgxfdxf考查：coskkkTkdgdg显然当1cos时，kTkdg取极小值．因此：kkgd结论：负梯度方向使xf下降最快，亦即最速下降方向．最速下降法算法Step1:给出0:,10,0kRxnStep2:计算,kxf如果,kxf停．Step3:计算下降方向.kkgdStep4:计算步长因子.kStep5:令,1kkkkdxx转步２.分析：设cxbGxxxfTT21是正定二次函数,由精确的线搜索确定的?kkTkkTkkGdddg特别当：kkgdkTkkTkkGgggg例1：用最速下降法求解：Txxxxf1,92921min02221解：TxxGxxxg0,090019*21TTxfgx9,91,90008.02.70000001gGggggxxTT2.72.71g22211111128.018.09gGggggxxTT,2,1,8.019kxkkk分析：(1)8.0limlim1**1kkkkkkxxxxxx因此：最速下降法是整体收敛的，且是线性收敛的．(2)两个相邻的搜索方向是正交的．02.7,2.79,91010ddddTTT收敛性分析定理1:设xf在0xfxfRxLn上存在且一致连续，则最速下降法产生的序列满足或者对某个k有,0kg或者,kxf.0kg证明：对于最速下降法，,0k由以上定理立得．收敛性分析定理2:设xf二次连续可微，且,2Mxf其中M是个正常数，对任何给定的初始点,0x最速下降算法或有限终止，或者,limkkxf或者.0limkkg证明：用以上的结论：2121kkkgMxfxf最速下降法优点(1)程序设计简单，计算量小，存储量小，对初始点没有特别要求．(2)有着很好的整体收敛性，即使对一般的目标函数，它也整体收敛．最速下降法缺点(1)最速下降法是线性收敛的，并且有时是很慢的线性收敛．原因：①kkgd仅反映xf在kx处的局部性质．②,01kTkdg相继两次迭代中搜索方向是正交的．小结(1)最速下降法是基本算法之一，而非有效的实用算法．最速下降法的本质是用线性函数来近似目标函数，要想得到快速算法，需要考虑对目标函数的高阶逼近．§4.2牛顿法基本思想利用目标函数xf在点kx处的二阶Taylor展开式去近似目标函数，用二次函数的极小点去逼近目标函数的极小点．算法构造问题：设xf二阶连续可微，,nkRx,kkxfg海色阵kkxfG2正定．如何从?1kkxxkTkkkkkxxgfxqxxxfxfkkTkxxGxx21因为kG正定，则xqk有唯一极小点，用这个极小点作为.1kx所以要求：01kkxq即：01kkkkgxxGkkkkgGxx11因此：这就是牛顿法迭代公式．注：这里.,11kkkkgGd牛顿法算法Step1:给出0:,10,0kRxnStep2:计算,kxf如果,kxf停．Step3:否则计算,kGStep4:令,1kkkdxx转步２.并且求解方程,kkkgdG得出.kd例1：用牛顿法求解：Txxxxf1,92921min02221解：TxxGxxxg0,090019*21*1010010099900119xgGxx牛顿法收敛定理定理1:设xf二次连续可微，*x是xf的局部极小点，*xf正定．假定xf的海色阵kkxfG2满足Lipschitz条件，即存在,0使得对于所有nji,1有：1,,nijijRyxyxyGxG其中xGij是海色阵kG的ji,元素．则当0x充分靠近*x时，对于一切,k牛顿迭代有意义，迭代序列kx收敛到,*x并且具有二阶收敛速度．牛顿法优点(1)(2)对正定二次函数，迭代一次就可以得到极小点．如果*G正定且初始点选取合适，算法二阶收敛．牛顿法缺点(1)(2)对多数问题算法不是整体收敛的．每次都需要计算,kG计算量大．(3)每次都需要解;kkgdG方程组有时奇异或病态的，无法确定,kd或kd不是下降方向．(4)收敛到鞍点或极大点的可能性并不小．阻尼牛顿法算法Step1:给出0:,10,0kRxnStep2:计算,kxf如果,kxf停．Step3:否则计算,kGStep4:沿并且求解方程,kkgdG得出.kdkd进行线搜索，得出.kStep5:令,1kkkkdxx转Step2.阻尼牛顿法收敛定理定理2:设xf二阶连续可微，又设对任意的,0nRx存在常数,0m使得xf在0xfxfxL上满足：022,,xLxRmxfnT则在精确线搜索条件下，阻尼牛顿法产生的点列kx满足：(1)当kx是有限点列时，其最后一个点为xf的唯一极小点．(2)当kx是无限点列时，收敛到xf的唯一极小点．阻尼牛顿法收敛定理定理3:设xf二阶连续可微，又设对任意的,0nRx存在常数,0m使得xf在0xfxfxL上满足：022,,xLxRmxfnT则在Wolfe不精确线搜索条件下，阻尼牛顿法产生的点列kx满足：0limkkxf且kx收敛到xf的唯一极小点．例2：用阻尼牛顿法求解：Txxxxxxf0,01min0222141解：21102000Gg显然0G不是正定的，但：011210G于是，020100gGd沿方向0d进行线搜索，,116400dxf得其极小点.00从而迭代不能继续下去．带保护的牛顿法算法给出0:,,,210kRxnStep1:kG若为奇异的，转Step8，否则，Step2:令,1kkkgGdStep3:若,1kkkTkdgdg为奇异的，转Step8，否则，则转Step8，否则，Step4:若,1kkkTkdgdg则转Step9，否则，Step5:沿方向kd进行线搜索，求出,k并令.1kkkkdxxStep6:若,21kg停；Step7:令,1kk转Step1；Step8:令,kkgd转Step5；Step9:令,kkdd转Step5.例3：用带保护的牛顿法求解：Txxxxxxf0,01min0222141解：21102000Gg显然0G不是正定的，但：011210G于是，020100gGd因为，,000dgT故令，,2000gd沿0d进行线搜索得：,2100,1011xfx第二次迭代：2110,0111Gg而：121111gGd使,0211dgT故令12121d沿1d进行线搜索，得出,3479422.01于是:5824451.03479422.16958844.022xfx此时:01073.072gGill-Murray稳定牛顿法当kG正定时，总有Cholesky分解：TkkkkLDLG当kG不是正定时，Gill-Murray(1974)提出了强迫正定的修改Cholesky分解，使得：,kkTkkkkEGLDLG其中kE是对角阵．然后解：,kTkkkkgdLDLdG问题1:如何建立有效的算法？从二次模型到一般模型问题2:什么样的算法有效呢？二次终止性§4.3共轭方向法与共轭梯度法算法特点（１）建立在二次模型上，具有二次终止性．（２）有效的算法，克服了最速下降法的慢收敛性，又避免了牛顿法的计算量大和局部收性的缺点．（３）算法简单，易于编程，需存储空间小等优点，是求解大规模问题的主要方法．共轭方向及其性质定义1:设mddd,,,21是nR中任一组非零向量，如果：jiGddjTi,0则称mddd,,,21是关于G共轭的．注：若,IG则是正交的，因此共轭是正交的推广．定理1:设G为n阶正定阵，非零向量组mddd,,,21关于G共轭，则必线性无关．推论1:设G为n阶正定阵，非零向量组nddd,,,21关于G共轭，则向量构成nR的一组基．推论2:设G为n阶正定阵，非零向量组nddd,,,21关于G共轭，若向量v与nddd,,,21关于G共轭，则.0v共轭方向法算法Step1:给出0:,10,0kRxn计算00xgg和初始下降方向.0dStep2:如果,kg停止迭代．Step3:计算,,1kkx使得.1kkkkdxxStep4:采用某种共轭方向法计算1kd使得：.,,1,0,01kjGddjTkStep5:令,1:kk转Step2.共轭方向法基本定理定义2:设n维向量组kddd,,,21线性无关，,1nRx向量集合kiiiikRdxH111为1x与kddd,,,21生成的k维超平面．引理1:设xf是连续可微的严格凸函数，n维向量组kddd,,21线性无关，,1nRx则：ikiikdxx111是xf在kH上唯一极小点的充要条件是：kidgiTk,2,1,01h证：构造：kiiikdxfh1121,,,分析：是(1)k维严格凸函数．(2)1kx是xf在kH上的极小点的充要条件是Tk,,21是kh,,21在kR上的极小点．定理2:设G为n阶正定阵，向量组kddd,,21关于G共轭，对正定二次函数,21cxbGxxxfTT由任意1x开始，依次进行k次精确线搜索：,,2,1,1kidxxiiii则：（１）kidgiTk,2,1,01（２）1kx是xf在kH上的极小点．推论:当nk时，1nx为正定二次函数在nR上的极小点．共轭梯度法记：11kkkkdgd左乘,1GdTk并使1111kTkkTkkGddGdg,01kTkdGd得：（Hestenes-Stiefel公式）取：00gd共轭梯度法基本性质定理3:对于正定二次函数，采用精确线搜索的共轭梯度法在nm步后终止，且对ni1成立下列关系式：,1,,1,0,0ijGddjTi,1,,1,0,0ijggjTi,iTiiTigggd,1,1,00ijdgjTi（共轭性）（正交性）（下降条件）系数的其他形式（１）FR公式111kTkkTkkgggg（1964）（2）PRP公式1111kTkkkTkkggggg（1969）FR共轭梯度法算法Step1:给出0:,10,0kRxnStep2:计算,k