Optimization: principles and algorithms, by Michel Bierlaire
bfgs.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 13.1: BFGS method with line search. Implementation of algorithm 13.1 of \cite Bier15-book
3 %>
4 %> @author Michel Bierlaire
5 %> @date Sat Mar 21 16:29:03 2015
6 %> @ingroup Algorithms
7 %> @ingroup chap13
8
9 %> Applies BFGS algorithm with line search to solve \f$\min_x f(x)\f$ where \f$f:\mathbb{R}^n\to\mathbb{R}\f$.
10
11 %> @note Tested with \ref run0508bfgs.m
12 %> @note Tested with \ref runRosenbrockBfgs.m
13 %> @note Calls \ref lineSearch
14
15 %> @param obj the name of the Octave function defining f(x) and its derivatives
16 %> @param x0 the starting point
17 %> @param eps algorithm stops if \f$\|\nabla f(x)\| \leq \varepsilon \f$.
18 %> @param maxiter maximum number of iterations (Default: 100)
19 %> @return [solution,iteres,niter]
20 %> @return solution: local minimum of the function
21 %> @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.
22 %> @return niter: total number of iterations
23 function [solution,iteres,niter] = bfgs(obj,x0,eps,maxiter=100)
25  iteres = zeros(1+ maxiter,4) ;
26  n = size(x0,1) ;
27  I = eye(n) ;
28  Hinv = eye(n) ;
29  xk = x0 ;
30  [f,g] = feval(obj,xk) ;
31  iteres(1,:) = [xk' f norm(g) ] ;
32  k = 0 ;
33  do
34  d = - Hinv * g ;
35  alpha = lineSearch(obj,xk,d,1.0,0.3,0.7,2) ;
36  xold = xk ;
37  gold = g ;
38  xk = xk + alpha * d ;
39  [f,g,H] = feval(obj,xk);
40  k=k+1 ;
41  iteres(k+1,:) = [xk' f norm(g) ] ;
42  d = xk - xold ;
43  y = g - gold ;
44  denom = d' * y ;
45  Hinv = (I - (d * y') / denom) * Hinv * (I - (y * d') / denom) + d * d' / \
46  denom ;
47  until (norm(g) <= eps || k >= maxiter)
48  solution = xk ;
49  niter = k ;
50 endfunction
function bfgs(in obj, in x0, in eps, in maxiter)
Applies BFGS algorithm with line search to solve where .
function lineSearch(in obj, in x, in d, in alpha0, in beta1, in beta2, in lambda, in printlevel)
Applies the line search algorithm to find a step along a direction that verifies the Wolfe conditions...