第五章无约束最优化 Newton法:(续) 特点:二阶收敛,局部收敛。 (当充分接近时局部函数可用正定二次函数很好地近似, 放伙很快) 二次终结性:当f(x)为正定二次函数时,从任意初始点可一步迭 代达到最优解。 设f(x=1/2xgx+Px+,Qnxn对称正定,P∈R,r∈R.Vx Vfl=oxo+P 送代:x=x(-Q1Qx1+P)=-Q-1P(班点即opt 主要缺点:(1)局部收敛 (2)用到二阶Hee阵,且要求正定 (3)需计算Hest阵逆或解n阶线性方程组,计算量大
第五章 无约束最优化 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 ▽2 f(x(1))=Q 迭代： x (2) = x (1) - Q –1 (Qx(1) +P) = - Q –1 P (驻点即opt.) 主要缺点：(1)局部收敛 (2)用到二阶Hesse阵，且要求正定 (3)需计算Hesse阵逆或解n阶线性方程组，计算量大
第五章无约束最优化 53 Newton法及其修正 Newton法的改进 (1)为减小工作量,取m(正整数),使每m次选代使用同一个 Hese阵,迭代公式变为 x(knti+=x(km+- Vf(x(km)I-Vfllkmti 产=0,1,2,…,m-l,k=0,1,2, 特点:收速度随m的增大而下降 mF=1的 Newton法,m∞即线性收敛。 (2)带线性搜索的 Newton法: 在 Newton选代中,取酗=-Vfx}Wf(x), 加入线性搜索: min fle)+k) 求得k,x+1=x+kdr8 特点:可改善局部收敛性,当为函数上升方向时,可向负 方向搜索,但可能出现士均非下降方向的情况
第五章 无约束最优化 5.3 Newton法及其修正 二、 Newton法的改进： (1)为减小工作量，取m（正整数），使每m次迭代使用同一个 Hesse阵，迭代公式变为： x (km+j+1)=x(km+j) -[▽2 f(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)= -[▽2 f(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)均非下降方向的情况
第五章无约束最优化 53 Newton法及其修正 二、 Newton法的改进:(续) (3) Goldstein- Price方法(G-P法) 取1VFVx1),四正定 (x1y) 否则 采用下列精确一维搜索:求,使其中δ∈(0,1/2) 1°f(x()+kd)≤f(x(0+dV(x1)dak 2°(x+4k学x)+(1-6)0x)T)k 特点:在一定条件下,GP法全局收敛。 但当V(x1)非正定情况较多时,收敛速度停为 接近线性
第五章 无约束最优化 5.3 Newton法及其修正 二、 Newton法的改进：（续） (3)Goldstein-Price方法(G-P法)： 取 d (k)= -[▽2 f(x(k)) ]-1 ▽f(x(k)) ， ▽2 f(x(k)) 正定 - ▽f(x(k)) ，否则 采用下列精确一维搜索： 求λk，使其中δ ∈(0,1／2) 1° f(x(k)+λk d (k)) ≤ f(x(k))+ δ ▽f(x(k)) Td (k) λk 2° f(x(k)+λk d (k)) ≥f(x(k))+ (1-δ) ▽f(x(k)) Td (k) λk 特点：在一定条件下， G-P法全局收敛。 但当▽2 f(x(k)) 非正定情况较多时，收敛速度降为 接近线性
第五章无约束最优化 53 Newton法及其修正 Newton法的改进:(续) (4) Levenberg- Marquardt法(L-M法): 主要思想: 用[V(x)+I取代Vfx)进 行迭代,其中Ⅰ为单位矩阵 u>l 使 Vfx)+正定,尽量小 特点:全局二阶收鲛
第五章 无约束最优化 5.3 Newton法及其修正 二、 Newton法的改进：（续） (4)Levenberg-Marguardt法（L-M法）： 主要思想： 用[▽2 f(x(k)) +μ I ] 取代▽2 f(x(k)) 进 行迭代，其中I 为单位矩阵。 μ>0 使 [▽2 f(x(k)) +μ I] 正定， μ尽量小。 特点：全局二阶收敛
第五章无约束最优化 54共轭梯度法 共轭梯度法的方向: 设f(x)=(1/2)xGx+bx+ c Nxn对称正定,b∈R,从最速下 條方向开始,构造一组共轭方向: 设初始点,取=-(x)……①(最速下摩方向 设松1,已得致个相互共的方向,d2,,秒,以及,由x 开始依次沿上述方向精确一维搜索得到点,…、x(,x+即 有下式: 4+1)=x()+0x4 ,i=l,2,…, 精确一维搜索保证方向导数为0: Vf(.)c0=O,i1,2,…,k 在x什+点构造新方向为x+1)与,P,…,,P的组合: =-Vf(x14)+∑Bd0…④
第五章 无约束最优化 5.4 共轭梯度法 一、共轭梯度法的方向： 设f(x)=(1/2)xTGx+bTx+c Gn×n对称正定，b∈Rn ,从最速下 降方向开始，构造一组共轭方向： 设初始点x (1) ,取d (1)= -▽f(x(1)) ……① (最速下降方向) 设k≥1,已得到k个相互共轭的方向d (1),d(2), …,d(k) ,以及，由x (1) 开始依次沿上述方向精确一维搜索得到点x (2) , …，x (k),x(k+1) .即 有下式： x (i+1)=x(i)+αid (i) , i=1,2, …,k ……② 精确一维搜索保证方向导数为0： ▽f T (x(i+1))d(i)=0, i=1,2, …,k ……③ 在x (i+1)点构造新方向d (k+1)为-▽f(x(k+1)) 与d (1),d(2), …,d(k)的组合： = + + = − + k j k j j k k d f x d 1 ( 1) ( 1) ( ) ( ) ( ) ④