- Forward


One-Dimensional Optimization
An Introduction with Examples


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back SMYC Forward
  • An Observation:
    • There are many real-world applications in which one needs to find the maximum (or minimum) of a function
  • A Reminder:
    • One way to solve such a problem is to take the derivative of the function, set it equal to 0, and solve the resulting equation
  • A Difficulty:
    • In many cases this is not possible
An Example
Back SMYC Forward
  • The Chip Monk Chocolate Chip Cookie Company:
    • A local supermarket has agreed to pay you $3.00 per pound for as many pounds of cookies as you can produce
    • The cost of producing cookies varies with the number of cookies you produce
  • Some Details:
    • Revenue: \(R(q) = 3q\)
    • Production Cost: \(C(q) = 0.5 q\)
    • Shipping Cost: \(S(q) = 0.0005 q^{2}\)
An Example (cont.)
Back SMYC Forward
  • Profit:
    • \(\pi(q) = R(q) - C(q) - S(q) = 3.0 q - 0.5 q - 0.005 q^{2} \)
  • Maximizing Profit:
    • We could use calculus in this case
    • We want to use a numerical algorithm for illustrative purposes
The Golden Section Algorithm
Back SMYC Forward
goldensection01
The Golden Section Algorithm (cont.)
Back SMYC Forward
goldensection02
The Golden Section Algorithm (cont.)
Back SMYC Forward
  • Updating the Test Points:
    • Use the golden ratio [\(0.5 (\sqrt{5} - 1)\)]
    • Set \(t_L\) equal to \(L + 0.382 (U - L)\)
    • Set \(t_R\) equal to \(L + 0.618 (U - L)\)
  • Why?
    • It's not important
    • Other values between 0.5 and 1 can be used
The Golden Section Algorithm (cont.)
Back SMYC Forward

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
Back SMYC Forward

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
Back SMYC Forward
cppexamples/optimization/GoldenSection.cpp
 
There's Always More to Learn
Back -