不难发现，只要B0对称正定，上述校正公式可以保证矩阵序列{B} 的对称正定性.下面给出基于Armijo搜索准则的BGS算法的详细 步骤 算法5.2(BFGS算法) 步0给定参数6∈(0,1)，o∈(0,0.5)，初始点x0∈Rm,终止误 差0≤e<1.初始对称正定阵B0(通常取为G(aco)或单位阵In).令 k=0. 步1计算9k=Vf(xk).若g‖≤E,停算，输出xk作为近似极 小点. 步2解线性方程组得解d: Bkd=-gk. (5.12) Back Close
16/52 JJ II J I Back Close ÿJuy, êá B0 È°½, ˛„˙™å±y› S {Bk} È°½5. e°â—ƒu Armijo |¢OK BFGS é{ç[ ⁄½. é{ 5.2 (BFGS é{) ⁄ 0 â½ÎÍ δ ∈ (0, 1), σ ∈ (0, 0.5), –©: x0 ∈ R n , ™éÿ 0 ≤ ε 1. –©È°½ B0 (œ~è G(x0) ½¸† In). - k := 0. ⁄ 1 Oé gk = ∇f(xk). e kgkk ≤ ε, é, —— xk äèCq4 :. ⁄ 2 )Ç5êß|) dk: Bkd = −gk. (5.12)
步3设m以是满足下列不等式的最小非负整数m: f(ck+6mdk)<f(xk)+aomgi dk. (5.13) 令Qk=δmk,xk+1=xk+Qkdk. 步4由校正公式(5.11)确定Bk+1 5 步5令k=k+1,转步1. 下面给出基于Armijo搜索的BFGS算法的Matlab程序. 程序5.2(BFGS算法程序) function [x,val,k]=bfgs(fun,gfun,x0,varargin) %功能：用BFGS算法求解无约束问题：minf(x) %输入：x0是初始点，fun,gfun分别是目标函数及其梯度； %varargin是输入的可变参数变量，简单调用bfgs时可以忽略它， %但若其它程序循环调用该程序时将发挥重要的作用 %输出：x,va1分别是近似最优点和最优值，k是迭代次数 Back maxk=500;%给出最大迭代次数 Close
17/52 JJ II J I Back Close ⁄ 3 mk ¥˜veÿ ™ÅöKÍ m: f(xk + δ mdk) ≤ f(xk) + σδmg T k dk. (5.13) - αk = δ mk , xk+1 = xk + αkdk. ⁄ 4 d˙™ (5.11) (½ Bk+1. ⁄ 5 - k := k + 1, =⁄ 1. e°â—ƒu Armijo |¢ BFGS é{ Matlab ßS. ßS 5.2 ( BFGS é{ßS) function [x,val,k]=bfgs(fun,gfun,x0,varargin) %ıU: ^BFGSé{¶)ÃÂØK: min f(x) %—\: x0¥–©:, fun, gfun©O¥8IºÍ9ŸF›; % varargin¥—\åCÎÍC˛, {¸N^bfgsûå±—ß, % eŸßßSÃÇN^TßSûÚuûáä^ %——: 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); Bk=eye(n);%Bk=feval('Hess',x0) while(k<maxk) gk=feval(gfun,x0,varargin{:);%计算梯度 if(norm(gk)<epsilon),break;end%检验终止准则 dk=-Bk\gk;%解方程组，计算搜索方向 m=0;mk=0; while(m<20)%用Armijo搜索求步长 newf=feval(fun,x0+rho m*dk,varargin{:}) oldf=feval(fun,x0,varargin{:}) if (newf<oldf+sigma*rho m*gk'*dk) mk=m;break; end m=m+1; end %BFGS校正 x=x0+rho mk*dk; sk=x-x0;yk=feval(gfun,x,varargin{:})-gk; if(yk'*sk>0) Back Close
18/52 JJ IIJI Back Close rho=0.55;sigma=0.4; epsilon=1e-5; k=0; n=length(x0); Bk=eye(n); %Bk=feval(’Hess’,x0); while(k<maxk) gk=feval(gfun,x0,varargin{:}); % O é F › if(norm(gk)<epsilon), break; end % u ™é O K dk=-Bk\gk; % ) ê ß | , Oé|¢ ê ï m=0; mk=0; while(m<20) % ^Armijo|¢ ¶ ⁄ newf=feval(fun,x0+rho^m*dk,varargin{:}); oldf=feval(fun,x0,varargin{:}); if(newf<oldf+sigma*rho^m*gk’*dk) mk=m; break; end m=m+1; end %BFGS x=x0+rho^mk*dk; sk=x-x0; yk=feval(gfun,x,varargin{:})-gk; if(yk’*sk>0)