J89 (1121213), страница 10
Текст из файла (страница 10)
Because W(y∗ ) ≤ V(y∗ ), we have W(y∗ ) ≤V(y∗ ) < W(yq ).By combining the two parts of the proof, we conclude for any y = (y, α, γ )T andy∗ = (y∗ , α max , γ max )T , where y ∈ Y − Yopt and y∗ ∈ Yopt , that the virtual energy Wis minimized at y∗ . Hence, the Markov chain converges to y∗ with probability oneaccording to Proposition 1.Acknowledgments Research supported by the National Science Foundation Grants MIP96-32316and IIS 03-12084 and a Department of Energy Early Career Principal Investigator Grant.References1. Aarts, E., Korst, J.: Simulated Annealing and Boltzmann Machines. Wiley, New York (1989)2. Anily, S., Federgruen, A.: Ergodicity in parametric nonstationary Markov chains: an applicationto simulated annealing methods.
Operations Res. 35(6):867–874 (1987)3. Anily, S., Federgruen, A.: Simulated annealing methods with general acceptance probabilities.J. Appl. Prob. 24:657–667 (1987)4. Auslender, A., Cominetti, R., Maddou, M.: Asymptotic analysis for penalty and barrier methodsin convex and linear programming. Math. Operations Res. 22:43–62 (1997)5. Back, T., Hoffmeister, F., Schwefel, H.-P.: A survey of evolution strategies. In: Proceedings of the4th Int’l Conference on Genetic Algorithms, pp 2–9. San Diego, CA (1991)6. Bean, J. C., Hadj-Alouane, A. B.: A dual genetic algorithm for bounded integer programs.
In Technical Report TR 92-53, Department of Industrial and Operations Engineering, The University ofMichigan (1992)7. Bertsekas, D. P., Koksal, A. E.: Enhanced optimality conditions and exact penalty functions.Proceedings of Allerton Conference, Allerton, IL (2000)8. Bongartz, I.,Conn, A. R.,Gould, N., Toint, P. L.: CUTE: Constrained and unconstrained testingenvironment. ACM Trans. Math Softw, 21(1):123–160 (1995)9. Chen, Y.
X.: Solving nonlinear constrained optimization problems through constraint partitioning.Ph.D. thesis, Department of Computer Science, University of Illinois, Urbana, IL (2005)10. Corana, A., Marchesi, M., Martini, C., Ridella, S.: Minimizing multimodal functions of continuous variables with the simulated annealing algorithm. ACM Trans. Math.
Softw. 13(3):262–280(1987)11. Evans, J. P., Gould, F. J., Tolle, J. W.: Exact penalty functions in nonlinear programming. Math.Program. 4:72–97 (1973)12. Fletcher, R.: A class of methods for nonlinear programming with termination and convergenceproperties. In: Abadie J. (ed.) Integer and Nonlinear Programming. North-Holland, Amsterdam(1970)13. Fletcher, R.: An exact penalty function for nonlinear programming with inequalities.
TechnicalReport 478, Atomic Energy Research Establishment, Harwell (1972)14. Fourer, R., Gay, D. M., Kernighan, B. W.: AMPL: A Modeling Language for MathematicalProgramming. Brooks Cole Publishing Company (2002)15. Freidlin, M. I., Wentzell, A. D.: Random Perturbations of Dynamical Systems. Springer, Berlin(1984)16. Gill, P. E., Murray, W., Saunders, M.: SNOPT: an SQP algorithm for large-scale constrainedoptimization. SIAM J.
Optim. 12:979–1006 (2002)17. Homaifar, A., Lai, S. H-Y., Qi, X.: Constrained optimization via genetic algorithms. Simulation62(4):242–254 (1994)18. Joines, J., Houck, C.: On the use of non-stationary penalty functions to solve nonlinear constrainedoptimization problems with gas. In: Proceedings of the First IEEE Int’l Conf. on EvolutionaryComputation, pp. 579–584. Orlando, FL (1994)19.
Kirkpatrick, S., Gelatt, Jr., C.D., Vecchi, M.P.: Optimization by simulated annealing. Science220(4598):671–680 (1983)20. Krishnan, S., Krishnamoorthy, S., Baumgartner, G., Lam, C. C., Ramanujam, J., Sadayappan, P.,Choppella, V.: Efficient synthesis of out-of-core algorithms using a nonlinear optimization solver.J Glob Optim21.22.23.24.25.26.27.28.29.30.31.32.33.Technical report, Department of Computer and Information Science, Ohio State University,Columbus, OH (2004)Kuri, A.: A universal electric genetic algorithm for constrained optimization. In: Proceedings ofthe 6th European Congress on Intelligent Techniques and Soft Computing, pp.
518–522. Aachen,Germany (1998)Luenberger, D.G.: Linear and Nonlinear Programming. Addison-Wesley, Reading, MA (1984)Mitra, D., Romeo, F., Vincentelli, A.S.: Convergence and finite-time behavior of simulated annealing. Adv. Appl. Prob. 18:747–771 (1986)Rardin, R.L.: Optimization in Operations Research. Prentice Hall, New York (1998)Trouve, A.: Rough large deviation estimates for the optimal convergence speed exponent ofgeneralized simulated annealing algorithms. Technical report, LMENS-94-8, Ecole NormaleSuperieure, France (1994)Trouve, A.: Cycle decomposition and simulated annealing. SIAM J.
Control Optim. 34(3):966–986(1996)Wah, B., Chen, Y. X.: Constraint partitioning in penalty formulations for solving temporal planning problems. Artif Intel 170(3):187–231 (2006)Wah, B. W., Chen, Y. X.: Solving large-scale nonlinear programming problems by constraint partitioning. In: Proceedigs of the Principles and Practice of Constraint Programming, LCNS-3709,pp. 697–711. Springer-Verlag, New York (2005)Wah, B.W., Wang, T.: Simulated annealing with asymptotic convergence for nonlinear constrainedglobal optimization. In: Proceedings of the Principles and Practice of Constraint Programming,pp.
461–475. Springer-Verlag, New York (1999)Wah, B.W., Wu, Z.: The theory of discrete Lagrange multipliers for nonlinear discrete optimization. In: Proceedings of the Principles and Practice of Constraint Programming, pp. 28–42.Springer-Verlag, New York (1999)Wang, T.: Global Optimization for Constrained Nonlinear Programming. Ph.D. thesis, Department of Computer Science, University of Illinois, Urbana, IL (2000)Wu, Z.: The Theory and Applications of Nonlinear Constrained Optimization using LagrangeMultipliers. Ph.D.
thesis, Department of Computer Science, University of Illinois, Urbana, IL(2001)Zangwill, W.I.: Nonlinear programming via penalty functions. Manag. Sci. 13:344–358 (1967).