Optimization: principles and algorithms, by Michel Bierlaire
goldenSection.m
Go to the documentation of this file.
1 %> \file
2 %> Exact line search using golden section
3 %>
4 %> @author <a href="http://people.epfl.ch/michel.bierlaire">Michel Bierlaire </a>
5 %> @date Fri Mar 20 17:38:25 2015
6 %> @ingroup Algorithms
7 %> @ingroup chap11
8
9
10 %> Find the global minimum of \f$h(\alpha)\f$ on \f$[\ell,u]\f$, where \f$h:\mathbb{R}\to\mathbb{R}\f$ is strictly unimodular on \f$[\ell,u]\f$. If the function is not strictly unimodular, the result is unspecified.
11
12 %> \note Tested with \ref runGoldenSection.m
13
14 %> @param obj the name of the Octave function defining h(x)
15 %> @param l the lower bound of the interval
16 %> @param u the upper bound of the interval
17 %> @param eps tolerance.
18 %> @return xstar the local minimum
19 function xstar = goldenSection(obj,l,u,eps)
20  rho = (3.0 - sqrt(5.0)) / 2.0 ;
21  alpha1 = l + rho * (u - l) ;
22  h1 = feval(obj,alpha1) ;
23  alpha2 = u - rho * (u - l) ;
24  h2 = feval(obj,alpha2) ;
25  k = 1 ;
26  do
27  printf("%d\t%.6g\t%.6g\t%.6g\t%.6g\t%.6g\t%.6g\n",k,l,alpha1,alpha2,u,h1,h2)
28  if (h1 == h2)
29  l = alpha1 ;
30  u = alpha2 ;
31  alpha1 = l + rho * (u - l) ;
32  h1 = feval(obj,alpha1) ;
33  alpha2 = u - rho * (u - l) ;
34  h2 = feval(obj,alpha2) ;
35  elseif (h1 > h2)
36  l = alpha1 ;
37  alpha1 = alpha2 ;
38  h1 = h2 ;
39  alpha2 = u - rho * (u - l) ;
40  h2 = feval(obj,alpha2) ;
41  else
42  u = alpha2 ;
43  alpha2 = alpha1 ;
44  h2 = h1 ;
45  alpha1 = l + rho * (u - l) ;
46  h1 = feval(obj,alpha1) ;
47  endif
48  k = k + 1 ;
49  until((u - l) <= eps)
50  printf("%d\t%.6g\t%.6g\t%.6g\t%.6g\t%.6g\t%.6g\n",k,l,alpha1,alpha2,u,h1,h2)
51  xstar = (l+u)/2.0 ;
52 endfunction
53
function goldenSection(in obj, in l, in u, in eps)
Find the global minimum of on , where is strictly unimodular on . If the function is not strictly u...
Copyright 2015-2016 Michel Bierlaire