Simulated annealing with asymptotic convergence for nonlinear constrained optimization |
| |
Authors: | Benjamin W Wah Yixin Chen Tao Wang |
| |
Institution: | (1) Department of Electrical and Computer Engineering and the Coordinated Science Laboratory, University of Illinois, Urbana-Champaign, Urbana, IL 61801, USA;(2) Department of Computer Science, Washington University, St. Louis, MO 63130, USA;(3) Synopsys Inc., 700 East Middlefield Road, Mountain View, CA 94043, USA |
| |
Abstract: | In this paper, we present constrained simulated annealing (CSA), an algorithm that extends conventional simulated annealing to look for constrained local minima of nonlinear constrained
optimization problems. The algorithm is based on the theory of extended saddle points (ESPs) that shows the one-to-one correspondence
between a constrained local minimum and an ESP of the corresponding penalty function. CSA finds ESPs by systematically controlling
probabilistic descents in the problem-variable subspace of the penalty function and probabilistic ascents in the penalty subspace.
Based on the decomposition of the necessary and sufficient ESP condition into multiple necessary conditions, we present constraint-partitioned simulated annealing (CPSA) that exploits the locality of constraints in nonlinear optimization problems. CPSA leads to much lower complexity
as compared to that of CSA by partitioning the constraints of a problem into significantly simpler subproblems, solving each
independently, and resolving those violated global constraints across the subproblems. We prove that both CSA and CPSA asymptotically
converge to a constrained global minimum with probability one in discrete optimization problems. The result extends conventional
simulated annealing (SA), which guarantees asymptotic convergence in discrete unconstrained optimization, to that in discrete
constrained optimization. Moreover, it establishes the condition under which optimal solutions can be found in constraint-partitioned
nonlinear optimization problems. Finally, we evaluate CSA and CPSA by applying them to solve some continuous constrained optimization
benchmarks and compare their performance to that of other penalty methods. |
| |
Keywords: | Asymptotic convergence Constrained local minimum Constraint partitioning Simulated annealing Dynamic penalty methods Extended saddle points Nonlinear constrained optimization |
本文献已被 SpringerLink 等数据库收录! |
|