第五章 无约束最优化方法
第 五 章 无约束最优化方法
第五章无约束最优化 (f) min flx f:Rn→R 5.1最优性条件 设∫f连续可微 必要条件:若x*-opt则Vx=0(班点 当f凸时,x*-LOp Vfl*=0 注意:f(x)2(x)+V0x)(x),x 故x)≤(x),Vx.(由于x=0) 52最速下降法 在迭代点x取方向d=-Vf(x) 精确一维搜索 最速下降法:梯度方向函数值变化最快的方 向
第五章 无约束最优化 （f） min f(x) f : Rn→R 5.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(,E>0,k=1 k=k+1 Yes ‖V6)|e stop. x-解 =-Vf(x1() 解 (x()+2dy t.1>0 得xk+1=x0+d
第五章 无约束最优化 5.2 最速下降法（续） x (1) , ε >0, k=1 || ▽f(x(k) ) ||< ε? Yes stop. x (k) –解 No d (k)= －▽f(x(k) ) 解 min f(x(k)+λ d(k)) s.t. λ >0 得 x (k+1)=x(k)+λkd (k) k=k+1
第五章无约束最优化 52最速下降法(续) 特点:全局收敛,线性收敛,易产生扭摆现象而造成 早停。 (当x距最优点较远时,速度快,而接近最优点时, 速度下降) 原因:f(x)=x(6)+Vx1)(x)+ol|x-x 当x接近Lop时V(x1)→0,于是高阶项 o|rx61的影购可能超过)(xx 53 Newton法及其修正 Newton法: 设f(x)二阶可微,取(x)在x点附近的二阶ayor近似函数 坐Ax()+Vx1x16+1/2(x-x1)n=x 驻点 qkl)=Vf(rl)+ Vf(x k)(-x(k)
第五章 无约束最优化 5.2 最速下降法（续） 特点：全局收敛，线性收敛，易产生扭摆现象而造成 早停。 （当x (k)距最优点较远时，速度快，而接近最优点时， 速度下降） 原因：f(x)=f(x(k))+▽Tf(x(k))(x-x (k)) + o||x-x (k)|| 当 x (k)接近 l.opt.时 ▽f(x(k) ) →0，于是高阶项 o||x-x (k)||的影响可能超过▽Tf(x(k))(x-x (k)) 。 5.3 Newton法及其修正 一、 Newton法： 设f(x)二阶可微，取f(x)在x (k)点附近的二阶Taylor近似函数： qk (x)=f(x(k))+ ▽T f(x(k))(x-x (k)) +1／2 (x-x (k)) T▽2 f(x(k)) (x-x (k)) 求驻点： ▽ qk (x)= ▽f(x(k))+ ▽2 f(x(k)) (x-x (k))=0
第五章无约束最优化 Newton法:(续) 当Vfx)正定时,有极小点: x(k+=x(k-Vf(r()/-/ vflxlky ewton迭代公式 实用中常用∫Vx)S=-V(x()解得 +D)=x()+s( x(,E>0,k=1 实用中,判断 k=k+1 若V0x9)若正定时 进行相应处理 Vf(r()S=-Vflxc(ky 得,x(k+=x+s EYe s|<e? STOPx(.opt
第五章 无约束最优化 Newton法： （续） 当▽2 f(x(k)) 正定时，有极小点： x (k+1)=x(k) -[▽2 f(x(k)) ]-1 ▽f(x(k)) ——Newton迭代公式 实用中常用 ▽2 f(x(k)) S= -▽f(x(k)) 解得s (k) x (k+1)=x(k)+s(k) x (1), ε >0, k=1 ▽2 f(x(k)) S= -▽f(x(k)) 得s (k) , x (k+1)=x(k)+s(k) || s (k) ||< ε? STOP.x (k+1)—l.opt No Yes k=k+1 实用中，判断 若▽2 f(x(k))非正定时 进行相应处理