Optimization: principles and algorithms, by Michel Bierlaire
lineSearch.m
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 11.5: Line search algorithm. Implementation of algorithm 11.5 of \cite Bier15-book
3 %>
4 %> @author <a href="http://people.epfl.ch/michel.bierlaire">Michel Bierlaire</a>
5 %> @date Fri Mar 20 17:42:10 2015
6 %> @ingroup Algorithms
7 %> @ingroup chap11
8
9 %> \note Tested with \ref runInexactLineSearch.m
10 %> \note Called by \ref steepestDescent
11 %> \note Called by \ref newtonLineSearch
12
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)
24  if (lambda <= 1)
25  error("lambda must be > 1 and is %f",lambda)
26  endif
27  if (alpha0 <= 0)
28  error("alpha0 must be > 0 and is %f",alpha0)
29  endif
30  if (beta1 >= beta2)
31  error("Incompatible Wolfe cond. beta1 = %f beta2 = %f",beta1,beta2)
32  endif
33  [f,g] = feval(obj,x) ;
34  deriv = g' * d ;
35  if (deriv >= 0)
36  error("d is not a descent direction: %.4e\n",g'*d) ;
37  endif
38  i = 0 ;
39  alpha = alpha0 ;
40  alphal = 0 ;
41  alphar = 999999 ;
42  ok = 0 ;
43  do
44  if (printlevel != 0)
45  printf("%e\t%e\t%e\t",alpha,alphal,alphar) ;
46  endif
47  xnew = x+alpha * d ;
48  [fnew,gnew] = feval(obj,xnew) ;
49  if (fnew > f + alpha * beta1 * deriv)
50  if (printlevel != 0)
51  printf("too long\n" ) ;
52  endif
53  # Step is too long
54  alphar = alpha ;
55  alpha = (alphal + alphar) / 2.0 ;
56  else
57  if (gnew'*d < beta2 * deriv)
58  if (printlevel != 0)
59  printf("too short\n") ;
60  endif
61  # Insufficient decrease
62  alphal = alpha ;
63  if (alphar == 999999)
64  alpha = lambda * alpha ;
65  else
66  alpha = (alphal + alphar) / 2.0 ;
67  endif
68  else
69  if (printlevel != 0)
70  printf("ok\n") ;
71  endif
72  ok = 1 ;
73  endif
74  endif
75  until (ok == 1)
76 endfunction
function newtonLineSearch(in obj, in x0, in eps, in printlevel)
Applies Newton&#39;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...