2 %> Algorithm 11.5: Line search algorithm. Implementation of algorithm 11.5 of \cite Bier15-book
4 %> @author <a href=
"http://people.epfl.ch/michel.bierlaire">Michel Bierlaire</a>
5 %> @date Fri Mar 20 17:42:10 2015
9 %> \note Tested with \ref runInexactLineSearch.m
13 %> Applies the line search algorithm to find a step along a direction that verifies the Wolfe conditions.
14 %> @param obj objective function \f$f:\mathbb{R}^n \to \mathbb{R} \f$.
15 %> @param x current iterate
16 %> @param d direction
for the line search
17 %> @param alpha0 initial step
18 %> @param beta1 parameter
for the first Wolfe condition (strictly between 0 and 1. Suggested value: 1.0e-4)
19 %> @param beta2 parameter
for the second Wolfe condition (strictly between beta1 and 1. Suggested value: 0.99)
20 %> @param lambda expansion factor
for short steps
21 %> @param printlevel
if different from 0, informations are printed at each iteration (Default: 0)
22 %> @
return step alpha verifying the two Wolfe conditions
23 function alpha =
lineSearch(obj,x,d,alpha0,beta1,beta2,lambda,printlevel=0)
25 error("lambda must be > 1 and is %f",lambda)
28 error("alpha0 must be > 0 and is %f",alpha0)
31 error("Incompatible Wolfe cond. beta1 = %f beta2 = %f",beta1,beta2)
33 [f,g] = feval(obj,x) ;
36 error("d is not a descent direction: %.4e\n",g'*d) ;
45 printf("%e\t%e\t%e\t",alpha,alphal,alphar) ;
48 [fnew,gnew] = feval(obj,xnew) ;
49 if (fnew > f + alpha * beta1 * deriv)
51 printf("too
long\n" ) ;
55 alpha = (alphal + alphar) / 2.0 ;
57 if (gnew
'*d < beta2 * deriv) 59 printf("too short\n") ; 61 # Insufficient decrease 64 alpha = lambda * alpha ; 66 alpha = (alphal + alphar) / 2.0 ; function newtonLineSearch(in obj, in x0, in eps, in printlevel)
Applies Newton's algorithm with line search to solve where .
function steepestDescent(in obj, in x0, in eps, in maxiter)
Applies the steepest descent algorithm with linesearch 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...