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
andThe 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
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 of9
to11
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
1 POD Error
The following errors were encountered while parsing the POD:
- Around line 298:
You forgot a '=back' before '=head1'