Abstract
In this paper, we present constrained simulated annealing (CSA), a global minimization algorithm that converges to constrained global minima with probability one, for solving nonlinear discrete non-convex constrained minimization problems. The algorithm is based on the necessary and sufficient condition for constrained local minima in the theory of discrete Lagrange multipliers we developed earlier. The condition states that the set of discrete saddle points is the same as the set of constrained local minima when all constraint functions are non-negative. To find the discrete saddle point with the minimum objective value, we model the search by a finite inhomogeneous Markov chain that carries out (in an annealing fashion) both probabilistic descents of the discrete Lagrangian function in the original-variable space and probabilistic ascents in the Lagrange-multiplier space. We then prove the asymptotic convergence of the algorithm to constrained global minima with probability one. Finally, we extend CSA to solve nonlinear constrained problems with continuous variables and those with mixed (both discrete and continuous) variables. Our results on a set of nonlinear benchmarks are much better than those reported by others. By achieving asymptotic convergence, CSA is one of the major developments in nonlinear constrained global optimization today.
Research supported by National Science Foundation Grant NSF MIP 96-32316.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aarts, E., Korst, J.: Simulated Annealing and Boltzmann Machines. J. Wiley and Sons, Chichester (1989)
Anily, S., Federgruen, A.: Simulated annealing methods with general acceptance probabilities. Journal of Appl. Prob. 24, 657–667 (1987)
Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press, London (1982)
Corana, A., Marchesi, M., Martini, C., Ridella, S.: Minimizing multimodal functions of continuous variables with the simulated annealing algorithm. ACM Trans. on Mathematical Software 13(3), 262–280 (1987)
Koziel, S., Michalewicz, Z.: Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization. Evolutionary Computation 7(1), 19–44 (1999)
Luenberger, D.G.: Linear and Nonlinear Programming. Addison-Wesley Publishing Company, Reading (1984)
Michalewicz, Z., Schoenauer, M.: Evolutionary algorithms for constrained parameter optimization problems. Evolutionary Computation 4(1), 1–32 (1996)
Shang, Y., Wah, B.W.: A discrete Lagrangian based global search method for solving satisfiability problems. J. Global Optimization 12(1), 61–99 (1998)
Spellucci, P.: An SQP method for general nonlinear programs using only equality constrained subproblems. Mathematical Programming 82, 413–448 (1998)
Trouve, A.: Cycle decomposition and simulated annealing. SIAM Journal on Control and Optimization 34(3), 966–986 (1996)
Wah, B.W., Wu, Z.: The theory of discrete lagrange multipliers for nonlinear discrete optimization. Principles and Practice of Constraint Programming (October 1999) (accepted to appear)
Wu, Z.: Discrete Lagrangian Methods for Solving Nonlinear Discrete Constrained Optimization Problems. M.Sc. Thesis, Dept. of Computer Science, Univ. of Illinois, Urbana, IL (May 1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wah, B.W., Wang, T. (1999). Simulated Annealing with Asymptotic Convergence for Nonlinear Constrained Global Optimization. In: Jaffar, J. (eds) Principles and Practice of Constraint Programming – CP’99. CP 1999. Lecture Notes in Computer Science, vol 1713. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-48085-3_33
Download citation
DOI: https://doi.org/10.1007/978-3-540-48085-3_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66626-4
Online ISBN: 978-3-540-48085-3
eBook Packages: Springer Book Archive