最优化方法及其Matlab程序设计 第三章最速下降法和牛顿法 Back Close
1/33 JJ II J I Back Close Å`zê{9Ÿ Matlab ßSO 1nŸ ÅÑe¸{⁄⁄Ó{
本章讨论无约束优化问题 min f(x) (3.1) x∈Rn 的最速下降法和牛顿法及其改进算法.其中最速下降法是求解无约束 优化问题最简单和最古老的方法之一，虽然时至今日它不再具有实用 性，但它却研究其它无约束优化算法的基础，许多有效算法都是以它 基础通过改进或修正而得到的.此外，牛顿法也是一种经典的无约束 优化算法，并且因其收敛速度快以及具有自适应性等优点而至今仍受 到科技工作者的青睐。 S3.1最速下降方法及其Matlab实现 在第2章关于无约束优化问题下降类算法的一般框架时提及，用 不同的方式确定搜索方向或搜索步长，就会得到不同的算法.最速下 Back Close
2/33 JJ II J I Back Close Ÿ?ÿÃÂ`zØK min x∈Rn f(x) (3.1) ÅÑe¸{⁄⁄Ó{9ŸU?é{. Ÿ•ÅÑe¸{¥¶)à`zØKÅ{¸⁄ÅPê{Éò, è,ûñ8Fßÿ2‰k¢^ 5, ß%ÔƒŸßÃÂ`zé{ƒ:, Nıké{—¥±ß ƒ:œLU?½? . d , ⁄Ó{è¥ò´²;à`zé{, øÖœŸ¬Òћر9‰kg·A5 `: ñ8E. âEÛäˆì‡. §3.1 ÅÑe¸ê{9Ÿ Matlab ¢y 31 2 Ÿ'uÃÂ`zØKe¸aé{òѵeûJ9, ^ ÿ”ê™(½|¢êï½|¢⁄, “¨ÿ”é{. ÅÑe
降法是用负梯度方向 dk =-Vf(xk) (3.2) 作为搜索方向的（因此也称为梯度法）.设f(x)在xk附近连续可微， d以为搜索方向向量，gk=Vf(x).由泰勒展开式得 f(Zk +adk)=f(k)+agi dk+o(a),a0. 那么目标函数f(x)在xk处沿方向d山下降的变化率为 lim f(xk+adk)-f(Ck) agi dk o(a) a→0 Q Q-→0 Q gi di=llgkldell cos0, 其中0k是9张与d,的夹角.显然，对于不同的方向山k,函数变化率 取决于它与9k夹角的余弦值.要使变化率最小，只有c0s0=一1，即 0:=π时才能达到，亦即d应该取(3.2)中的负梯度方向这也是将 Back Close
3/33 JJ II J I Back Close ¸{¥^KF›êï dk = −∇f(xk) (3.2) äè|¢êï (œdè°èF›{). f(x) 3 xk NCÎYåá, dk è|¢êïï˛, gk = ∇f(xk). dV–m™ f(xk + αdk) = f(xk) + αgT k dk + o(α), α > 0. @o8IºÍ f(x) 3 xk ?˜êï dk e¸Cz«è lim α→0 f(xk + αdk) − f(xk) α = lim α→0 αgT k dk + o(α) α = g T k dk = kgkkkdkk cos ¯θk, Ÿ• ¯θk ¥ gk Ü dk Y. w, Èuÿ”êï dk, ºÍCz« ˚ußÜ gk Y{uä. á¶Cz«Å, êk cos ¯θk = −1, = ¯θk = π û‚Uà, ½= dk AT (3.2) •KF›êï, ˘è¥Ú
负梯度方向叫作最速下降方向的由来.下面给出最速下降法的具体计 算步骤 算法3.1（最速下降法 步0选取初始点x0∈R”,容许误差0≤e《1.令k:=1. 步1计算9k=又f(xk.若‖lg‖≤e,停算，输出ck作为近似最 优解 步2取方向d=-9k: 步3由线搜索技术确定步长因子Q 步4令xk+1=xk十Qkdk,k:=k+1,转步1. 说明步3中步长因子α的确定即可使用精确线搜索方法，也可 以使用非精确线搜索方法，在理论上都能保证其全局收敛性.若采用 Back Close
4/33 JJ II J I Back Close KF›êïäÅÑe¸êïd5. e°â—ÅÑe¸{‰NO é⁄½. é{ 3.1 (ÅÑe¸{) ⁄ 0 ¿–©: x0 ∈ R n , NNÿ 0 ≤ ε 1. - k := 1. ⁄ 1 Oé gk = ∇f(xk). e kgkk ≤ ε, é, —— xk äèCqÅ `). ⁄ 2 êï dk = −gk. ⁄ 3 dÇ|¢E‚(½⁄œf αk. ⁄ 4 - xk+1 := xk + αkdk, k := k + 1, =⁄ 1. `² ⁄ 3 •⁄œf αk (½=å¶^°(Ç|¢ê{, èå ±¶^ö°(Ç|¢ê{, 3nÿ˛—UyŸ ¤¬Ò5. eÊ^
精确线搜索方法，即 f(Ck akdk)=min f(Tk adk), a>0 那么应满足 ())d0. 由(3.2)有 Vf(k+1)TVf(Zk)=0, 即新点xk+1处的梯度与旧点xk处的梯度是正交的，也就是说迭代点 列所走的路线是锯齿型的，故其收敛速度是很缓慢的（至多线性收敛 速度)： 由d=-9k及(2.16)，即 -9d4 cos0k= -9R-9 =1,→0k=0, Back geldk IglI‖-9l Close
5/33 JJ II J I Back Close °(Ç|¢ê{, = f(xk + αkdk) = min α≥0 f(xk + αdk), @o αk A˜v φ 0 (α) = d dα f(xk + αdk)|α=αk = ∇f(xk + αkdk) T dk = 0. d (3.2) k ∇f(xk+1) T∇f(xk) = 0, =#: xk+1 ?F›ÜŒ: xk ?F›¥, è“¥`Sì: §r¥Ç¥Á¸., Ÿ¬ÒÑ›¥ÈÖ˙ (ñıÇ5¬Ò Ñ›). d dk = −gk 9 (2.16), = cosθk = −g T k dk kgkkkdkk = −g T k (−gk) kgkkk − gkk = 1, ⇒ θk = 0,
故条件(2.15)必然满足(0≤≤)-4,4>0).从而直接应用定理 22和定理2.3即得到最速下降法的全局收敛性定理： 定理3.1设目标函数f(x)连续可微且其梯度函数Vf(x)是 Lipschitz连续的，{xk}由最速下降法产生，其中步长因子ak由精确 线搜索，或由Wolfe准则，或由Armijo准则产生.则有 lim‖Vf(xk)川l=0. 下面的定理给出了最速下降法求解严格凸二次函数极小值问题 时的收敛速度估计，其证明可参阅有关文献，此处省略不证， 定理3.2设矩阵H∈Rmxn对称正定，c∈Rm.记入1和入n分 别是H最大和最小特征值，k=入1/八：考虑如下极小化问题 min f()=cx+女H Back Close
6/33 JJ II J I Back Close ^á (2.15) 7,˜v (0 ≤ θk ≤ π 2 − µ, µ > 0). l ÜA^½n 2.2 ⁄½n 2.3 =ÅÑe¸{ ¤¬Ò5½n: ½n 3.1 8IºÍ f(x) ÎYåáÖŸF›ºÍ ∇f(x) ¥ Lipschitz ÎY, {xk} dÅÑe¸{), Ÿ•⁄œf αk d°( Ç|¢, ½d Wolfe OK, ½d Armijo OK). Kk lim k→∞ k∇f(xk)k = 0. e°½nâ— ÅÑe¸{¶)ÓLJgºÍ4äØK û¬ÒÑ›O, Ÿy²åÎ k'©z, d?é—ÿy. ½n 3.2 › H ∈ R n×n È°½, c ∈ R n . P λ1 ⁄ λn © O¥ H Åå⁄ÅAä, κ = λ1/λn. ƒXe4zØK min f(x) = c T x + 1 2 x THx.
设{x}是用精确线搜索的最速下降法求解上述问题所产生的迭代序 列，则对于所有的k,下面的不等式成立 l欧+1-H≤（优十）欧a-lm, (3.3) 其中，x*是问题的唯一解，‖xH=VxTHz 由上面的定理可以看出，若条件数接近于1（即H的最大特征 值和最小特征值接近时)，最速下降法是收敛很快的.但当条件数较 大时（即H近似于病态时），算法的收敛速度是很缓慢的， 下面我们给出基于Armijo非精确线搜索的最速下降法Matlab程 序 程序3.1（最速下降法程序） function [x,val,k]=grad(fun,gfun,x0) %功能：用最速下降法求解无约束问题：minf(x) Back %输入：x0是初始点，fun,gfun分别是目标函数和梯度 Close
7/33 JJ II J I Back Close {xk} ¥^°(Ç|¢ÅÑe¸{¶)˛„ØK§)SìS , KÈu§k k, e°ÿ ™§· kxk+1 − x ∗ kH ≤ κ − 1 κ + 1 kxk − x ∗ kH, (3.3) Ÿ•, x ∗ ¥ØKçò), kxkH = √ x THx. d˛°½nå±w—, e^áÍ κ Cu 1 (= H ÅåA ä⁄ÅAäCû), ÅÑe¸{¥¬ÒÈØ. ^áÍ κ åû (= H Cquæû), é{¬ÒÑ›¥ÈÖ˙. e°·Çâ—ƒu Armijo ö°(Ç|¢ÅÑe¸{ Matlab ß S. ßS 3.1 (ÅÑe¸{ßS) function [x,val,k]=grad(fun,gfun,x0) %ıU: ^ÅÑe¸{¶)ÃÂØK: min f(x) %—\: x0¥–©:, fun, gfun©O¥8IºÍ⁄F›
%输出：x,val分别是近似最优点和最优值，k是迭代次数. maxk=5000;%最大迭代次数 rho=0.5;sigma=0.4; k=0;epsilon=1e-5; while(k<maxk) g=feval(gfun,x0);%计算梯度 d=-g;%计算搜索方向 if(norm(d)<epsilon),break;end m=0;mk=0; while(m<20) %Armijo搜索 if(feval(fun,x0+rho m*d)<feval(fun,x0)+sigma*rho m*g'*d) mk=m;break; end m=m+1; end xO=x0+rho mk*d; k=k+1; end X=x0; val=feval(fun,x0) Back Close
8/33 JJ II J I Back Close %——: x, val©O¥CqÅ`:⁄Å`ä, k¥SìgÍ. maxk=5000; %ÅåSìgÍ rho=0.5;sigma=0.4; k=0; epsilon=1e-5; while(k<maxk) g=feval(gfun,x0); %OéF› d=-g; %Oé|¢êï if(norm(d)<epsilon), break; end m=0; mk=0; while(m<20) %Armijo|¢ if(feval(fun,x0+rho^m*d)<feval(fun,x0)+sigma*rho^m*g’*d) mk=m; break; end m=m+1; end x0=x0+rho^mk*d; k=k+1; end x=x0; val=feval(fun,x0);
例3.1利用程序3.1求解无约束优化问题 mif(x)=100(x-x2)2+(1-1)2. x∈R2 该问题有精确解x*=(1,1)T,f(x*)=0. 解首先建立两个分别计算目标函数和梯度的文件： function f=fun(x) f=100*(x(1)2-x(2)^2+(x(1)-1)^2; function g=gfun(x) g=[400*x(1)*(x(1)2-x(2)+2*(x(1)-1),-200*(x(1)2-x(2)]'; 我们利用程序3.1，终止准则取为‖7f(x)川≤10-5.取不同的初 始点，数值结果如下表， 表3.1最速下降法的数值结果 Back Close
9/33 JJ II J I Back Close ~ 3.1 |^ßS 3.1 ¶)ÃÂ`zØK min x∈R2 f(x) = 100(x 2 1 − x2) 2 + (x1 − 1)2 . TØKk°() x ∗ = (1, 1)T , f(x ∗ ) = 0. ) ƒkÔ·¸á©OOé8IºÍ⁄F› m ©á: function f=fun(x) f=100*(x(1)^2-x(2))^2+(x(1)-1)^2; function g=gfun(x) g=[400*x(1)*(x(1)^2-x(2))+2*(x(1)-1), -200*(x(1)^2-x(2))]’; ·Ç|^ßS 3.1, ™éOKè k∇f(xk)k ≤ 10−5 . ÿ”– ©:, Íä(JXeL. L 3.1 ÅÑe¸{Íä(J
初始点(ro) 迭代次数(k)目标函数值(f(ax) (0.0,0.0)T 1159 1.1630×10-10 (2.0,1.0)7 611 1.1416×10-10 (1.0,-1.0)7 1551 1.2251×10-10 (-1.0,-1.0)T 1499 9.2536×10-11 （-1.2,1)7 1435 1.1985×10-10 (10,-10)7 1024 1.0156×10-10 由上表可以看出，最速下降法的收敛速度是比较缓慢的 说明上述程序的调用方式是 x0=[-1.21]; [x,val,k]=grad('fun','gfun',x0) 其中fun,gfn分别是求目标函数值及其梯度的M函数文件. S3.2牛顿法及其Matlab实现 跟最速下降法一样，牛顿法也是求解无约束优化问题最早使用的 经典算法之一.其基本思想是用迭代点x处的一阶导数（梯度）和二 Back Close
10/33 JJ II J I Back Close –©: (x0) SìgÍ (k) 8IºÍä (f(xk)) (0.0, 0.0)T 1159 1.1630 × 10−10 (2.0, 1.0)T 611 1.1416 × 10−10 (1.0, −1.0)T 1551 1.2251 × 10−10 (−1.0, −1.0)T 1499 9.2536 × 10−11 (−1.2, 1)T 1435 1.1985 × 10−10 (10, −10)T 1024 1.0156 × 10−10 d˛Lå±w—, ÅÑe¸{¬ÒÑ›¥'Ö˙. `² ˛„ßSN^ꙥ: x0=[-1.2 1]’; [x,val,k]=grad(’fun’,’gfun’,x0) Ÿ• fun, gfun ©O¥¶8IºÍä9ŸF› M ºÍ©á. §3.2 ⁄Ó{9Ÿ Matlab ¢y ãÅÑe¸{ò, ⁄Ó{襶)ÃÂ`zØKÅ@¶^ ²;é{Éò. Ÿƒ gé¥^Sì: xk ?ò Í (F›) ⁄