3、最速下降法的总体收敛性定理设f eC，在最速下降法中采用精确一维定理1讠则产生的迭代点列x搜索或不精确一维搜索的每一个聚点是驻点。定理2 设f eC，且2f(x)≤M.对任何给定的的初始值x和ε>0,采用精确一维搜索最速下降法或者有限终止，或lim f(x）=-0,或limVf(x)=0k-→>00k→80遗感的是最速下降法的整体收敛性并不能保证它是一个有效的方法。6/68
6/68 3、最速下降法的总体收敛性定理 的每一个聚点是驻点。 搜索或不精确一维搜索，则产生的迭代点列 设 ，在最速下降法中采用精确一维 { } 1 k x 定理1 f C 定理2 lim ( ) , lim ( ) 0 0, ( ) . 0 2 2 = − = → → k k k k f x f x x f C f x M 或者有限终止，或 或 的初始值 和 采用精确一维搜索最速下降法 设 ， 且 对任何给定的 遗憾的是最速下降法的整体收敛性并不能保 证它是一个有效的方法
4、最速下降法的性质性质．设f(x)有一阶连续偏导数，若步长 α,满足f(x* +αup) = min f(x* +αp*)2则有 Vf(x*+αp)’ p = 0 。证明:令 (α)= f(x+αp"),则 β'(α)=Vf(x* +αp*) pk.: f(x* +αrp*)=min f(x* +αp*)a.. p'(α)=Vf(xk +αrph)T pk =0 .注:因为梯度法的搜索方向 pk+1=-Vf(x +αμp"),所以(p*+1) p* = 0= p*+I p* 。7/68
7/68 ( ) min ( ) k k k k k f x p f x p + = + 则有 f (x k +k p k ) T p k = 0。 性质. 证明：令 () = f (x k + p k )， ( ) ( ) . k k T k 则 = f x + p p ( ) min ( ) k k k k k f x p f x p + = + ( ) = ( + ) = 0 . k T k k k k f x p p 设 f (x) 有一阶连续偏导数，若步 长 k 满 足 注： ( p k+1 ) T p k = 0 p k+1 ⊥ p k 。 因为梯度法的搜索方向 p k+1 = − f (x k +k p k )，所以 4、最速下降法的性质
最速下降法的锯齿现象+数值实验表明，当目标函数的等值线接近于一个圆（球）时，最速下降法下降较快，而当目标函数的等值线接近于一个扁长的椭球时，最速下降法开始几步下降较快，后来就出现锯齿现象，下降十分缓慢，8/68
8/68 1 x * x 2 x 3 x 最速下降法的锯齿现象 数值实验表明，当目标函数的等值线接近于一个 圆（球）时，最速下降法下降较快，而当目标函 数的等值线接近于一个扁长的椭球时，最速下降 法开始几步下降较快，后来就出现锯齿现象，下 降十分缓慢
三、Newton法minf(x)问题：XER"s.t.选代公式：x+1=x+αpf(xk +αrph)< f(x*)要求1.Newton法的基本思想：利用f(x）在xk处的二阶Taylor展开式的极小值点作为xk+19/68
9/68 三、Newton 法 利用 f(x) 在x k处的二阶Taylor展开式的 极小值点作为x k+1 1. Newton法的基本思想： n s t x R f x . . min ( ) k k k 1 k x x p + 迭代公式： = + ( ) ( ) k k k k f x p f x + 问题： 要求
将f(x)在x*处二阶Taylor展开f(x) ~ Q(x)= f(x)+Vf(xk) (x -x*)++;(x-x*)v"f(x")(x-x*)记 gk=Vf(xh),G,=V"f(x*)。则 Q(x)= f(x*)+gl (x-x*)+=(x-xh)'G(x-xh)令 VQ(x)=gk +G;(x-x)=0若Hesse矩阵G,正定，即G,>0，则G=l>0，此时有k+1 = xk - GrgkXNewton迭代公式10/68
10/68 ( ) ( )( ) 21 ( ) ( ) ( ) ( ) ( ) k T 2 k k k k T k x x f x x x f x Q x f x f x x x + − − = + − + ( ) ( ) 21 ( ) ( ) ( ) k k T k k T k k 则 Q x = f x + g x − x + x − x G x − x 记 gk = f (xk ) ,Gk = 2 f (xk )。 ( ) = + ( − ) = 0 k k k Q x g G x x 将f (x)在xk处二阶Taylor展 开 令 若Hesse矩阵Gk正定，即Gk 0，则Gk−1 0，此时有 k k k k x x G g +1 −1 = − Newton迭代公式