第四章-无约束最优化方法课件.ppt

1、 4.1 4.1 最速下降法最速下降法问题提出问题：在点kx处，沿什么方向,kd xf下降最快?分析：0kkTkkkkdodgxfdxf考查：coskkkTkdgdg显然当1cos时，kTkdg取极小值因此：kkgd结论：负梯度方向使 xf下降最快，亦即最速下降方向最速下降法算法Step1:给出0:,10,0kRxnStep2:计算,kxf如果,kxf停Step3:计算下降方向.kkgdStep4:计算步长因子.kStep5:令,1kkkkdxx转步.分析：设 cxbGxxxfTT21是正定二次函数,由精确的线搜索确定的?kkTkkTkkGdddg特别当：kkgdkTkkTkkGgggg例1：

2、用最速下降法求解：Txxxxf1,92921min02221解：TxxGxxxg0,090019*21TTxfgx9,91,90008.02.70000001gGggggxxTT2.72.71g22211111128.018.09gGggggxxTT,2,1,8.019kxkkk分析：(1)8.0limlim1*1kkkkkkxxxxxx因此：最速下降法是整体收敛的，且是线性收敛的(2)两个相邻的搜索方向是正交的02.7,2.79,91010ddddTTT收敛性分析定理1:设 xf在0 xfxfRxLn上存在且一致连续，则最速下降法产生的序列满足或者对某个k有,0kg或者,kxf.0kg证明：

3、对于最速下降法，,0k由以上定理立得收敛性分析定理2:设 xf二次连续可微，且,2Mxf其中M是个正常数，对任何给定的初始点,0 x最速下降算法或有限终止，或者,limkkxf或者.0limkkg证明：用以上的结论：2121kkkgMxfxf最速下降法优点(1)程序设计简单，计算量小，存储量小，对初始点没有特别要求(2)有着很好的整体收敛性，即使对一般的目标函数，它也整体收敛最速下降法缺点(1)最速下降法是线性收敛的，并且有时是很慢的线性收敛原因：kkgd仅反映 xf在kx处的局部性质,01kTkdg相继两次迭代中搜索方向是正交的小结(1)最速下降法是基本算法之一，而非有效的实用算法最速下降法

4、的本质是用线性函数来近似目标函数，要想得到快速算法，需要考虑对目标函数的高阶逼近 4.2 4.2 牛顿法牛顿法基本思想利用目标函数 xf在点kx处的二阶Taylor展开式去近似目标函数，用二次函数的极小点去逼近目标函数的极小点算法构造问题：设 xf二阶连续可微，,nkRx ,kkxfg海色阵 kkxfG2正定如何从?1kkxx kTkkkkkxxgfxqxxxfxfkkTkxxGxx21因为kG正定，则 xqk有唯一极小点，用这个极小点作为.1kx所以要求：01kkxq即：01kkkkgxxGkkkkgGxx11因此：这就是牛顿法迭代公式注：这里.,11kkkkgGd牛顿法算法Step1:给出

5、0:,10,0kRxnStep2:计算,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,元素 则当0 x充分靠近*x时，对于一切,k牛顿迭代

6、有意义，迭代序列kx收敛到,*x并且具有二阶收敛速度牛顿法优点(1)(2)对正定二次函数，迭代一次就可以得到极小点如果*G正定且初始点选取合适，算法二阶收敛牛顿法缺点(1)(2)对多数问题算法不是整体收敛的每次都需要计算,kG计算量大(3)每次都需要解;kkgdG方程组有时奇异或病态的，无法确定,kd或kd不是下降方向(4)收敛到鞍点或极大点的可能性并不小阻尼牛顿法算法Step1:给出0:,10,0kRxnStep2:计算,kxf如果,kxf停Step3:否则计算,kGStep4:沿并且求解方程,kkgdG得出.kdkd进行线搜索，得出.kStep5:令,1kkkkdxx转Step2.阻尼牛顿

7、法收敛定理定理2:设 xf二阶连续可微，又设对任意的,0nRx 存在常数,0m使得 xf在 0 xfxfxL上满足：022,xLxRmxfnT则在精确线搜索条件下，阻尼牛顿法产生的点列 kx满足：(1)当 kx是有限点列时，其最后一个点为 xf的唯一极小点(2)当 kx是无限点列时，收敛到 xf的唯一极小点阻尼牛顿法收敛定理定理3:设 xf二阶连续可微，又设对任意的,0nRx 存在常数,0m使得 xf在 0 xfxfxL上满足：022,xLxRmxfnT则在Wolfe不精确线搜索条件下，阻尼牛顿法产生的点列 kx满足：0limkkxf且 kx收敛到 xf的唯一极小点例2：用阻尼牛顿法求解：Tx

8、xxxxxf0,01min0222141解：21102000Gg显然0G不是正定的，但：011210G于是，020100gGd沿方向0d进行线搜索，,116400dxf得其极小点.00从而迭代不能继续下去带保护的牛顿法算法给出0:,210kRxnStep1:kG若为奇异的，转Step8，否则，Step2:令,1kkkgGdStep3:若,1kkkTkdgdg为奇异的，转Step8，否则，则转Step8，否则，Step4:若,1kkkTkdgdg则转Step9，否则，Step5:沿方向kd进行线搜索，求出,k并令.1kkkkdxxStep6:若,21kg停；Step7:令,1 kk转Step1；

9、Step8:令,kkgd转Step5；Step9:令,kkdd转Step5.例3：用带保护的牛顿法求解：Txxxxxxf0,01min0222141解：21102000Gg显然0G不是正定的，但：011210G于是，020100gGd因为，,000dgT故令，,2000gd沿0d进行线搜索得：,2100,1011xfx第二次迭代：2110,0111Gg而：121111gGd使,0211dgT故令 12121d沿1d进行线搜索，得出,3479422.01于是:5824451.03479422.16958844.022xfx此时:01073.072gGill-Murray稳定牛顿法当kG正定时，总

10、有Cholesky分解：TkkkkLDLG当kG不是正定时，Gill-Murray(1974)提出了强迫正定的修改Cholesky分解，使得：,kkTkkkkEGLDLG其中kE是对角阵 然后解：,kTkkkkgdLDLdG问题1:如何建立有效的算法？从二次模型到一般模型问题2:什么样的算法有效呢？二次终止性 4.3 4.3 共轭方向法共轭方向法与共轭梯度法与共轭梯度法算法特点（）建立在二次模型上，具有二次终止性（）有效的算法，克服了最速下降法的慢收敛性，又避免了牛顿法的计算量大和局部收性的缺点（）算法简单，易于编程，需存储空间小等优点，是求解大规模问题的主要方法共轭方向及其性质定义1:设md

11、dd,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共轭，则.0v共轭方向法算法Step1:给出0:,10,0kRxn计算00 xgg和初始下降方向.0dStep2:如果,kg停止迭代Step3:计算,1kkx使得.1kkkkdxxStep4:采用某种共轭方向法计

12、算1kd使得：.,1,0,01kjGddjTkStep5:令,1:kk转Step2.共轭方向法基本定理定义2:设n维向量组kddd,21线性无关，,1nRx 向量集合kiiiikRdxH111为1x与kddd,21生成的k维超平面引理1:设 xf是连续可微的严格凸函数，n维向量组kddd,21线性无关，,1nRx 则：ikiikdxx111是 xf在kH上唯一极小点的充要条件是：kidgiTk,2,1,01h证：构造：kiiikdxfh1121,分析：是(1)k维严格凸函数(2)1kx是 xf在kH上的极小点的充要条件是Tk,21是kh,21在kR上的极小点定理2:设G为n阶正定阵，向量组kd

13、dd,21关于G共轭，对正定二次函数,21cxbGxxxfTT由任意1x开始，依次进行k次精确线搜索：,2,1,1kidxxiiii则：（）kidgiTk,2,1,01（）1kx是 xf在kH上的极小点推论:当nk 时，1nx为正定二次函数在nR上的极小点共轭梯度法记：11kkkkdgd左乘,1GdTk 并使1111kTkkTkkGddGdg,01kTkdGd得：（Hestenes-Stiefel公式）取：00gd共轭梯度法基本性质定理3:对于正定二次函数，采用精确线搜索的共轭梯度法在nm 步后终止，且对ni 1成立下列关系式：,1,1,0,0ijGddjTi,1,1,0,0ijggjTi,i

14、TiiTigggd,1,1,00ijdgjTi（共轭性）（正交性）（下降条件）系数的其他形式（）FR公式111kTkkTkkgggg（1964）（2）PRP公式1111kTkkkTkkggggg（1969）FR共轭梯度法算法Step1:给出0:,10,0kRxnStep2:计算,kkxfg如果,kg停Step3:11kkkkdgd101111kkggggkTkkTkkStep4:由精确线搜索求.kStep5:,1,1kkdxxkkkk转Step2.例4：用FR共轭梯度法求解：Txxxxxxxf4,222123min01212221解：化成 cxbGxxxfTT21形式 2121210,2111

15、3,21xxxxxxxf 420 x 61200bGxg(1)6120d17500000GdddgTT173817260001dxx171217611bGxg789.01g(2)289100110ggggTT289210289900011dgd171011111GdddgTT111112dxx02g112*xx例5：用FR共轭梯度法求解：TTdxxxxf0,11,12121min002221解：化成 cxbGxxxfTT21形式 21211001,21xxxxxf110 x1100bGxg(1)010d100000GdddgTT100001dxx1011bGxg11g(2)2100110ggg

16、gTT1210011dgd5411111GdddgTT51521112dxxFR共轭梯度法收敛定理定理4:假定 xf在有界水平集 0 xfxfRxLn上连续可微，且有下界，那么采用精确线搜索下的FR共轭梯度法产生的点列kx至少有一个聚点是驻点，即：(1)当kx是有穷点列时，其最后一个点是 xf的驻点(2)当kx是无穷点列时，它必有聚点，且任一聚点都是 xf的驻点再开始FR共轭梯度法算法Step1:给出0:,10,0kRxnStep2:计算,00 xfg如果,0g停，Step4:否则.00gdStep3:由精确线搜索求,k并令：.1,1kkdxxkkkk计算,kkxfg若,1.021kkTkgg

17、g令,:0kxx转Step2;如果,kg停.Step5:若,nk 令,:0kxx转step2.Step6:计算11111,kkkkkTkkTkkdgdggggStep7:如果,0kTkgd令,:0kxx转step2,否则转step3.作业：FR共轭梯度法（上机）上机实现FR共轭梯度法并求解Rosenbrock函数，初始点选,1,2.10Tx线搜索分别采用黄金分割法与强Wolfe线搜索，并对比 4.4 4.4 拟牛顿法拟牛顿法基本思想本质上是基于逼近牛顿法的方法牛顿法每次都计算,kG1959年,Davidon提出设想仅用每次迭代中得到的梯度信息来近似海色阵，基于此导致了一类非常成功的拟牛顿法本节

18、介绍Broyden族拟牛顿法：DFP算法和BFGS算法算法原理最速下降法和阻尼牛顿法的迭代公式可统一为：kkkkkgHxx1思考：要使上面的算法比最速下降法快，比牛顿法计算简单，且整体收敛性好，关键在于构造矩阵列.kH要求：kH的选取既能逐步逼近,1kG又无需计算二阶导数，且具备以下条件：C1：kH是对称正定阵C2：1kH由kH经简单修正而得：kkkEHH1C3：kH满足下面的拟牛顿方程（推导如下）设 xf是二次连续可微的，11111121kkTkkTkkxxGxxxxgxfxf 111kkkxxGgxg令：,kxx则：kkkkkggxxG111令：kkkkkkggyxxs11,因此：kkky

19、sG1（对二次函数为等式）若11kG非奇异：kkksyG11设想：kkksyH1（拟牛顿方程）这样1kH就可很好的近似.11kG拟牛顿算法Step1:给出0:,10,00kHRxnStep2:计算,0gStep3:kkkgHdStep4:精确线搜索求.kStep5:kkkkdxx1Step6:计算,1kg若,1kg停；否则转Step7.Step7:校正,1kkHH使拟牛顿方程成立Step8:,1 kk转Step3.DFP校正公式kkkEHH1TTkvvuuEvu,是n维待定向量要求：kkksyH1所以：kkTkTkksyvvyuuyH令：kkkyHvsu,得：11kTkTyvyu因此：kkTk

20、kTkTkkTyHyyvsyyu1111所以：kTkTkkkkTkkTkkkkksyssyHyHyyHHH1（DFP校正公式）例6：用DFP算法求解：1212221422minxxxxxxf40010100111Hx取解：4222424222121xGxxxxxg(1)24240000gHdg 32040200dxf 4100215.0210001gdxx435.01010010ggyxxs4138388410010000000000001syssyHyHyyHHHTTTT(2)6851111gHd 4505.5458122400242*21112xxgdxx注:（）DFP算法具有二次终止性（

21、）搜索方向是共轭方向：565824422210ddG010GddTDFP校正公式的正定继承性引理2:设,syssHyyHHyyHHTTTTH为正定阵，nnRsRy,且,0,0sy则：H为正定阵的充要条件是.0syT定理5:在DFP算法中，如果0H正定，则整个矩阵列kH都正定DFP算法的二次终止性推论:在上面定理条件下：（1）DFP算法至多经过n次迭代就可得到极小点，即存在nkk0有：.*xxk（2）若,10,*nkxxk则.1 GHnBFGS校正公式kkkysB1kkTkkTkkkkTkTkkkksBsBssBsyyyBB1(称为关于kB的BFGS校正公式或互补DFP公式)由上式可得：1970

22、)(1kTkTkkkTkTkkkTkTkkBFGSKysssyssyIHysysIHkkTkTkkkTkTkkkkTkTkkDFPKsyyysyysIHsysyIB)(1对称秩一校正公式kkkEHH1TkuvE要求：kkksyH1要求Hesse逆近似也是对称的，kkTkksyuvyH即：kkkkTyHsuyvTkkkkTkkvyHsyvHH11取：kkkyHsvkTkkkTkkkkkkkkyyHsyHsyHsHH1因此：注:（1）通常不能保证（2）分母可能取零,修正公式不再有意义kH的正定性（3）逼近1kG程度高，近来用于信赖域算法，取得了很好的效果Broyden族kkTkkkkTkkkkTkkyHyyHyssyHyv2/1取BFGSkDFPkkHHH111119671TkkkkTkkTkkkkTkTkkkkvvyHyHyyHysssHH注：,0得DFP校正注：,1得BFGS校正,kTkkkkTkyyHsys得对称秩一校正其中：Broyden族算法性质定理6:设 xf在nR上连续可微，给定,00Hx在精确线搜索下，由Broyden族算法产生的点列kx与参数无关结论：可将DFP算法的性质推广到整个Broyden族作业(1)用FR共轭梯度法求解：552min02221xxxxf(2)用DFP算法求解：12242min012221xxxxxf