Optimization: principles and algorithms, by Michel Bierlaire
steepestDescentCauchy.m
Go to the documentation of this file.
1 %> \file
2 %> Steepest descent algorithm, calculating the Cauchy point at each iteration.
3 %>
4 %> @author <a href="http://people.epfl.ch/michel.bierlaire">Michel Bierlaire</a>
5 %> @date Fri Mar 20 17:07:48 2015
6 %> @ingroup Algorithms
7 %> @ingroup chap11
8
9
10 %>
11 %> Applies the steepest descent algorithm to solve \f$\min_x f(x)\f$ where \f$f:\mathbb{R}^n\to\mathbb{R}\f$. The Cauchy point is calculated at each iteration.
12
13 %> \note Tested with \ref run1101cauchy.m
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$\|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] = steepestDescentCauchy(obj,x0,eps,maxiter = 100)
24  xk = x0 ;
25  [f,g,H] = feval(obj,xk) ;
26  iteres = zeros(1+ maxiter,4) ;
27  k = 0 ;
28  iteres(1,:) = [xk' f norm(g) ] ;
29  do
30  denom = g' * H * g ;
31  if (denom <= 0)
32  error("The function is not convex in the direction of the gradient. The Cauchy point is not defined.")
33  endif
34  alpha = g' * g / denom ;
35  xk = xk - alpha * g ;
36  [f,g,H] = feval(obj,xk);
37  k=k+1 ;
38  iteres(k+1,:) = [xk' f norm(g) ] ;
39  until (norm(g) <= eps || k >= maxiter)
40  solution = xk ;
41  niter = k ;
42 endfunction
function steepestDescentCauchy(in obj, in x0, in eps, in maxiter)
Applies the steepest descent algorithm to solve where . The Cauchy point is calculated at each itera...
Copyright 2015-2016 Michel Bierlaire