故条件(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›) ⁄