nmplot

Description

This class provides several direct search optimization algorithms based on the simplex method.

The goal of this class is to provide a neldermead component with plotting features. It enables to make fast plots of the algorithm progress through the iterations.

It is a specialized neldermead class, with a specific output command. This output function allows to store the history of several datas through the iterations of the algorithm. These datas are :

• the history of the coordinates of the simplex ,

• the history of the function value (averaged on the vertices),

• the history of the minimum function value in the simplex,

• the history of the size of the simplex (as computed with the sigma+ method).

These data are stored into several data files during the optimization process. Several methods allows to plot the data stored into these data files.

Design

The nmplot component is built on top of the neldermead component. The -outputcommand option (of the neldermead class) is not available since the nmplot class uses its own output function. Additionnal options -simplexfn, -fbarfn, -foptfn and -sigmafn are provided, which allows to configure the file names where the data is stored.

The nmplot class can be considered as a sample test case of the -outputcommand option of the neldermead class. It gives an example of the situation where the user wants to get specialized outputs out of the neldermead class.

Functions

The following functions are available.

newobj = nmplot_new ()

Creates a new nmplot object.

newobj

The new object.

this = nmplot_destroy (this)

Destroy the given object.

this

The current object.

this = nmplot_configure (this,key,value)

Configure the current object with the given value for the given key.

this

The current object.

key

the key to configure. The following keys are available.

-verbose

set to 1 to enable verbose logging. (default is 0)

-verbosetermination

set to 1 to enable verbose termination logging. (default is 0)

-x0

the initial guess, as a n x 1 column vector, where n is the number of variables.

-maxfunevals

the maximum number of function evalutations (default is 100). If this criteria is triggered, the status of the optimization is set to "maxfuneval".

-maxiter

the maximum number of iterations (default is 100). If this criteria is triggered, the status of the optimization is set to "maxiter".

-tolfunabsolute

the absolute tolerance for the function value (default is 0.0).

-tolfunrelative

the relative tolerance for the function value (default is %eps).

-tolfunmethod

the method used for the tolerance on function value in the termination criteria.

The following values are available : "absolute+relative", "relative", "absolute", "disabled" (default is "disabled"). If this criteria is triggered, the status of the optimization is set to "tolf".

-tolxabsolute

the absolute tolerance on x (default is 0.0).

-tolxrelative

the relative tolerance on x (default is %eps).

-tolxmethod

the method used for the tolerance on x in the termination criteria.

The following values are available : "relative", "absolute", "disabled" (default is "relative"). If this criteria is triggered, the status of the optimization is set to "tolx".

-function

the objective function, which computes the value of the cost and the non linear constraints, if any.

See below for the details of the communication between the optimization system and the cost function.

-costfargument

an additionnal argument, passed to the cost function.

-outputcommand

a command which is called back for output.

See below for the details of the communication between the optimization system and the output command function.

-outputcommandarg

an additionnal argument, passed to the output command.

-numberofvariables

the number of variables to optimize (default is 0).

-storehistory

set to 1 to enable the history storing (default is 0).

-boundsmin

the minimum bounds for the parameters, as an array of values (default is empty, i.e. there are no bounds).

-boundsmax

the maximum bounds for the parameters, as an array of values (default is empty, i.e. there are no bounds).

-nbineqconst

the number of inequality constraints (default is 0)

-method

the name of the algorithm to use. The following methods are available :

"fixed"

the Spendley et al. fixed simplex shape algorithm. This algorithm is for unconstrained problems (i.e. bounds and non linear constraints are not taken into account)

"variable"

the Nelder-Mead variable simplex shape algorithm. This algorithm is for unconstrained problems (i.e. bounds and non linear constraints are not taken into account)

"box"

the Box complex algorithm. This algorithm takes into account bounds and nonlinear inequality constraints.

-simplex0method

the method to use to compute the initial simplex. The first vertex in the simplex is always the initial guess associated with the -x0 option. The following methods are available :

"given"

the coordinates associated with the -coords0 option are used to compute the initial simplex, with arbitrary number of vertices.

This allow the user to setup the initial simplex by a specific method which is not provided by the current component (for example with a simplex computed from a design of experiments). This allows also to configure the initial simplex so that a specific behaviour of the algorithm an be reproduced (for example the Mac Kinnon test case).

The given matrix is expected to have n rows and k columns, where n is the dimension of the problem and k is the number of vertices.

"axes"

the simplex is computed from the coordinate axes and the length associated with the -simplex0length option.

"spendley"

the simplex is computed so that it is regular with the length associated with the -simplex0length option (i.e. all the edges have the same length).

"pfeffer"

the simplex is computed from an heuristic, in the neighborhood of the initial guess. This initial simplex depends on the -simplex0deltausual and -simplex0deltazero.

"randbounds"

the simplex is computed from the bounds and a random number. This option is available only if bounds are available : if bounds are not available, an error is generated. This method is usually associated with Box's algorithm. The number of vertices in the simplex is taken from the -boxnbpoints option.

-coords0

the coordinates of the vertices of the initial simplex. If the -simplex0method option is set to "given", these coordinates are used to compute the initial simplex. This matrix is expected to have shape nbve x n where nbve is the number of vertices and n is the number of variables.

-simplex0length

the length to use when the initial simplex is computed with the "axes" or "spendley" methods. If the initial simplex is computed from "spendley" method, the length is expected to be a scalar value. If the initial simplex is computed from "axes" method, it may be either a scalar value or a vector of values, with rank n, where n is the number of variables.

-simplex0deltausual

the relative delta for non-zero parameters in "pfeffer" method. The default value is 0.05.

-simplex0deltazero

the absolute delta for non-zero parameters in "pfeffer" method. The default value is 0.0075.

-rho

the reflection coefficient. This parameter is used when the -method option is set to "fixed" or "variable". The default value is 1.0.

-chi

the expansion coefficient. This parameter is used when the -method option is set to "variable". The default value is 2.0.

-gamma

the contraction coefficient. This parameter is used when the -method option is set to "variable". The default value is 0.5.

-sigma

the shrinkage coefficient. This parameter is used when the -method option is set to "fixed" or "variable". The default value is 0.5.

-tolfstdeviationmethod

set to "enabled" to enable the termination criteria based on the standard deviation of the function values in the simplex. The default value is "disabled". If this criteria is triggered, the status of the optimization is set to "tolfstdev".

This criteria is suggested by Nelder and Mead.

-tolfstdeviation

the absolute tolerance on standard deviation. The default value is 0.0.

-tolsimplexizemethod

set to "disabled" to disable the tolerance on the simplex size. The default value is "enabled". If this criteria is triggered, the status of the optimization is set to "tolsize".

When this criteria is enabled, the values of the options -tolsimplexizeabsolute and -tolsimplexizerelative are used in the termination criteria. The method to compute the size is the "sigmaplus" method.

-tolsimplexizeabsolute

the absolute tolerance on the simplex size. The default value is 0.0.

-tolsimplexizerelative

the relative tolerance on the simplex size. The default value is %eps.

-tolssizedeltafvmethod

set to "enabled" to enable the termination criteria based on the size of the simplex and the difference of function value in the simplex. The default value is "disabled". If this criteria is triggered, the status of the optimization is set to "tolsizedeltafv".

This termination criteria uses the values of the options -tolsimplexizeabsolute and -toldeltafv. This criteria is identical to Matlab's fminsearch.

-toldeltafv

the absolute tolerance on the difference between the highest and the lowest function values.

-kelleystagnationflag

set to 1 to enable the termination criteria using Kelley's stagnation detection, based on sufficient decrease condition. The default value is 0. If this criteria is triggered, the status of the optimization is set to "kelleystagnation".

-kelleynormalizationflag

set to 0 to disable the normalization of the alpha coefficient in Kelley's stagnation detection, i.e. use the value of the option -kelleystagnationalpha0 as is. Default value is 1, i.e. the simplex gradient of the initial simplex is taken into account in the stagnation detection.

-kelleystagnationalpha0

the parameter used in Kelley's stagnation detection. The default value is 1.e-4.

-restartflag

set to 1 to enable the automatic restart of the algorithm. Default value is 0.

-restartdetection

the method to detect if the automatic restart must be performed. The following methods are available :

"oneill"

the factorial local optimality test by O'Neill is used. If the test finds a local point which is better than the computed optimum, a restart is performed.

"kelley"

the sufficient decrease condition by O'Neill is used. If the test finds that the status of the optimization is "kelleystagnation", a restart is performed. This status may be generated if the -kelleystagnationflag option is set to 1.

The default method is "oneill".

-restartmax

the maximum number of restarts, when automatic restart is enabled via the -restartflag option. Default value is 3.

-restarteps

the absolute epsilon value used to check for optimality in the factorial O'Neill restart detection. The default value is %eps.

-restartstep

the absolute step length used to check for optimality in the factorial O'Neill restart detection. The default value is 1.0.

-restartsimplexmethod

the method to compute the initial simplex after a restart. The following methods are available.

"given"

the coordinates associated with the -coords0 option are used to compute the initial simplex, with arbitrary number of vertices.

This allow the user to setup the initial simplex by a specific method which is not provided by the current component (for example with a simplex computed from a design of experiments). This allows also to configure the initial simplex so that a specific behaviour of the algorithm an be reproduced (for example the Mac Kinnon test case).

The given matrix is expected to have n rows and k columns, where n is the dimension of the problem and k is the number of vertices.

"axes"

the simplex is computed from the coordinate axes and the length associated with the -simplex0length option.

"spendley"

the simplex is computed so that it is regular with the length associated with the -simplex0length option (i.e. all the edges have the same length).

"pfeffer"

the simplex is computed from an heuristic, in the neighborhood of the initial guess. This initial simplex depends on the -simplex0deltausual and -simplex0deltazero.

"randbounds"

the simplex is computed from the bounds and a random number. This option is available only if bounds are available : if bounds are not available, an error is generated. This method is usually associated with Box's algorithm. The number of vertices in the simplex is taken from the -boxnbpoints option.

"oriented"

the simplex is computed so that it is oriented, as suggested by C.T. Kelley.

The default method is "oriented".

-boxnbpoints

the number of points in the initial simplex, when the -restartsimplexmethod option is set to "randbounds". The default value is so that the number of points is twice the number of variables of the problem.

-nbineqloops

the number of loops to perform in Box and Box-Guin algorithms to scale the trial point for function improvement or into the constraints. Default value is 10.

-ineqscaling

the scaling coefficient used to scale the trial point for function improvement or into the constraints. Default value is 0.5

-simplexfn

the name of the file containing the history of the simplex. Default value is the empty string.

-fbarfn

the name of the file containing the history of the function value, averaged on the vertices of the simplex. Default value is the empty string.

-foptfn

the name of the file containing the history of the minimum function value in the simplex. Default value is the empty string.

-sigmafn

the name of the file containing the history of the size of the simplex. Default value is the empty string.

value

the value.

value = nmplot_cget (this,key)

Get the value for the given key. If the key is unknown, generates an error.

this

The current object.

key

the name of the key to quiery. The list of available keys is the same as for the nmplot_configure function.

value = nmplot_get ( this , key )

Get the value for the given key. If the key is unknown, generates an error.

this

The current object.

key

the key to get.

The following keys are available :

-funevals

the number of function evaluations

-iterations

the number of iterations

-xopt

the x optimum, as a n x 1 column vector, where n is the number of variables.

-fopt

the optimum cost function value

-historyxopt

an array, with nbiter values, containing the history of x during the iterations.

This array is available after optimization if the history storing was enabled with the -storehistory option.

-historyfopt

an array, with nbiter values, containing the history of the function value during the iterations.

This array is available after optimization if the history storing was enabled with the -storehistory option.

-fx0

the function value for the initial guess

-status

a string containing the status of the optimization. See below for details about the optimization status.

-historysimplex

a matrix containing the history of the simplex during the iterations. This matrix has rank nbiter x nbve x n, where nbiter is the number of iterations, nbve is the number of vertices in the simplex and n is the number of variables.

-simplexopt

the optimum simplex. This is a simplex object, which is suitable for processing with the simplex interface.

-restartnb

the number of actual restarts performed.

Most fields are available only after an optimization has been performed with one call to the neldermead_search method.

this = nmplot_display ( this )

Display the current settings in the console.

this

The current object.

this = nmplot_search ( this )

Performs the optimization associated with the method associated with the -method option and find the optimum.

this

The current object.

If the -restartflag option is enabled, automatic restarts are performed, based on the -restartdetection option.

this = nmplot_restart ( this )

Restarts the optimization by updating the simplex and performing a new search.

this

The current object.

[ this , xdata , ydata , zdata ] = nmplot_contour ( this , xmin , xmax , ymin , ymax , nx , ny )

Plot the contours of the cost function. The cost function must be a function with two parameters.

this

The current object.

xmin , xmax , ymin , ymax

the bounds for the contour plot

nx , ny

the number of points in the directions x, y

xdata , ydata , zdata

vectors of data, as required by the contour function

nmplot_simplexhistory ( this , colorforeground , markforeground , markstyle )

Plots the simplex history on the current graphic window. The colorforeground , markforeground , markstyle options are provided to produce fast plots. Specific settings can still be applied with the usual graphic features.

this

The current object.

colorforeground

the color of the foreground for the simplices. Default value is 5.

markforeground

the foreground mark for the simplices. Default value is 3.

markstyle

the mark style for the simplices. Default value is 9.

nmplot_historyplot ( this , datafile , mytitle , myxlabel , myylabel )

Plots the history from the given data file on the current graphic window. The mytitle, myxlabel, myylabel options are provided as a way to produce plots faster. Specific settings can still be applied with the usual graphic features.

this

The current object.

datafile

the data file which contains the history. The file is expected to be formatted in a way similar to the files associated with the -fbarfn, -foptfn and -sigmafn files. The default value is the value of the -foptfn option.

mytitle

the title of the plot. Default value is the empty string.

myxlabel

the x label for the plot. Default value is the empty string.

myylabel

the y label for the plot. Default value is the empty string.

[ this , result ] = nmplot_function ( this , x , index )

Call the cost function and return the value.

this

The current object.

x

the point where the function is to be evaluated

index

optionnal, a flag to pass to the cost function (default = 1). See the section "The cost function" of the neldermead component for available values of index.

Example

In the following example, we use the fixed shape Spendley et al. simplex algorithm and find the minimum of a quadratic function. We begin by defining a quadratic function associated with 2 input variables. We then define an nmplot object and configure the object so that the "fixed" shape simplex algorithm is used with the regular initial simplex associated with the "spendley" key. Four files are configured, which will contain the history of the simplex, the history of fbar, fopt and sigma through the iterations. The search is performed by the nmplot_search function, which writes the 4 data files during the iterations. The nmplot_contour function is called in order to compute the arrays xdata, ydata and zdata which are required as input to the contour function. The nmplot_simplexhistory then uses the history of the simplex, as stored in the rosenbrock.fixed.history.simplex.txt data file, and plot the various simplices on the contour plot. The nmplot_historyplot is used with the files rosenbrock.fixed.history.fbar.txt, rosenbrock.fixed.history.fopt.txt and rosenbrock.fixed.history.sigma.txt, which produces 3 plots of the history of the optimization algorithm through the iterations.

mprintf("Defining quadratic function...\n");
function y = quadratic (x)
  y = x(1)^2 + x(2)^2 - x(1) * x(2);
endfunction

mprintf("Creating nmplot object...\n");
nm = nmplot_new ();
nm = nmplot_configure(nm,"-numberofvariables",2);
nm = nmplot_configure(nm,"-function",quadratic);
nm = nmplot_configure(nm,"-x0",[2.0 2.0]');
nm = nmplot_configure(nm,"-maxiter",100);
nm = nmplot_configure(nm,"-maxfunevals",300);
nm = nmplot_configure(nm,"-tolxrelative",1.e-8);
nm = nmplot_configure(nm,"-simplex0method","spendley");
nm = nmplot_configure(nm,"-method","fixed");
//
// Setup output files
//
nm = nmplot_configure(nm,"-simplexfn","rosenbrock.fixed.history.simplex.txt");
nm = nmplot_configure(nm,"-fbarfn","rosenbrock.fixed.history.fbar.txt");
nm = nmplot_configure(nm,"-foptfn","rosenbrock.fixed.history.fopt.txt");
nm = nmplot_configure(nm,"-sigmafn","rosenbrock.fixed.history.sigma.txt");
//
// Perform optimization
//
mprintf("Searching for minimum...\n");
nm = nmplot_search(nm);
nmplot_display(nm);
// Plot the contours of the cost function and the simplex history
mprintf("Plotting contour...\n");
[nm , xdata , ydata , zdata ] = nmplot_contour ( nm , xmin = -2.0 , xmax = 4.0 , ymin = -2.0 , ymax = 4.0 , nx = 100 , ny = 100 );
f = scf();
contour ( xdata , ydata , zdata , [0.1 1.0 2.0 5.0 10.0 15.0 20.0] )
nmplot_simplexhistory ( nm );
mprintf("Plotting history of fbar...\n");
f = scf();
nmplot_historyplot ( nm , "rosenbrock.fixed.history.fbar.txt" , ...
  mytitle = "Function Value Average" , myxlabel = "Iterations" );
mprintf("Plotting history of fopt...\n");
f = scf();
nmplot_historyplot ( nm , "rosenbrock.fixed.history.fopt.txt" , ...
  mytitle = "Minimum Function Value" , myxlabel = "Iterations" );
mprintf("Plotting history of sigma...\n");
f = scf();
nmplot_historyplot ( nm , "rosenbrock.fixed.history.sigma.txt" , ...
  mytitle = "Maximum Oriented length" , myxlabel = "Iterations" );
deletefile("rosenbrock.fixed.history.simplex.txt");
deletefile("rosenbrock.fixed.history.fbar.txt");
deletefile("rosenbrock.fixed.history.fopt.txt");
deletefile("rosenbrock.fixed.history.sigma.txt");
nm = nmplot_destroy(nm);

TODO

• add an example

Authors

Michael Baudin - INRIA - 2008-2009

Michael Baudin - Digiteo - 2009

See Also

• neldermead