第五章 无约束最优化方法
第 五 章 无约束最优化方法
第五章无约束最优化 (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) ) ||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))非正定时 进行相应处理
第五章无约束最优化 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) ( ) ( ) ( ) ④