NAME

Simplex - multidimensional optimiser

SYNOPSIS

  use Simplex;

DESCRIPTION

This performs a multidimensional simplex. This version is different in calling parameters to an earlier one, hence the "2" in the name. It now does not encourage the objective function to maintain state. More on this below. It needs

• reference to a function

• starting point

• maximum number of steps

• maximumn number of starts

• tolerance for recognising convergence

It can also use

• lower bound

• upper bound

• output file for recording progress

• amount of spread/scatter on initial simplex

PARAMETERS

Parameters are passed by a reference to a single hash like this

    my %simplex_arg;
    $simplex_arg {max_iter} = 1000;

    my %result = simplex (\%simplex_arg);

In detail:

Obligatory Parameters

• function

    %simplex_arg {func} = \&myfunc;

  This is a reference to a function to be minimised.

     sub myfunc () {
         my $a = shift;
         my $b = shift;
         return ($a * $a + ($b - 2) * ($b - 2);
     }
     ...
         %simplex_arg{func} = \&myfunc;

• Initial guess

      my @initial_guess = (1, 3, 5, 4);
      %simplex_arg {ini_pt} = \@initial_guess

  This must be a reference to an array. The number of dimensions should be correct for the function being optimised.

• Maximum iterations

  This is the maximum number of iterations per restart. The optimisation may restart many times.

      %simplex_arg {max_iter} = 1000;

  This is single integer;

• Maximum restarts

  This is the maximum number of times the simplex may be started. It is not really the number of restarts. If you set it to 1, you will get an initial minimisation only and no restarts.

• Tolerance

  Convergence criteria are always fun. Currently, we stop when

  • The difference between best and worst corners of the simplex is less than f_tol and

  • The difference between the worst value and previous worst value is less than f_tol.

  To set this

      %simplex_args {f_tol} = 10e-5;

Optional Parameters

• Fixed parameter array

  If the hash of simplex arguements contains a member called fix_param, it will be taken as a reference to an array of fixed parameters. These are things that will not change from step to step of minimising. The calling mechanism is explained below.

• Lower bounds

  You can specify lower bounds for the search. If the simplex tries to go below this in any dimension, it will reject the point.

      my @lower = (-2, -3, -4, -5);
      %simplex_arg {lower} = \@lower;

  This must be a reference to an array. The dimensions must agree with those of @ini_pt.

• Upper bounds.

  This has corresponding behaviour to the lower bounds array.

      my @upper = (10, 20, 10, 3000);
      %simplex_arg {upper} = \@upper;

• Output file

  This is not essential. If you want to record the progress, then set this like

      %simplex_arg {o_file} = 'splx_out';

  This example would end up creating two files

  splx_out_hi.out

  splx_out_low.out

  This first lists the cycle number, function value and test point for the worst corner of the simplex. The second gives the same information for the best point on the simplex

  When reading this, the worst (highest) point should change from step to step. The best point will only change every so often.

• Initial Scatter

  The simplex is initialised by taking your guess and spreading corners of the simplex around it, perfectly evenly. In two dimensions, This would correspond to surrounding your initial guess by a triangle.

  This parameter controls the width of the spread.

      %simplex_args{scatter} = 0.2;

  Would result in a spread of 20 % of the size in each dimension, going 10 % up and 10 % down. If your initial guess is 10, then the simplex would span a range of 9 to 11 in this dimension. If you have a two dimensional problem, the initial values would be 9, 10 and 11. If you have a four dimensional problem, the values would be 9, 9.5, 1, 10.5, and 11.

  If you do not specify a value, some default like 0.2 will be used.

RETURN

The routine returns a reference to a hash with three elements

• success / failure

• array containing best point

• value at best point

Access them like this:

    my $result = simplex (\%simplex_arg);
    if ($$result {success} == $SPLX_SUCCESS) {
        print "Simplex happy \n"; }

    my $success = $$result{success};
    my @best = @{${$s_arg{result}}{best}};
    my $best_value = $$result {value};
    print "best value of $best_value at \n@best\n";

The element, $$result{success} can have one of three values which are exported to the caller:

$SPLX_SUCCESS

No problems.

$SPLX_TOO_MANY

The routine did not converge within the maximum number of iterations.

$SPLX_BROKEN

A programming bug.

NOTES and OPERATION

• The code is taken from Numerical recipes, but much changed.

• On each restart, the simplex is centred at the best value previously found.

• If the simplex hits a plateau, nothing terrible should happen. If the best and worst points are on the plateau, it will just return, which is a bummer. If some of the points are on a plateau, the whole simplex will just contract about the best point.

• Do not look for a parameter with the number of dimensions. Since perl arrays know how big they are, there is no point in adding another parameter. We get the dimensionality by looking at the size of the @ini_pt array.

EXAMPLE

We have a small function like this:

    sub toyfunc ( \@)
    {
        my ($a, $b) = @_;
        return (($a + 8) * ($a + 8) + ($a - 40) * ($a - 40) + 30 * $a * sin($a)
                + $b * $b * $b * $b_);

    }

Then try my $fref = \&toyfunc; my @guess = (1, 14); my @lower = (-10, -3000); my @upper = (20, 230); my $max_iter = 1000; my $max_restart = 5; my $f_tol = 10e-7;

    my %result;
    my %s_arg = (
        func        => \&toyfunc,
        ini_pt      => \@guess,
        lower       => \@lower,
        upper       => \@upper,
        max_iter    => $max_iter,
        max_restart => $max_restart,
        o_file      => 'splx_out',
        scatter     => 0.20,
        f_tol       => $f_tol,
        result      => \%result
                 
    );
    
    my $result = simplex (\%s_arg);

    if ($result {success} == $SPLX_SUCCESS) {
        print "Simplex happy \n";
    } elsif ($result {success} == $SPLX_TOO_MANY) {
        print "Simplex too many\n"; }
    for (my $i = 0; $i < $s_arg{n_dim}; $i++) {
        printf '%4g ', "${${$s_arg{result}}{best}}[$i]"; }
    print "\n";

ANOTHER EXAMPLE

Imagine we have some parameters which should be passed to the cost function, but do not vary. In the caller, we have

    my %s_arg
    my %fix_param;
    $fix_param { num_days } = 5;
    $fix_param { colour } = 'red';

    my %s_arg = (
        func        => \&align_cost,
        ini_pt      => \@guess,
        lower       => \@lower,
        upper       => \@upper,
        max_iter    => $max_iter,
        max_restart => $max_restart,
        o_file      => 'splx_out',
        scatter     => 0.20,
        f_tol       => $f_tol,
        result      => \%result,
        fix_param   => \%fix_param
    );
   [... lots of code ..]
    use lib 'path_to_Simplex';
    use Simplex2;
    my $ret = simplex2 (\%s_arg);

In the cost function, we have something like

   sub align_cost (\@ \%)
    {
        my $var_param = shift;
        my $fix_param = shift;

        my $num_days = $$fix_param { num_days };
        my $colour   = $$fix_param { colour };
        
        my $first_variable = $$var_param[0];
            [.... calculate and return a cost ..]

BUGS

cpanm Wurst

perl -MCPAN -e shell
install Wurst