资源描述：
《运筹学与最优化方法第5章ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章无约束最优化方法第五章无约束最优化（f）minf(x)f:Rn→R5.1最优性条件设f连续可微必要条件：若x*－l.opt.则▽f(x*)=0(驻点)。当f凸时，x*－l.opt.←→▽f(x*)=0注意：f(x)≥f(x*)+▽Tf(x*)(x-x*),x.故f(x*)≤f(x)，x.（由于▽Tf(x*)=0）5.2最速下降法在迭代点x(k)取方向d(k)=－▽f(x(k))精确一维搜索最速下降法：梯度方向函数值变化最快的方向第五章无约束最优化5.2最速下降法（续）x(1),ε>0,k=1
2、
3、▽f(x(k))
4、
5、<ε?Yesstop.x(k)–解Nod(
6、k)=－▽f(x(k))解minf(x(k)+λd(k))s.t.λ>0得x(k+1)=x(k)+λkd(k)k=k+1第五章无约束最优化5.2最速下降法（续）特点：全局收敛，线性收敛，易产生扭摆现象而造成早停。（当x(k)距最优点较远时，速度快，而接近最优点时，速度下降）原因：f(x)=f(x(k))+▽Tf(x(k))(x-x(k))+o
7、
8、x-x(k)
9、
10、当x(k)接近l.opt.时▽f(x(k))→0，于是高阶项o
11、
12、x-x(k)
13、
14、的影响可能超过▽Tf(x(k))(x-x(k))。5.3Newton法及其修正一、Newton法：设f(x)二阶可微，取f(x
15、)在x(k)点附近的二阶Taylor近似函数：qk(x)=f(x(k))+▽Tf(x(k))(x-x(k))+1／2(x-x(k))T▽2f(x(k))(x-x(k))求驻点：▽qk(x)=▽f(x(k))+▽2f(x(k))(x-x(k))=0第五章无约束最优化Newton法：（续）当▽2f(x(k))正定时，有极小点：x(k+1)=x(k)-[▽2f(x(k))]-1▽f(x(k))——Newton迭代公式实用中常用▽2f(x(k))S=-▽f(x(k))解得s(k)x(k+1)=x(k)+s(k)x(1),ε>0,k=1▽2f(x(k))S=-▽f(x(k))
16、得s(k),x(k+1)=x(k)+s(k)
17、
18、s(k)
19、
20、<ε?STOP.x(k+1)—l.optYesNok=k+1实用中，判断若▽2f(x(k))非正定时进行相应处理第五章无约束最优化Newton法：（续）特点：二阶收敛，局部收敛。（当x(k)充分接近x*时,局部函数可用正定二次函数很好地近似，故收敛很快）二次终结性：当f(x)为正定二次函数时，从任意初始点可一步迭代达到最优解。设f(x)=1／2xTQx+PTx+r,Qn×n对称正定，P∈Rn,r∈R.x(1),▽f(x(1))=Qx(1)+P▽2f(x(1))=Q迭代：x(2)=x(1)-Q–1(Qx(1
21、)+P)=-Q–1P(驻点即opt.)主要缺点：(1)局部收敛(2)用到二阶Hesse阵，且要求正定(3)需计算Hesse阵逆或解n阶线性方程组，计算量大第五章无约束最优化5.3Newton法及其修正二、Newton法的改进：(1)为减小工作量，取m（正整数），使每m次迭代使用同一个Hesse阵，迭代公式变为：x(km+j+1)=x(km+j)-[▽2f(x(km))]-1▽f(x(km+j))j=0,1,2,…,m-1,k=0,1,2,…特点：收敛速度随m的增大而下降m=1时即Newton法，m→∞即线性收敛。(2)带线性搜索的Newton法：在Newton迭代中
22、，取d(k)=-[▽2f(x(k))]-1▽f(x(k)),加入线性搜索：minf(x(k)+λkd(k))求得λk,x(k+1)=x(k)+λkd(k)特点：可改善局部收敛性，当d(k)为函数上升方向时，可向负方向搜索，但可能出现±d(k)均非下降方向的情况。第五章无约束最优化5.3Newton法及其修正二、Newton法的改进：（续）(3)Goldstein-Price方法(G-P法)：取d(k)=-[▽2f(x(k))]-1▽f(x(k))，▽2f(x(k))正定-▽f(x(k))，否则采用下列精确一维搜索：求λk，使其中δ∈(0,1／2)1°f(x(k)+λ
23、kd(k))≤f(x(k))+δ▽f(x(k))Td(k)λk2°f(x(k)+λkd(k))≥f(x(k))+(1-δ)▽f(x(k))Td(k)λk特点：在一定条件下，G-P法全局收敛。但当▽2f(x(k))非正定情况较多时，收敛速度降为接近线性。第五章无约束最优化5.3Newton法及其修正二、Newton法的改进：（续）(4)Levenberg-Marguardt法（L-M法）：主要思想：用[▽2f(x(k))+μI]取代▽2f(x(k))进行迭代，其中I为单位矩阵。μ>0使[▽2f(x(k))+μI]正定，μ尽量小。特点：全局二阶收敛。第五章无约束最优
