Optimization: principles and algorithms, by Michel Bierlaire
Go to the documentation of this file.
1 %> \file
2 %> Algorithm 11.3: Exact line search using quadratic interpolation. Implementation of algorithm 11.3 of \cite Bier15-book
3 %>
4 %> @author <a href="http://people.epfl.ch/michel.bierlaire">Michel Bierlaire</a>
5 %> @date Fri Mar 20 17:21:38 2015
6 %> @ingroup Algorithms
7 %> @ingroup chap11
8
9 %> \note Tested with \ref runQuadraticInterpolation.m
10 %> \note Calls \ref initLineSearch
11
12 %> Find a local minimum of the problem \f$\min_{x \geq 0} h(x)\f$, where \f$h:\mathbb{R}\to\mathbb{R}\f$.
13 %> @param obj the name of the Octave function defining h(x)
14 %> @param delta the parameter to initialize the line search. Must be such that \f$h(\delta) < h(0)\f$.
15 %> @param eps tolerance.
16 %> @return xstar the local minimum
18  [a,ha,b,hb,c,hc] = initLineSearch(obj,delta) ;
19  k = 1 ;
20  do
21  beta1 = ((b-c)*ha+(c-a)*hb+(a-b)*hc)/((a-b)*(c-a)*(c-b)) ;
22  beta2 = hb / (b-a) ;
23  beta3 = ha / (a-b) ;
24  xplus = (beta1 * (a+b) - beta2 - beta3) / (2 * beta1) ;
25  if (xplus == b)
26  if ((b-a) < (c-b))
27  xplus = b + eps / 2.0 ;
28  else
29  xplus = b - eps / 2.0 ;
30  endif
31  endif
32  hxplus = feval(obj,xplus) ;
33  printf("%d\t%.6g\t%.6g\t%.6g\t%.6g\t%.6g\t%.6g\t%.6g\t%.6g\n",k,a,b,c,xplus,ha,hb,hc,hxplus)
34  if (xplus > b)
35  if (hxplus > hb)
36  c = xplus ;
37  hc = hxplus;
38  else
39  a = b ;
40  ha = hb ;
41  b = xplus ;
42  hb = hxplus ;
43  endif
44  else
45  if (hxplus > hb)
46  a = xplus ;
47  ha = hxplus ;
48  else
49  c = b ;
50  hc = hb ;
51  b = xplus ;
52  hb = hxplus ;
53  endif
54  endif
55  s1 = max(ha,hc)-hb ;
56  s2 = c-a ;
57  k = k + 1;
58  until (s1 <= eps || s2 <= eps)
59  xstar = b ;
60  printf("%d\t%.6g\t%.6g\t%.6g\t%.6g\t%.6g\t%.6g\t%.6g\t%.6g\n",k,a,b,c,xplus,ha,hb,hc,hxplus)
61  endfunction
62
function quadraticInterpolation(in obj, in delta, in eps)
Find a local minimum of the problem , where .
function initLineSearch(in obj, in delta)
Calculate , and such that , and .