文档介绍：第五章
无约束最优化方法
第五章无约束最优化
(f) min f(x) f : Rn→R
最优性条件
设 f 连续可微
必要条件:若x*-. 则▽f(x*)=0 (驻点)。
当 f 凸时, x*-. ←→▽f(x*)=0
注意: f(x) ≥f(x*)+ ▽Tf(x*)(x-x*), x.
故 f(x*) ≤f(x), x. ( 由于▽Tf(x*) =0)
最速下降法
在迭代点 x(k) 取方向 d(k)= -▽f(x(k) )
精确一维搜索
最速下降法:梯度方向函数值变化最快的方向
第五章无约束最优化
最速下降法(续)
x(1), ε>0, k=1
|| ▽f(x(k) ) ||< ε?
Yes
stop. x(k) –解
No
d(k)= -▽f(x(k) )
解 min f(x(k)+λ d(k))
. λ>0
得 x(k+1)=x(k)+λkd(k)
k=k+1
第五章无约束最优化
最速下降法(续)
特点:全局收敛,线性收敛,易产生扭摆现象而造成早停。
(当x(k)距最优点较远时,速度快,而接近最优点时,速度下降)
原因:f(x)=f(x(k))+▽Tf(x(k))(x-x(k)) + o||x-x(k)||
当 x(k)接近 ▽f(x(k) ) →0,于是高阶项
o||x-x(k)||的影响可能超过▽Tf(x(k))(x-x(k)) 。
Newton法及其修正
一、 Newton法:
设f(x)二阶可微,取f(x)在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))
得s(k) , x(k+1)=x(k)+s(k)
|| s(k) ||< ε?
(k+1)—
Yes
No
k=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))=Q x(1) +P ▽2f(x(1))=Q
迭代: x(2) = x(1) - Q –1(Qx(1) +P) = - Q –1 P (驻点即opt.)
主要缺点: (1)局部收敛
(2)用到二阶Hesse阵,且要求正定
(3)需计算Hesse阵逆或解n阶线性方程组,计算量大
第五章无约束最优化
Newton法及其修正
二、 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迭代中,取d(k)= -[▽2f(x(k)) ]-1 ▽f(x(k)) ,
加入线性搜索:min f(x(k)+λk d(k))
求得λk , x(k+1)=x(k)+λkd(k)
特点:可改善局部收敛性,当d(k)为函数上升方向时,可向负方向搜索,但可能出现± d(k)均非下降方向的情况。
第五章无约束最优化
Newton法及其修正
二、 Newton法的改进: (续)
(3)Goldstein-Price方法(G-P法):
取 d(k)= -[▽2f(x(k)) ]-1 ▽f(x(k)) , ▽2f(x(k)) 正定
- ▽f(x(k)) ,否则
用下列不精确一维搜索: 求λk,使其中δ∈(