Talk:Quasi-Newton method

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Relation to Gauss-Newton / Gradient Descent / Levenberg-Marquardt methods[edit]

This topic is somehow related to Gauss-Newton method and Levenberg-Marquardt Method and Gradient descent. None of these requires second derivatives. Gauss-Newton, however, requires an overdetermined system.

The exact relations are not stated in this article. It would be helpful to show different assumptions or what the algorithms do have in common with quasi-Newton-methods.

Matlab Code[edit]

The Matlab code presented here is incomplete and unsourced. It calls subroutines Grad() and LineSearchAlfa() that are not defined. Also, there is no indication of the author or source of the code, or of the copyright status of the code. Unless this information can be determined, it should probably be deleted. J Shailer (talk) 19:22, 5 March 2012 (UTC)

I agree completely with Shailer. Regardless of the quality of the code, this is not the right venue (the right venue is http://www.mathworks.com/matlabcentral/fileexchange/). I propose a compromise step of moving the code to the talk page for now. Lavaka (talk) 13:29, 7 March 2012 (UTC)
I am posting that code here: Lavaka (talk) 13:34, 7 March 2012 (UTC)

Here is a Matlab example which uses the BFGS method.

%***********************************************************************%
% Usage: [x,Iter,FunEval,EF] = Quasi_Newton (fun,x0,MaxIter,epsg,epsx)
%         fun: name of the multidimensional scalar objective function
%              (string). This function takes a vector argument of length
%              n and returns a scalar.
%          x0: starting point (row vector of length n).
%     MaxIter: maximum number of iterations to find a solution.
%        epsg: maximum acceptable Euclidean norm of the gradient of the
%              objective function at the solution found.
%        epsx: minimum relative change in the optimization variables x.
%           x: solution found (row vector of length n).
%        Iter: number of iterations needed to find the solution.
%     FunEval: number of function evaluations needed.
%          EF: exit flag,
%              EF=1: successful optimization (gradient is small enough).
%              EF=2: algorithm converged (relative change in x is small 
%                    enough).
%              EF=-1: maximum number of iterations exceeded.
 
%  C) Quasi-Newton optimization algorithm using (BFGS)                  %
 
function [x,i,FunEval,EF]= Quasi_Newton (fun, x0, MaxIter, epsg, epsx) 
%   Variable Declaration 
 xi        = zeros(MaxIter+1,size(x0,2));
 xi(1,:)   = x0;
 Bi        = eye(size(x0,2));
 
%  CG algorithm
FunEval = 0;
EF = 0;
 
  for i = 1:MaxIter
 
      %Calculate Gradient around current point
      [GradOfU,Eval] =  Grad (fun, xi(i,:));
      FunEval        =  FunEval + Eval;       %Update function evaluation
 
      %Calculate search direction 
      di             = -Bi\GradOfU ;
 
      %Calculate Alfa via exact line search 
      [alfa, Eval]   =  LineSearchAlfa(fun,xi(i,:),di);      
      FunEval        =  FunEval + Eval;       %Update function evaluation
 
      %Calculate Next solution of X    
      xi(i+1,:)      =  xi(i,:) + (alfa*di)';
 
      % Calculate Gradient of X on i+1
      [Grad_Next, Eval] =  Grad (fun, xi(i+1,:));
      FunEval           =  FunEval + Eval;       %Update function evaluation
 
      %Calculate new Beta value using BFGS algorithm            
      Bi                =  BFGS(fun,GradOfU,Grad_Next,xi(i+1,:),xi(i,:), Bi);         
 
      % Calculate maximum acceptable Euclidean norm of the gradient
      if norm(Grad_Next,2) < epsg
          EF        = 1;
          break
      end
 
      % Calculate minimum relative change in the optimization variables
      E            =   xi(i+1,:)- xi(i,:);
      if norm(E,2) < epsx
          EF       = 2;
          break
      end
  end
  % report optimum solution
   x    = xi(i+1,:);
 
  if i == MaxIter
  % report Exit flag that MaxNum of iterations reach      
     EF =  -1;
  end
 
  % report MaxNum of iterations reach  
  Iter  = i;
 
end
 
%***********************************************************************%
% Broyden, Fletcher, Goldfarb and Shanno (BFGS) formula
%***********************************************************************%
function  B  = BFGS(fun,GradOfU,Grad_Next,Xi_next,Xi,Bi)
 
 % Calculate Si term
  si               =  Xi_next   - Xi;
 
 % Calculate Yi term
  yi               =  Grad_Next - GradOfU;
 %
 % BFGS formula (Broyden, Fletcher, Goldfarb and Shanno)
 %
  B   =  Bi - ((Bi*si'*si*Bi)/(si*Bi*si')) + ((yi*yi')/(yi'*si'));
 
end