JMU
One-Dimensional Optimization
An Introduction with Examples


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu


Motivation
An Example
An Example (cont.)
The Golden Section Algorithm
images/goldensection01.gif
The Golden Section Algorithm (cont.)
images/goldensection02.gif
The Golden Section Algorithm (cont.)
The Golden Section Algorithm (cont.)

In Pseudocode

    Choose an initial lower bound L and upper bound U

    Set t_L equal to L + 0.382 * (U - L)
    Set t_R equal to L + 0.618 * (U - L)

    while (U - L is too large} {

      if (The objective function evaluated at t_L is greater
          than the objective function evaluated at t_R) {

            Set U equal to t_R
            Set t_R equal to t_L
            Set t_L equal to L + 0.382 * (U - L)

      } else {

            Set L equal to t_L
            Set t_L equal to t_R
            Set t_R equal to  L + 0.618 * (U - L)
      }
    }
    
Solving the Example

Bounds: 0, 800

Iter. L tL tR U
1 0.00 305.57 494.43 800.00
2 0.00 188.85 305.57 494.43
3 188.85 305.57 377.71 494.43
4 188.85 260.99 305.57 377.71
5 188.85 233.44 260.99 305.57
6 233.44 260.99 278.02 305.57
7 233.44 250.47 260.99 278.02
8 233.44 243.96 250.47 260.99
9 243.96 250.47 254.49 260.99
10 243.96 247.98 250.47 254.49
11 247.98 250.47 252.00 254.49
12 247.98 249.52 250.47 252.00
13 249.52 250.47 251.05 252.00
14 249.52 250.10 250.47 251.05
An Implementation
cppexamples/optimization/GoldenSection.cpp
        #include "Maximize.h"

/**
 * Maximize a "well-behaved" function using the Golden Section algorithm
 */
double maximize(double (*f)(double), double L_0, double U_0, double tol) {
  double L, t_L, t_R, U;

  // Initialize
  L = L_0;
  U = U_0;

  t_L = L + 0.382 * (U - L);
  t_R = L + 0.618 * (U - L);

  // Iterate
  while ((U - L) > tol) {
    if (f(t_L) > f(t_R)) {
//       L   = L;
      U = t_R;
      t_R = t_L;
      t_L = L + 0.382 * (U - L);
    } else {
      L = t_L;
//       U   = U;
      t_L = t_R;
      t_R = L + 0.618 * (U - L);
    }
  }

  return (U + L) / 2.0;
}