4.Newton法收敛定理定理设f eC2，x充分靠近x*，Vf(x*)=0,如果2f(x*)正定，且Hessian矩阵G(x)满足Lipschitz条件，即存在β>0，使得对所有i,j,有G,(x)-G,(y)≤βx- yll其中G,(x)是Hessian矩阵G(x)的(i,j)元素。则对一切k,Newton法迭代xk+1= x*-GF'gk有定义，且所得序列x收敛到，并且具有二阶收敛速度。16/68
16/68 4. Newton法收敛定理 定理 k k k k ij ij ij k k x x G g G x G x i j G x G y x y i j f x G x f C x x f x 1 1 2 * 2 * * ,Newton ( ) Hessian ( ) ( , ) ( ) ( ) , Lipschitz 0 , , ( ) Hessian ( ) ( ) 0, + − = − − − = 则对一切 法迭代 其 中 是 矩 阵 的 元素。 条件，即存在 ，使得对所有 有 如 果 正定，且 矩 阵 满 足 设 ， 充分靠近 ， 具有二阶收敛速度。 有定义，且所得序列{x k }收敛到x *，并且
5.带步长因子的迭代法一阻尼生顿法pk = -Gilgk ,xk+1 = xk +αk p带步长因子的迭代法在一定条件下是总体收敛的。6.Newton法的特点收敛速度快，为二阶收敛。当初始点远离最优解时，G不一定正定，牛顿方向不一定是下降方向，其收敛性不能保证。G计算工作量大，有的目标函数的Hessian矩阵很难计算，甚至不好求得。17/68
17/68 ▪ 收敛速度快，为二阶收敛。 6. Newton法的特点 5. 带步长因子的迭代法—阻尼牛顿法 ▪ 当初始点远离最优解时，Gk不一定正定，牛顿方 向不一定是下降方向，其收敛性不能保证。 k k k k x = x + p +1 , 1 k k k p G g − = − 带步长因子的迭代法在一定条件下是总体收敛的。 ▪ Gk计算工作量大，有的目标函数的Hessian矩阵 很难计算，甚至不好求得
四、拟牛顿法（变尺度法）1、拟牛顿法的思想在Newton迭代公式：xk+1 = x* -GrVf(xh)中，如果用正定矩阵,替代Gi，则有：xk+1 = xk - H,Vf(x*)更一般的形式：k+1 = xk -αrH,Vf(x*)X称为拟Newton法或变尺度算法18/68
18/68 ( ) Newton 1 1 k k k k x = x − G f x + − 在 迭代公式： ( ) 1 1 k k k k k k x x H f x H G = − + 中，如果用正定矩阵 替 代 − ，则有： 四、拟牛顿法(变尺度法) 1、拟牛顿法的思想 ( ) 1 k k k k k x = x − H f x + 更一般的形式： 称为拟Newton法或变尺度算法
拟Newton法.k+1= xk -α,H,Vf(x*)特别的当Hk=I时→梯度法下降方向 p=-Vf(x)当H,=Gi"时= Newton法下降方向 dk=-G=iVf(xk)拟牛顿法中H应满足什么条件！19/68
19/68 ( ) 1 k k k k k x = x − H f x + 当Hk = Gk −1时 Newton法 拟Newton法 当Hk I时 梯度法 特别的 ( ) k k 下降方向 p = −f x ( ) 1 k k k d = −G f x 下降方向 − 拟牛顿法中Hk应满足什么条件？
2、拟牛顿算法中H,的确定H应满足什么条件！ 迭代公式具有下降性质 H,正定(②)H,的计算量要小>Hk+1 = Hk +AH(△Hk = Hk+1 - Hk)H~Grl(③)收敛速度要快关键:如何保证H,正定和Hk~G-l如何确定AH？20/68
20/68 2、拟牛顿算法中H k的确定 Hk正定 ( ) 1 1k k k k k k H H H H H H = − = + + + − 1 Hk Gk 如何确定 ？ 如何保证 正定和 k k k k HH H G − ?1 （1）迭代公式具有下降性质 （2） Hk的计算量要小 （3）收敛速度要快 关键： H k应满足什么条件？