Simulated annealing with nonlinear constraints

[heberf]

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.

_______________________________________________________________________________
Heber Farnsworth
Assistant Professor of Finance
John M. Olin School of Business
Washington University
Campus Box 1133                                 phone: (314) 935-4221   
One Brookings Drive                             FAX: (314) 935-6359
St. Louis, MO 63130-4899                




---------------------------------------------------------------------
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
---------------------------------------------------------------------