newtonLineSearch.m

Go to the documentation of this file.

%> \file
%> Algorithm 11:8 Newton's method with line search . Implementation of algorithm 11.8 of \cite Bier15-book
%> 
%> @author <a href="http://people.epfl.ch/michel.bierlaire">Michel Bierlaire</a>
%> @date Sat Mar 21 12:34:40 2015
%> @ingroup Algorithms
%> @ingroup chap11

%> \note Tested with \ref run0508newton.m
%> \note Tested with \ref runRosenbrockNewtonLineSearch.m
%> \note Calls \ref modifiedCholesky
%> \note Calls \ref lineSearch

%> Applies Newton's algorithm with line search to solve \f$\min_x f(x)\f$ where \f$f:\mathbb{R}^n\to\mathbb{R}\f$
%> @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$\|F(x)\| \leq \varepsilon \f$. 
%> @param printlevel If 1, information about iterations is printed. If 0, it is silent.
%> @param maxiter maximum number of iterations (Default: 100)
%> @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] = newtonLineSearch(obj,x0,eps,printlevel=1,maxiter=100)
  iteres = zeros(1+ maxiter,4) ;
  xk = x0 ;
  [f,g,H] = feval(obj,xk)  ;
  iteres(1,:) = [xk'  f  norm(g) ] ;
  k = 0 ;
  if (printlevel != 0)
    printf("f\t\t||g||\t\talpha\t\ttau\n");
    printf("%e\t%e\n",f,norm(g)) ;
  endif
  alpha0 = 1.0 ;
  beta1 = 1.0e-4  ;
  beta2 = 0.99 ;
  lambda = 2  ;
  lsprintlevel=printlevel ;
do
    [L,tau] = modifiedCholesky(H) ;
    z = L \ g ;
    d = - L' \ z ;
    alpha = lineSearch(obj,xk,d,alpha0,beta1,beta2,lambda,lsprintlevel) ;
    xk = xk + alpha * d ;
    [f,g,H] = feval(obj,xk);
    if (printlevel != 0)
      printf("%e\t%e\t%f\t%e\n",f,norm(g),alpha,tau) ;
    endif
    k=k+1 ; 
    iteres(k+1,:) = [xk' f  norm(g) ] ;
  until (norm(g) <= eps || k >= maxiter)
  solution = xk ;
  niter = k ;
endfunction