- Forward


Unconstrained Multidimensional Optimization
An Introduction with Examples in Java


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back Forward
  • A Question:
    • How would you climb to the top of a hill on a foggy night?
  • One Approach:
    • Wander aimlessly until you can't take an uphill step in any direction
  • Another Approach:
    • Only walk uphill
    • Don't walk too far
      images/toofar.gif
    • Stop when you can't find an uphill direction to walk in
Motivation (cont.)
Back Forward

An Illustration of the Ascent Algorithm

images/ascent.gif
A Generic Ascent Algorithm
Back Forward

In Pseudocode

while (You are not at the top of the hill) { Find an uphill direction and face that way Walk as far uphill as you can in the direction you are facing }
Choosing an Uphill Direction
Back Forward

A Series of "Bad" Directions

images/spiral.gif
Choosing an Uphill Direction (cont.)
Back Forward

A Really Good Direction

images/steepest.gif
Choosing an Uphill Direction (cont.)
Back Forward

Greed is Not Always Good

images/ridge.gif
A Visualization Technique
Back Forward

Generating Level Sets

images/levelset1.gif
A Visualization Technique (cont.)
Back Forward

The Level Sets for this Example

images/levelset2.gif
A Visualization Technique (cont.)
Back Forward

Level Sets in General

images/levelset3.gif
The Cyclic Coordinates Method
Back Forward

An Illustration

images/levelset4.gif
The Cyclic Coordinates Method (cont.)
Back Forward

In Pseudocode

while (You are not at the top of the hill) { Walk as far uphill as you can in the north/south direction Walk as far uphill as you can in the east/west direction }
The Cyclic Coordinates Method (cont.)
Back Forward

For Minimization (NOT Maximization)

javaexamples/optimization/CyclicCoordinates.java
 
An Abstract Objective Function
Back Forward

One Approach

javaexamples/optimization/Objective.java
 
An Example
Back Forward

Triangulation on the Plane

images/triangulation-example.gif
An Example (cont.)
Back Forward

An Objective Function for Triangulation on the Plane

javaexamples/optimization/TriangulationObjective.java
 
There's Always More to Learn
Back -