Unconstrained Multidimensional Optimization

Unconstrained Multidimensional Optimization
An Introduction with Examples in Java

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Motivation

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
- Stop when you can't find an uphill direction to walk in

Motivation (cont.)

An Illustration of the Ascent Algorithm

A Generic Ascent Algorithm

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

A Series of "Bad" Directions

Choosing an Uphill Direction (cont.)

A Really Good Direction

Choosing an Uphill Direction (cont.)

Greed is Not Always Good

A Visualization Technique

Generating Level Sets

A Visualization Technique (cont.)

The Level Sets for this Example

A Visualization Technique (cont.)

Level Sets in General

The Cyclic Coordinates Method

An Illustration

The Cyclic Coordinates Method (cont.)

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.)

For Minimization (NOT Maximization)

javaexamples/optimization/CyclicCoordinates.java

An Abstract Objective Function

One Approach

javaexamples/optimization/Objective.java

An Example

Triangulation on the Plane

An Example (cont.)

An Objective Function for Triangulation on the Plane

javaexamples/optimization/TriangulationObjective.java

There's Always More to Learn