Optimization: principles and algorithms, by Michel Bierlaire
newtonLocalQuadratic.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 10.2: Local Newton for optimization using the quadratic model. Implementation of algorithm 10.2 of \cite Bier15-book
3 %>
4 %> @author <a href="http://people.epfl.ch/michel.bierlaire">Michel Bierlaire</a>
5 %> @date Fri Mar 20 16:14:06 2015
6 %> @ingroup Algorithms
7 %> @ingroup chap10
8 
9 %> @note Tested with \ref run0508quadratic.m
10 %> @note Calls \ref quadraticDirect
11 %> @note Calls \ref conjugateGradient
12 
13 %> Applies local Newton algorithm to solve \f$\nabla f(x)=0\f$ where \f$\nabla f:\mathbb{R}^n\to\mathbb{R}^n \f$ is the gradient of the objective function.
14 %> @param obj the name of the Octave function defining \f$\nabla f(x)\f$ and the hessian \f$\nabla^2 f(x)\f$
15 %> @param x0 the starting point
16 %> @param eps algorithm stops if \f$\|F(x)\| \leq \varepsilon \f$.
17 %> @param cg if 0, the quadratic model is solved using the direct method. If not zero, using the conjugate gradient algorithm.
18 %> @param maxiter maximum number of iterations (Default: 100)
19 %> @return [solution,f]
20 %> @return solution: root of the function
21 %> @return f: value of F at the solution
22 function [solution,g] = newtonLocalQuadratic(obj,x0,eps,cg,maxiter=100)
23  addpath("../chap09") ;
24  xk = x0 ;
25  [g,H] = feval(obj,xk) ;
26  k = 0 ;
27  do
28  if (cg == 0)
29  d = quadraticDirect(H,g) ;
30  else
31  % Note that the CG algorithm is started from 0.
32  [directions, d] = conjugateGradient(H,g,zeros(size(g))) ;
33  endif
34  xk = xk + d ;
35  [g,H] = feval(obj,xk) ;
36  k=k+1;
37  until (norm(g) <= eps || k >= maxiter)
38  solution = xk ;
39 endfunction
function newtonLocalQuadratic(in obj, in x0, in eps, in cg, in maxiter)
Applies local Newton algorithm to solve where is the gradient of the objective function.
function quadraticDirect(in Q, in b)
Applies the direct resolution method to solve where and .
function conjugateGradient(in Q, in b, in x0, in printlevel)
Applies the conjugate gradient method to solve where and .
Copyright 2015-2016 Michel Bierlaire