coordinate_search, an Octave code which seeks the minimizer of a scalar function of several variables, by Jeff Borggaard.
The algorithm, which goes back to Fermi and Metropolis, is easy to describe. As originally designed, the algorithm begins with a central point, as well as 2*M "test" points, where M is the number of spatial dimensions. The I-th pair of test points differs from the central point only in the I-th coordinate. One test point increases, and one decreases, this coordinate by a fixed amount H.
The function value of all 2*M+1 points is computed; if the lowest value occurs at the center point, then H is decreased. If the lowest value occurs at a test point, then that test point becomes the new center point.
On the next step, using the current center point and size H, a new set of 2*M test points is computed, and the process is repeated.
Under certain simple conditions, the process will converge to a local minimizer of the function.
x_opt = coordinate_search ( x_center, f, flag )where
Very simple functions can be input as a quoted string. Thus, one could specify the f argument as '(x(1)-2*x(2)+7)^2'; However, for more complicated functions it makes sense to prepare an M-file that defines the function. For this same example, a suitable M-file would be:
function f = example ( x )
f = ( x(1) - 2 * x(2) + 7 )^2;
If this information was stored in an M-file called example.m, then one might invoke the optimization program with a command like
x_opt = coordinate_search ( x_init, @example, 0 )
The computer code and data files described and made available on this web page are distributed under the MIT license
coordinate_search is available in a MATLAB version and an Octave version.
asa047, an Octave code which minimizes a scalar function of several variables using the Nelder-Mead algorithm.
compass_search, is an Octave code which seeks the minimizer of a scalar function of several variables using compass search, a direct search algorithm that does not use derivatives.
nelder_mead, an Octave code which minimizes a scalar function of several variables using the Nelder-Mead algorithm.
praxis, a MATLAB library which implements the principal axis method of Richard Brent for minimization of a function without the use of derivatives.
test_opt, an Octave code which defines test problems requiring the minimization of a scalar function of several variables.
toms178, an Octave code which optimizes a scalar functional of multiple variables using the Hooke-Jeeves method.
Jeff Borggaard,
Mathematics Department,
Virginia Tech.