RE: Simulated annealing with nonlinear constraints

[Ted Harding]

On 09-Oct-99 address@hidden wrote:
> Someone asked if you could do simulated annealing with nonlinear
> inequality constraints.  The answer is yes and no.  With simulated
> annealing you essentially sample randomly from a distribution on the 
> feasible set.  If the feasible set is not of the form (low <= x
> <= high), where low, x, and high are vectors, then you won't be able to
> easily figure out the distribution.
> 
> However the beauty of simulated annealing is that you don't have to
> have a smooth objective function.  So you can just add the nonlinear
> constraint to the objective in the form of a large exterior penalty. 
> By this I mean that you add (if you are minimizing, subtract if
> maximizing) a large positive number to the objective for points which
> violate your constraint.
> This does waste some computer time because you will occasionally
> evaluate the objective function for infeasible points (for those
> unfamiliar with optimization the measure of efficiency of a given
> algorithm is how few times the objective has to be evaluated before a
> solution is obtained) but it's the best you can do.

As a further comment on the above: Simulated annealing is often
implemented as an evolutionary variant of Markov Chain Monte Carlo
(MCMC) in which the distribution being sampled from contains a
parameter ("temperature") which is slowly forced towards zero so that
the distribution being sampled from ultimately has all its probability
at the maximum of the objective function.

MCMC is a two-stage process. With 'x' the current position, a candidate
'y' for the next position is sampled from a "proposal distribution"
'q(x,y)'. Then the candidate 'y' is accepted at random with probability

  min[ 1, (q(y,x)*P(y))/(q(x,y)*P(x)) ]

(with the obvious interpretation if the denominator in this expression
is zero), where P(x) is the distribution you are trying to sample from.
If 'y is accepted, the next position is 'y; otherwise it remains at 'x'.

This process x -> ... is a Markov Chain with equilibrium
distribution P(x).

An alternative, therefore, to implementing the constraint by returning
a large "penalty" in the objective function outside the constraint
boundaries (as Heber suggests) is to incorporate the constraints
into the proposal distribution q(x,y) so that q(x,y) = 0 for all
'y' outside the constraint boundaries. In this way, such a 'y' will
never be a candidate and so will never appear as a sampled value from
the distribution 'P'.

Whether it is easier to do it this way depends, I suppose, on the
constraints. Since MCMC is pretty robust where choice of 'q(x,y)'
is concerned (though there is a lot of scope for studying good
choices of 'q(x,y)' in particular problems), maybe a simple and
effective suggestion might be to have 'q(x,y)', as a function of
'y', uniform over the admissible region and zero outside.

I hope this helps.

Best wishes,
Ted.

--------------------------------------------------------------------
E-Mail: (Ted Harding) <address@hidden>
Date: 09-Oct-99                                       Time: 11:00:14
------------------------------ XFMail ------------------------------



---------------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.  To ensure
that development continues, see www.che.wisc.edu/octave/giftform.html
Instructions for unsubscribing: www.che.wisc.edu/octave/archive.html
---------------------------------------------------------------------