Downhill Simplex Algorithm – C Coursework

First Iteration of Downhill Simplex
First Iteration of Downhill Simplex

In this coursework from semester two of year two the task is to numerically find the minimum of a multidimensional equation. As an example, the root of Rosenbrock’s parabolic valley is found using the Downhill simplex method developed by Nelder and Mead.

Using the downhill simplex header file the code can quickly be used to find the minimum of any two dimensional equation for which a function is defined, more detailed instructions can be found in the report.

This report describes and presents answer to my C Computing coursework, the aim of which was to create a program in C or C++ to find the minimum point of a two dimensional function using the Downhill Simplex, or Nelder-Mead approach. C++ was used as it allowed functions and operators to be overloaded and the creation of classes which aided in the program being able to be used for an arbitrary function. Please visit https://github.bath.ac.uk/pages/ew639/ C-Coursework/ which contains animations, source code files and the provided exercise. Code extracts in the report have had unnecessary comments removed.

Abstract from Report
Written by Edward Webster

In verbose mode, the program outputs the minimum found during each step of the iterative process to a file. Using MATLAB an animation was created which shows this root being found. This animation is embedded in the report PDF but incase Adobe Reader isn’t being used the video can be viewed here.

Animation showing the root of Rosenbrock’s Parabolic Valley being found.

Also embedded in Report PDF

Nelder-Mead method

The Nelder-Mead method (also downhill simplex method, amoeba method, or polytope method) is a commonly applied numerical method used to find the minimum or maximum of an objective function in a multidimensional space. It is a direct search method (based on function comparison) and is often applied to nonlinear optimization problems for which derivatives may not be known.

Leave a comment

Your email address will not be published. Required fields are marked *