Constrained Global Optimization by Constraint Partitioning and Simulated Annealing*

Abstract In this paper, we present constraint-partitioned sim-ulated annealing (CPSA), an algorithm that extends our previous constrained simulated annealing (CSA)for constrained optimization. The algorithm is based on the theory of extended saddle points (ESPs). Bydecomposing the ESP condition into multiple necessary conditions, CPSA partitions a problem by itsconstraints into subproblems, solves each independently using CSA, and resolves those violated globalconstraints across the subproblems. Because each subproblem is exponentially simpler and the numberof global constraints is very small, the complexity of solving the original problem is significantly reduced.We state without proof the asymptotic convergence of CPSA with probability one to a constrained globalminimum in discrete space. Last, we evaluate CPSA on some continuous constrained benchmarks. 1 Problem Definition A general mixed-integer nonlinear programming prob-lem (MINLP) is formulated as follows: (Pm) : minz f (z) (1) subject to h(z) = 0 and g(z) < = 0, where z = (x, y) 2 Z; x 2 Rv and y 2 Dw are,respectively, bounded continuous and discrete variables; f (z) is a lower-bounded objective function; g(z) = (g1(z),..., gr(z))T is a vector of r inequalityconstraint functions, and h(z) = (h1(z),..., hm(z))