Handling equality and inequality linear constraints in simulated annealing

Abstract

Simulated annealing (SA) has become an algorithm of choice when dealing with nonlinear global optimization problems, specially when the objective function is illbehaved or multimodal, and when derivative information is not available or difficult to evaluate. In general, most SA algorithms are devised for unconstrained optimization, though the use of lower and upper bounds to delimit the feasible region is a common practice. When additional constraints such as equality or inequality constraints are to be taken into account, the development of appropriate strategies to force the solution to satisfy those constraints is critical. In this sense, and for the sake of efficiency, the exploration of the model space to evaluate new and unknown areas within the feasibly region is a key issue that requires further investigation. This work presents a simple strategy for handling arbitrary linear constraints in SA or other ?random search? optimization technique. Both equality and inequality linear constraints are taken into account. In the case of inequality constraints, the optimization problem is reformulated as an unconstrained optimization one with dynamically adapted bounding constraints, which are easily implemented in SA algorithms. In the case of equality constraints, the optimization problem is also transformed into an unconstrained optimization problem with bounding constraints, but, instead, the original unknowns are expressed in terms of a new set of variables through the singular value decomposition (SVD) of the constraint matrix. The key of the proposed technique lies in the fact that, once an initial point within the feasible region is provided, new points are generated by addingrandom perturbations that lie in the null space at each annealing iteration. Hence, feasibility is maintained at every stage of the SA search process, avoiding unnecessary evaluations of the objective function due to constraints violations. Further, the proposedtechnique is general and easy to use, requiring neither modifications nor any parameter tuning to work in different problems, making it an interesting alternative to other constraint-handling techniques available in the literature. The strategy is illustrated using SA to minimize testing functions that contain both bounding and equalityor inequality linear constraints, including the classical loaded die problem.