Optimization: principles and algorithms, by Michel Bierlaire
newtonFinDiffNVariables.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 8.3: Newton's method with finite differences, n variables. Implementation of algorithm 8.3 of \cite Bier15-book
3 %>
4 %> @author <a href="http://people.epfl.ch/michel.bierlaire">Michel Bierlaire</a>
5 %> @date Thu Mar 19 18:26:50 2015
6 %> @ingroup Algorithms
7 %> @ingroup chap08
8 
9 %> @note Tested with \ref run0711df.m
10 
11 %> Applies Newton's algorithm with finite differences to solve \f$F(x)=0\f$ where \f$F:\mathbb{R}^n\to\mathbb{R}^n \f$
12 %> @param obj the name of the Octave function defining F(x) and its Jacobian
13 %> @param x0 the starting point
14 %> @param tau step for the finite difference approximation
15 %> @param eps algorithm stops if \f$\|F(x)\| \leq \varepsilon \f$.
16 %> @param maxiter maximum number of iterations (Default: 100)
17 %> @return root of the system
18 function solution = newtonFinDiffNVariables(obj,x0,tau,eps,maxiter=100)
19  xk = x0 ;
20  f = feval(obj,xk) ;
21  k = 0 ;
22  printf("%2d %+15.8e %+15.8e %+15.8e\n",k,xk(1),f(1),norm(f)) ;
23  printf(" %+15.8e %+15.8e\n",xk(2),f(2)) ;
24  n = size(x0,1) ;
25  do
26  for i=1:n
27  if (abs(xk(i)) >= 1)
28  s = tau * xk(i) ;
29  else
30  if (xk(i) >= 0)
31  s = tau ;
32  else
33  s = -tau ;
34  endif
35  endif
36  ei = eye(n,n)(:,i) ;
37  fp = feval(obj,xk+s * ei) ;
38  A(:,i) = (fp - f) / s ;
39  endfor
40  xk = xk - A \ f ;
41  f = feval(obj,xk) ;
42  k=k+1;
43  printf("%2d %+15.8e %+15.8e %+15.8e\n",k,xk(1),f(1),norm(f)) ;
44  printf(" %+15.8e %+15.8e\n",xk(2),f(2)) ;
45  until (norm(f) <= eps || k >= maxiter)
46  solution = xk ;
47 endfunction
function newtonFinDiffNVariables(in obj, in x0, in tau, in eps, in maxiter)
Applies Newton&#39;s algorithm with finite differences to solve where .
Copyright 2015-2016 Michel Bierlaire