由此，若(-Bxs)Tsk≠0，可取a2[(-Bs)Ts=1,即 a32= 1 E=-BS跳-BS)Y (Uk -BkSk)TSk (Uk -BkSk)TSk 故得对称秩1校正公式如下： B+1=B6+-BAs跳-BS)T (yk-BiSk)TSk (5.5) 类似地，利用拟牛顿方程(5.2)，对H进行对称秩1修正可得 He1=Hg+Sk-HEyk)(Sk-HKVR)T (5.6) (Sk:-HkVK)TVk 有了对称秩1校正公式后，利用它可以构造求解无约束优化问题 的一个拟牛顿算法，步骤如下： 算法5.1（对称秩1算法） 步0给定初始点x0∈R”,终止误差0≤e←1.初始对称正定 阵Ho(通常取单位阵In).令k:=0. Back Close
6/52 JJ II J I Back Close dd, e (yk − Bksk) T sk 6= 0, å αβ2 [(yk − Bksk) T sk] = 1, = αβ2 = 1 (yk − Bksk) T sk , Ek = (yk − Bksk)(yk − Bksk) T (yk − Bksk) T sk . È°ù 1 ˙™Xe: Bk+1 = Bk + (yk − Bksk)(yk − Bksk) T (yk − Bksk) T sk . (5.5) aq/, |^[⁄Óêß (5.2), È Hk ?1È°ù 1 ?å Hk+1 = Hk + (sk − Hkyk)(sk − Hkyk) T (sk − Hkyk) T yk . (5.6) k È°ù 1 ˙™, |^ßå±E¶)ÃÂ`zØK òá[⁄Óé{, ⁄½Xe: é{ 5.1 (È°ù 1 é{) ⁄ 0 â½–©: x0 ∈ R n , ™éÿ 0 ≤ ε 1. –©È°½ H0 (œ~¸† In). - k := 0
步1若‖g‖≤e,停算，输出xk作为近似极小点. 步2计算搜索方向dk=-Hgk 步3用线搜索技术求步长Q. 步4令xk+1=xk+adk,由对称秩1校正公式(5.6)确定H+1 步5令k=k十1，转步1. 下面给出基于Armijo搜索的对称秩1算法的Matlab程序， 程序5.1（对称秩1算法程序) function [x,val,k]=sr1(fun,gfun,x0) %功能：用对称秩1算法求解无约束问题：minf(x) %输入：x0是初始点，fun,gfun分别是目标函数及其梯度 %输出：x,val分别是近似最优点和最优值，k是迭代次数. maxk=500;%给出最大迭代次数 rho=0.55;sigma=0.4;epsilon=1e-5; k=0;n=length(x0);Hk=eye(n); while(k<maxk) Back Close
7/52 JJ II J I Back Close ⁄ 1 e kgkk ≤ ε, é, —— xk äèCq4:. ⁄ 2 Oé|¢êï dk = −Hkgk. ⁄ 3 ^Ç|¢E‚¶⁄ αk. ⁄ 4 - xk+1 = xk +αkdk, dÈ°ù 1 ˙™ (5.6) (½ Hk+1. ⁄ 5 - k := k + 1, =⁄ 1. e°â—ƒu Armijo |¢È°ù 1 é{ Matlab ßS. ßS 5.1 ( È°ù 1 é{ßS) function [x,val,k]=sr1(fun,gfun, x0) %ıU: ^È°ù1é{¶)ÃÂØK: min f(x) %—\: x0¥–©:, fun, gfun©O¥8IºÍ9ŸF› %——: x, val©O¥CqÅ`:⁄Å`ä, k¥SìgÍ. maxk=500; %â—ÅåSìgÍ rho=0.55;sigma=0.4; epsilon=1e-5; k=0; n=length(x0); Hk=eye(n); while(k<maxk)
gk=feval(gfun,x0);%计算梯度 dk=-k*gk;%计算搜索方向 if(norm(gk)<epsilon),break;end%检验终止准则 m=0;mk=0; while(m<20)%用Armijo搜索求步长 if(feval(fun,x0+rho m*dk)<feval(fun,x0)+sigma*rho m*gk'*dk) mk=m;break; end m=m+1; end x=x0+rho mk*dk; sk=x-x0;yk=feval(gfun,x)-gk; Hk=Hk+(sk-Hk*yk)*(sk-Hk*yk)'/(sk-Hk*yk)'*yk);%秩1校正 k=k+1; x0=X; end val=feval(fun,x0); 例5.1利用程序5.1求解无约束优化问题 minf(x)=100(x-x2)2+(1-1)2,x=(c1,2)T∈R2. Back Close
8/52 JJ II J I Back Close gk=feval(gfun,x0); %OéF› dk=-Hk*gk; %Oé|¢êï if(norm(gk)<epsilon), break; end %u™éOK m=0; mk=0; while(m<20) % ^Armijo|¢¶⁄ if(feval(fun,x0+rho^m*dk)<feval(fun,x0)+sigma*rho^m*gk’*dk) mk=m; break; end m=m+1; end x=x0+rho^mk*dk; sk=x-x0; yk=feval(gfun,x)-gk; Hk=Hk+(sk-Hk*yk)*(sk-Hk*yk)’/((sk-Hk*yk)’*yk); %ù1 k=k+1; x0=x; end val=feval(fun,x0); ~ 5.1 |^ßS 5.1 ¶)ÃÂ`zØK min f(x) = 100(x 2 1 − x2) 2 + (x1 − 1)2 , x = (x1, x2) T ∈ R 2
该问题有精确解x*=(1,1)T,fx*)=0. 解取终止准则值为‖Vf(xk)川≤10-5，利用程序5.1，取不同的初 始点，数值结果如下表 表5.1对称秩1校正算法的数值结果 初始点(0)迭代次数（目标函数值(f(c) (0,0)T 22 7.0304×10-19 0.5,0.5)7 19 3.8208×10-16 (2,2)7 38 3.3992×10-20 (-1,-1)7 45 8.2927×10-16 (1,10)7 98 1.9321×10-16 (10,10)7 142 2.1578×10-15 说明上述程序的调用方式是： x0=[-1.21]; [x,val,k]=sr1('fun','gfun',x0) 其中fun,gfun分别是求目标函数值及其梯度的M函数文件 Back Close
9/52 JJ II J I Back Close TØKk°() x ∗ = (1, 1)T , f(x ∗ ) = 0. ) ™éOKäè k∇f(xk)k ≤ 10−5 , |^ßS 5.1, ÿ”– ©:, Íä(JXeL. L 5.1 È°ù 1 é{Íä(J. –©: (x0) SìgÍ (k) 8IºÍä (f(xk)) (0, 0)T 22 7.0304 × 10−19 (0.5, 0.5)T 19 3.8208 × 10−16 (2, 2)T 38 3.3992 × 10−20 (−1, −1)T 45 8.2927 × 10−16 (1, 10)T 98 1.9321 × 10−16 (10, 10)T 142 2.1578 × 10−15 `² ˛„ßSN^ꙥ: x0=[-1.2 1]’; [x,val,k]=sr1(’fun’,’gfun’,x0) Ÿ• fun, gfun ©O¥¶8IºÍä9ŸF› M ºÍ©á
§5.2BFGS算法及其Matlab实现 BFGS校正是目前最流行也是最有效的拟牛顿校正，它是由Broy- den,Fletcher,Goldfarb和Shanno在1970年各自独立提出的拟牛顿法， 故称为BFGS算法.其基本思想是：在(5.3)中取修正矩阵E为秩2 矩阵： Er =aukug Bvkvt, 其中u,v∈R”是待定向量，Q,B∈R是待定实数.于是由拟牛顿方 程(5.1)可得 (Bk+au4f+Bku)sk=张， 或等价地 a(u以sJu+B(fs)v%=张-Bksk (5.7） Back Close
10/52 JJ II J I Back Close §5.2 BFGS é{9Ÿ Matlab ¢y BFGS ¥8cÅ61è¥Åk[⁄Ó, ߥd Broyden, Fletcher, Goldfarb ⁄ Shanno 3 1970 càg’·J—[⁄Ó{, °è BFGS é{. Ÿƒ gé¥: 3 (5.3) •?› Ek èù 2 › : Ek = αuku T k + βvkv T k , Ÿ• uk, vk ∈ R n ¥ñ½ï˛, α, β ∈ R ¥ñ½¢Í. u¥d[⁄Óê ß (5.1) å (Bk + αuku T k + βvkv T k )sk = yk, ½ d/ α(u T k sk)uk + β(v T k sk)vk = yk − Bksk. (5.7)