Stochastic approximation algorithms for constrained optimization via simulation

Abstract

We develop four algorithms for simulation-based optimization under multiple inequality constraints. Both the cost and the constraint functions are considered to be long-run averages of certain state-dependent single-stage functions. We pose the problem in the simulation optimization framework by using the Lagrange multiplier method. Two of our algorithms estimate only the gradient of the Lagrangian, while the other two estimate both the gradient and the Hessian of it. In the process, we also develop various new estimators for the gradient and Hessian. All our algorithms use two simulations each. Two of these algorithms are based on the smoothed functional (SF) technique, while the other two are based on the simultaneous perturbation stochastic approximation (SPSA) method. We prove the convergence of our algorithms and show numerical experiments on a setting involving an open Jackson network. The Newton-based SF algorithm is seen to show the best overall performance.

References

1. Bertsekas, D. P. and Tsitsiklis, J. N. 1996. Neuro-Dynamic Programming. Athena Scientific, Belmont, MA.
2. Bhatnagar, S. 2005. Adaptive multivariate three-timescale stochastic approximation algorithms for simulation based optimization. ACM Trans. Model. Comput. Simul. 15, 1, 74--107.
3. Bhatnagar, S. 2007. Adaptive Newton-based smoothed functional algorithms for simulation optimization. ACM Trans. Model. Comput. Simul. 18, 1, 27--62.
4. Bhatnagar, S. 2010. An actor-critic algorithm with function approximation for discounted cost constrained Markov decision processes. Syst. Control Lett. 59, 760--766.
5. Bhatnagar, S. and Borkar, V. S. 1998. A two time scale stochastic approximation scheme for simulation based parametric optimization. Prob. Eng. Inf. Sci. 12, 519--531.
6. Bhatnagar, S. and Borkar, V. S. 2003. Multiscale chaotic SPSA and smoothed functional algorithms for simulation optimization. Simulation 79, 10, 568--580.
7. Bhatnagar, S., Fu, M. C., Marcus, S. I., and Bhatnagar, S. 2001. Two timescale algorithms for simulation optimization of hidden Markov models. IIE Trans. 33, 3, 245--258.
8. Borkar, V. S. 1997. Stochastic approximation with two timescales. Syst. Control Lett. 29, 291--294.
9. Borkar, V. S. 2005. An actor-critic algorithm for constrained Markov decision processes. Syst. Control Lett. 54, 207--213.
10. Brandiere, O. 1998. Some pathological traps for stochastic approximation. SIAM J. Control Optim. 36, 1293--1314.
11. Cassandras, C. G. 1993. Discrete Event Systems: Modeling and Performance Analysis. Aksen Associates, Boston, MA.
12. Chen, H. F., Duncan, T. E., and Pasik-Duncan, B. 1999. A Kiefer-Wolfowitz algorithm with randomized differences. IEEE Trans. Auto. Cont. 44, 3, 442--453.
13. Hirsch, M. W. 1989. Convergent activation dynamics in continuous time networks. Neural Netw. 2, 331--349.
14. Ho, Y. C. and Cao, X. R. 1991. Perturbation Analysis of Discrete Event Dynamical Systems. Kluwer, Boston.
15. Katkovnik, V. Y. and Kulchitsky, Y. 1972. Convergence of a class of random search algorithms. Autom. Remote Control 8, 1321--1326.
16. Kushner, H. J. and Yin, G. G. 1997. Stochastic Approximation Algorithms and Applications. Springer, Berlin.
17. Mas-Colell, A., Whinston, M. D., and Green, J. R. 1995. Microeconomic Theory. Oxford University Press, Oxford, UK.
18. Meyn, S. P. and Tweedie, R. L. 1993. Markov Chains and Stochastic Stability. (2nd ed.), Springer, Berlin.
19. Sadegh, P. 1997. Constrained optimization via stochastic approximation with a simultaneous perturbation gradient approximation. Automatica 33, 889--892.
20. Spall, J. C. 1992. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Trans. Autom. Control 37, 3, 332--341.
21. Spall, J. C. 2000. Adaptive stochastic approximation by the simultaneous perturbation method. IEEE Trans. Autom. Control 45, 1839--1853.
22. Styblinski, M. A. and Tang, T.-S. 1990. Experiments in nonconvex optimization: Stochastic approximation with function smoothing and simulated annealing. Neural Netw. 3, 467--483.
23. Tadic, V. B., Doucet, A., and Singh, S. 2003. Two time-scale stochastic approximation for constrained stochastic optimization and constrained Markov decision problems. In Proceedings of the American Control Conference, 4736--4741.
24. Wang, I.-J. and Spall, J. C. 2008. Stochastic optimization with inequality constraints using simultaneous perturbations and penalty functions. Int. J. Control 81, 8, 1232--1238.
25. Whitney, J. E. and Hill, S. D. 2001. Constrained optimization over discrete sets via SPSA with application to non-separable resource allocation. In Proceedings of the Winter Simulation Conference, 313--317.

Index Terms

• Computing methodologies

  • Modeling and simulation

    • Simulation theory

• Mathematics of computing

  • Probability and statistics