## Introduction

The simulated annealing algorithm (proposed by Metropolis in 1953, message me for a reference) draws a reference to the structure of a metal, as it cools, settling into a crystalline structure. As the metal cools, it settles down to one of these lower energy minima. However, as the structure changes into lower minima orientations, the temperature of the metal can actually increase. By mimicking this natural process, a minima is actually achieved. The same analogy is pushed for numerical optimization.

## Simulated Annealing in Octave

In Octave, simulated annealing is implemented as *samin*. Typing “help samin” at the Octave terminal yields the results

help samin

samin: simulated annealing minimization of a function. See samin_example.m

usage: [x, obj, convergence, details] = samin(“f”, {args}, {control})

Arguments:

* “f”: function name (string)

* {args}: a cell array that holds all arguments of the function,

* {control}: a cell array with 11 elements

* LB – vector of lower bounds

* UB – vector of upper bounds

* nt – integer: # of iterations between temperature reductions

* ns – integer: # of iterations between bounds adjustments

* rt – (0 < rt <1): temperature reduction factor

* maxevals – integer: limit on function evaluations

* neps – integer: number of values final result is compared to

* functol – (> 0): the required tolerance level for function value

comparisons

* paramtol – (> 0): the required tolerance level for parameters

* verbosity – scalar: 0, 1, or 2.

* 0 = no screen output

* 1 = only final results to screen

* 2 = summary every temperature change

* minarg – integer: which of function args is minimization over?

Returns:

* x: the minimizer

* obj: the value of f() at x

* convergence:

0 if no convergence within maxevals function evaluations

1 if normal convergence to a point interior to the parameter space

2 if convergence to point very near bounds of parameter space

(suggest re-running with looser bounds)

* details: a px3 matrix. p is the number of times improvements were found.

The columns record information at the time an improvement was found

* first: cumulative number of function evaluations

* second: temperature

* third: function value

Example: see samin_example

/usr/libexec/octave/packages/optim-1.0.0/i386-redhat-linux-gnu-api-v32/samin.oct

Additional help for built-in functions and operators is

available in the on-line version of the manual. Use the command

`doc ‘ to search the manual index.

Help and information about Octave is also available on the WWW

at http://www.octave.org and via the help@octave.org

mailing list.

So let’s try this out for the same example f(x,y)=x^2+y^2. The minima is (x,y)=(0,0). This was encoded in the function *obj_fcn1.m* which looks like

`function out=obj_fcn1(x)`

x=x(:);

out=x'*x;

Let’s say that our initial estimate is x_0=[10,10]’. Recall, *samin* takes first the string argument “obj_fcn1”. The second argument is a cell. This cell, denoted by {,….,}, contains all the arguments of the function “obj_fcn1”. In this case, only x_0 is the input. The third argument is a cell argument with 11 interior arguments including lower and upper bounds, iterations between temperature and iteration changes, factor at which temperature is reduced, max function evals, number of values at which final estimate is compared, function tolerance, parameter tolerances, level of screen output, and argument (2nd *samin* input) which is being minimized. Here is my setup:

`x_0=[10,10]';`

LB=[-100,-100]';

UB=[1e10,1e10]';

nt=100;

ns=100;

rt=1e-3;

maxevals=1e8;

neps=100;

functol=1e-7;

paramtol=1e-7;

verbosity=2;

minarg=1;

[x_f,j_f]=samin("obj_fcn1",{x_0},{LB,UB,nt,ns,rt,maxevals,neps,functol,paramtol,verbosity,minarg});

The argument *minarg* is set to 1 since there is only one input to *obj_fcn1*.

Here is the final output from the run using the commands above:

`samin: intermediate results before next temperature change`

temperature 1.000000e-306

current best function value 0.000000

total evaluations so far 2280000

total moves since last temperature reduction 20000

downhill 4824

accepted uphill 4808

rejected uphill 10368

out of bounds trials 0

new minima this temperature 4

parameter search width

-0.000000 0.000000

-0.000000 0.000000

================================================

SAMIN results

==> Normal convergence <==

Convergence tolerances:

Function: 1.000000e-07

Parameters: 1.000000e-07

Objective function value at minimum: 0.000000

parameter search width

-0.000000 0.000000

-0.000000 0.000000

================================================

## Conclusion

Simulated annealing, as a stochastic search, is quite excellent with good convergence properties. In cases, where there is no knowledge of derivatives or where there are many local minima, SA is a good choice. SA has known global convergence properties and might be the answer for your problem.