Nelder-Mead and Multi Directional Search methods

This repository contains implementation of algorithms, examples and a testing suite for Bachelor of Science thesis in Mathematics, Use of Nelder-Mead and Multi Directional Search methods in perturbed function optimization.

Abstract: This thesis compares two of direct search methods based on simplices: the Nelder-Mead algorithm and the Multidirectional Search method. Theory part presents known convergence results for continuous functions and proceeds to discuss known results for optimization of perturbed functions using forementioned methods. Further part compares performance of algorithms using test set proposed by MDS' author and extends the test cases by additionally covering a variant of Nelder-Mead algorithm.

Repository contents

Direct search optimization implementation

MATLAB code implements:

1. Nelder-Mead method [1] with optional oriented restarts as defined by Kelley [3],
2. Multidirectional Search Method by Virginia Torczon [2].

Usage:

init
[x, fval, exitflag, output] = fminsearch_nm(fun, x0, options);    % Uses NM method
[x, fval, exitflag, output] = fminsearch_mds(fun, x0, options);    % Uses MDS method

Interfaces of fminsearch_nm and fminsearch_mds are compatible with fminsearch implementation. Standard options from optimset are supported. You can set more options by calling xoptimset instead. Type

help xoptimset

for list of extended options.

To use optimizers in external projects, add top-level folder and includes folder to search path.

Examples

Several examples were used to generate images found in the thesis. To run example, enter project home directory and execute code snippets. You can run init only once and then call examples of choice.

Initial simplex generation

init
run('examples/initial_simplices/regular_simplex.m');
run('examples/initial_simplices/right_simplex.m');
run('examples/initial_simplices/pfeffer_method.m');

Perturbed quadratics

init
run('examples/perturbed_quadratics/perturbed_quadratics.m');

Rosenbrock Valley

init
run('examples/rosenbrock_valley/nm.m');
run('examples/rosenbrock_valley/mds.m');

Nelder favorite examples

init
run('examples/nelders_favorite/nelders_favorite_1.m');
run('examples/nelders_favorite/nelders_favorite_2.m');
run('examples/nelders_favorite/nelders_favorite_3.m');

McKinnon examples (original and with Kelley's restarts)

init
run('examples/mckinnon/mckinnon_2.m');
run('examples/mckinnon/mckinnon_2_stats.m');
run('examples/mckinnon/mckinnon_with_restarts_2.m');
run('examples/mckinnon/mckinnon_with_restarts_2_stats.m');

Woods examples of premature Nelder-Mead termination

init
run('examples/nm_pretermination/nm_pretermination_1.m');
run('examples/nm_pretermination/nm_pretermination_2.m');

Lattice of points generated by MDS iterations

init
run('examples/mds_grid/mds_grid.m');

Test suite

Folder tests/ contains a suite of tests used in the second part of the thesis.

Running tests

Tests run optimization on functions defined in tests/functions/ and their noisy counterparts. Since all functions are tested in multiple dimensions using different variants of optimizers, it may take a few hours for computation to finish. Iteration history of each run will be saved as a file in tests/out/data/

init
run('tests/test_all.m');    % Tests regular functions
run('tests/test_all_noisy.m');    % Tests perturbed functions

Visualizing results

Outputs of tests can be plotted on multiple graphs defined in tests/ folder. Run

init
run('tests/<visualization_name>.m');

to run selected visualization. See list of files in tests/ for possible options.

References

[1] J. Nelder, R. Mead, A simplex method for function minimization. The computer journal. 1965 Jan 1;7(4):308-13.

[2] V. J. Torczon. Multidirectional search: a direct search algorithm for parallel machines (Doctoral dissertation).

[3] C. T. Kelley, Detection and remediation of stagnation in the Nelder-Mead algorithm using a sufficient decrease condition., Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999.