bfgs.m

Go to the documentation of this file.

%> \file
%>  Algorithm 13.1: BFGS method with line search. Implementation of algorithm 13.1 of \cite Bier15-book
%> 
%> @author Michel Bierlaire
%> @date Sat Mar 21 16:29:03 2015
%> @ingroup Algorithms
%> @ingroup chap13

%> Applies BFGS algorithm with line search to solve \f$\min_x f(x)\f$ where \f$f:\mathbb{R}^n\to\mathbb{R}\f$. 

%> @note Tested with \ref run0508bfgs.m
%> @note Tested with \ref runRosenbrockBfgs.m
%> @note Calls \ref lineSearch

%> @param obj the name of the Octave function defining f(x) and its derivatives
%> @param x0 the starting point
%> @param eps  algorithm stops if \f$\|\nabla f(x)\| \leq \varepsilon \f$. 
%> @param maxiter maximum number of iterations (Default: 100)
%> @return [solution,iteres,niter] 
%> @return solution: local minimum of the function
%> @return iteres: sequence of iterates generated by the algorithm. It contains n+2 columns. Columns 1:n contains the value of the current iterate. Column n+1 contains the value of the objective function. Column n+2 contains the value of the norm of the gradient. It contains maxiter rows, but only the first niter rows are meaningful.
%> @return niter: total number of iterations
function [solution,iteres,niter] = bfgs(obj,x0,eps,maxiter=100)
  addpath("../chap11") ;
  iteres = zeros(1+ maxiter,4) ;
  n = size(x0,1) ;
  I = eye(n) ;
  Hinv = eye(n) ; 
  xk = x0 ;
  [f,g] = feval(obj,xk)  ;
  iteres(1,:) = [xk'  f  norm(g) ] ;
  k = 0 ;
  do
    d = - Hinv * g ;
    alpha = lineSearch(obj,xk,d,1.0,0.3,0.7,2) ;
    xold = xk ;
    gold = g ;
    xk = xk + alpha * d ;
    [f,g,H] = feval(obj,xk);
    k=k+1 ; 
    iteres(k+1,:) = [xk' f  norm(g) ] ;
    d = xk - xold ;
    y = g - gold ;
    denom = d' * y ;
    Hinv = (I - (d * y') / denom) * Hinv * (I - (y * d') / denom) + d * d' / \
      denom ;
  until (norm(g) <= eps || k >= maxiter)
  solution = xk ;
  niter = k ;
endfunction