2 %> Algorithm 12.4: Newton
's method with trust region. Implementation of algorithm 12.4 of \cite Bier15-book 4 %> @author Michel Bierlaire 5 %> @date Sat Mar 21 16:04:27 2015 9 %> Applies Newton's algorithm with trust region to solve \f$\min_x f(x)\f$ where \f$f:\mathbb{R}^n\to\mathbb{R}\f$. The parameters of the method are taken from \cite ConnGoulToin00 (p. 117).
11 %> @note Tested with \ref run0508tr.m
12 %> @note Tested with \ref runRosenbrockTrustRegion.m
16 %> @param obj the name of the Octave
function defining f(x) and its derivatives
17 %> @param x0 the starting point
18 %> @param delta0 radius of the initial trust region
19 %> @param eps algorithm stops if \f$\|F(x)\| \leq \varepsilon \f$.
20 %> @param tr method to solve the trust region subproblem. If 0, the
dogleg method is used. If different from 0, the truncated conjugate gradient is used (
default: 0).
21 %> @param maxiter maximum number of iterations (Default: 100)
22 %> @
return [solution,iteres,niter]
23 %> @
return solution: local minimum of the
function 24 %> @
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.
25 %> @
return niter: total number of iterations
26 function [solution,iteres,niter] =
newtonTrustRegion(obj,x0,delta0,eps, tr=0,maxiter=100)
28 iteres = zeros(1+ maxiter,4) ;
35 [f,g,H] = feval(obj,xk) ;
36 iteres(1,:) = [xk' f norm(g) ] ;
39 printf("%+10.5e,%+10.5e\n",xk(1),xk(2)) ;
43 [step,type] =
dogleg(g,H,delta) ;
47 [fc,gc,Hc] = feval(obj,xk+step) ;
49 denom = -step'*g - 0.5 * step' * H * step ;
52 delta = norm(step) / 2.0 ;
66 iteres(k+1,:) = [xk' f norm(g) ] ;
67 until (norm(g) <= eps || k >= maxiter)
function dogleg(in g, in H, in delta)
Given a current iterate , consider the trust region subproblem subject to Apply the Dogleg method t...
function truncatedConjugateGradient(in g, in H, in delta)
Given a current iterate , consider the trust region subproblem subject to Apply the truncated conju...
function newtonTrustRegion(in obj, in x0, in delta0, in eps, in tr)
Applies Newton's algorithm with trust region to solve where . The parameters of the method are taken...