Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
golden_search_extrema.cpp File Reference

Find extrema of a univariate real function in a given interval using golden section search algorithm. More...

#include <cassert>
#include <cmath>
#include <functional>
#include <iostream>
#include <limits>
Include dependency graph for golden_search_extrema.cpp:

Macros

#define _USE_MATH_DEFINES
 
#define EPSILON   1e-7
 solution accuracy limit
 

Functions

double get_minima (const std::function< double(double)> &f, double lim_a, double lim_b)
 Get the minima of a function in the given interval. To get the maxima, simply negate the function. The golden ratio used here is: More...
 
void test1 ()
 Test function to find minima for the function \(f(x)= (x-2)^2\) in the interval \([1,5]\)
Expected result = 2.
 
void test2 ()
 Test function to find maxima for the function \(f(x)= x^{\frac{1}{x}}\) in the interval \([-2,10]\)
Expected result: \(e\approx 2.71828182845904509\).
 
void test3 ()
 Test function to find maxima for the function \(f(x)= \cos x\) in the interval \([0,12]\)
Expected result: \(\pi\approx 3.14159265358979312\).
 
int main ()
 

Detailed Description

Find extrema of a univariate real function in a given interval using golden section search algorithm.

See also
brent_method_extrema.cpp
Author
Krishna Vedala

Function Documentation

◆ get_minima()

double get_minima ( const std::function< double(double)> &  f,
double  lim_a,
double  lim_b 
)

Get the minima of a function in the given interval. To get the maxima, simply negate the function. The golden ratio used here is:

\[ k=\frac{3-\sqrt{5}}{2} \approx 0.381966\ldots\]

Parameters
ffunction to get minima for
lim_alower limit of search window
lim_bupper limit of search window
Returns
local minima found in the interval
30  {
31  uint32_t iters = 0;
32  double c, d;
33  double prev_mean, mean = std::numeric_limits<double>::infinity();
34 
35  // golden ratio value
36  const double M_GOLDEN_RATIO = (1.f + std::sqrt(5.f)) / 2.f;
37 
38  // ensure that lim_a < lim_b
39  if (lim_a > lim_b) {
40  std::swap(lim_a, lim_b);
41  } else if (std::abs(lim_a - lim_b) <= EPSILON) {
42  std::cerr << "Search range must be greater than " << EPSILON << "\n";
43  return lim_a;
44  }
45 
46  do {
47  prev_mean = mean;
48 
49  // compute the section ratio width
50  double ratio = (lim_b - lim_a) / M_GOLDEN_RATIO;
51  c = lim_b - ratio; // right-side section start
52  d = lim_a + ratio; // left-side section end
53 
54  if (f(c) < f(d)) {
55  // select left section
56  lim_b = d;
57  } else {
58  // selct right section
59  lim_a = c;
60  }
61 
62  mean = (lim_a + lim_b) / 2.f;
63  iters++;
64 
65  // continue till the interval width is greater than sqrt(system epsilon)
66  } while (std::abs(lim_a - lim_b) > EPSILON);
67 
68  std::cout << " (iters: " << iters << ") ";
69  return prev_mean;
70 }
Here is the call graph for this function:

◆ main()

int main ( void  )

Main function

139  {
140  std::cout.precision(9);
141 
142  std::cout << "Computations performed with machine epsilon: " << EPSILON
143  << "\n";
144 
145  test1();
146  test2();
147  test3();
148 
149  return 0;
150 }
Here is the call graph for this function:
EPSILON
#define EPSILON
solution accuracy limit
Definition: golden_search_extrema.cpp:17
test3
void test3()
Test function to find maxima for the function in the interval Expected result: .
Definition: golden_search_extrema.cpp:123
std::sqrt
T sqrt(T... args)
test1
void test1()
Test function to find minima for the function in the interval Expected result = 2.
Definition: golden_search_extrema.cpp:78
std::numeric_limits::infinity
T infinity(T... args)
std::cerr
std::swap
T swap(T... args)
test2
void test2()
Test function to find maxima for the function in the interval Expected result: .
Definition: golden_search_extrema.cpp:100