Abstract
Recent research has demonstrated that ordinal comparison has fast convergence despite the possible presence of large estimation noise in the design of discrete event dynamic systems. In this paper, we address the fundamental problem of characterizing the convergence of ordinal comparison. To achieve this goal, an indicator process is formulated and its properties are examined. For several performance measures frequently used in simulation, the rate of convergence for the indicator process is proven to be exponential for regenerative simulations. Therefore, the fast convergence of ordinal comparison is supported and explained in a rigorous framework. Many performance measures of averaging type have asymptotic normal distributions. The results of this paper show that ordinal comparison converges monotonically in the case of averaging normal random variables. Such monotonicity is useful in simulation planning.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Doob, J. L.,Stochastic Processes, John Wiley and Sons, New York, New York, 1953.
Simon, H.,Economics, Bounded Rationality, and the Cognitive Revolution, Edward Elgar Publisher, Brookfield, Vermont, 1992.
Kushner, H. J., andClark, D. S.,Stochastic Approximation for Constrained and Unconstrained Systems, Springer Verlag, New York, New York, 1978.
Fabian, V.,Stochastic Approximation, Optimizing Methods in Statistics, Edited by J. S. Rustagi, Academic Press, New York, New York, pp. 439–470, 1971.
Dupuis, P., andKushner, H. J.,Stochastic Approximation and Large Deviations: Upper Bounds and w.p.1 Convergence, SIAM Journal on Control and Optimization, Vol. 27, pp. 1108–1135, 1989.
Barnhart, C. M., Wieselthier, J. E., andEphremides, A.,Ordinal Optimization by Means of Standard Clock Simulation and Crude Analytical Models, Proceedings of the 33rd Conference on Decision and Control, Lake Buena Vista, Florida, pp. 2645–2647, 1994.
Ho, Y. C.,Heuristics, Rule of Thumb, and the 80/20 Proposition, IEEE Transactions on Automatic Control, Vol. 39, pp. 1025–1027, 1994.
Ho, Y. C.,Overview of Ordinal Optimization, Proceedings of the 33rd Conference on Decision and Control, Lake Buena Vista, Florida, pp. 1975–1977, 1994.
Ho, Y. C., andDeng, M.,The Problem of Large Search Space in Stochastic Optimization, Proceedings of the 33rd Conference on Decision and Control, Lake Buena Vista, Florida, pp. 1470–1475, 1994.
Ho, Y. C., Sreenivas, R. S., andVakili, P.,Ordinal Optimization in DEDS, Discrete Event Dynamic Systems: Theory and Applications, Vol. 2, pp. 61–88, 1992.
Patsis, N., Chen, C. H., andLarson, M.,Parallel Simulations of DEDS, IEEE Transactions on Control Technology, 1996 (to appear).
Cassandras, C. G., andBao, G.,A Stochastic Comparison Algorithm for Continuous Optimization with Estimations, Proceedings of the 33rd Conference on Decision and Control, Lake Buena Vista, Florida, pp. 676–677, 1994.
Cassandras, C. G., andJulka, V.,Descent Algorithms for Discrete Resource Allocation Problems, Proceedings of the 33rd Conference on Decision and Control, Lake Buena Vista, Florida, pp. 2639–2644, 1994.
Gong, W. B., Ho, Y. C., andZhai, W.,Stochastic Comparison Algorithm for Discrete Optimization with Estimations, Discrete Event Dynamic Systems: Theory and Applications, 1996 (to appear).
Yan, D., andMukai, H.,Optimization Algorithm with Probabilistic Estimation, Journal of Optimization Theory and Applications, Vol. 79, pp. 345–371, 1993.
Vakili, P., Mollamustaflaglu, L., andHo, Y. C.,Massively Parallel Simulation of a Class of Discrete Event Systems, Proceedings of the IEEE Frontiers MPC-92 Symposium, Washington, DC, 1992.
Cassandras, C. G., andStrickland, S.,Observable Augmented Systems for Sensitivity Analysis of Markov and Semi-Markov Processes, IEEE Transactions on Automatic Control, Vol. 34, pp. 1026–1037, 1989.
Pan, J., andCassandras, C. G.,Parallel Sample Path Construction Techniques for Discrete Event Systems: K-Constructability and Applications, Proceedings of the 33rd Conference on Decision and Control, Lake Buena Vista, Florida, pp. 1978–1983, 1994.
Fujimoto, R. M.,Parallel Discrete Event Simulation, Communications of the ACM, Vol. 33, pp. 31–53, 1990.
Santner, T. J., andTamhane, A. C.,Design of Experiments, Marcel Dekker, New York, New York, 1984.
Ho, Y. C., Deng, M., andHu, J.,Effect of Correlated Estimation Error in Ordinal Optimization, Proceedings of the 1992 Winter Simulation Conference, pp. 466–475, 1992.
Glasserman, P., andVakili, P.,Comparing Markov Chains Simulated in Parallel, Probability in the Engineering and Information Sciences, Vol. 8, pp. 309–326, 1994.
Shedler, G. S.,Regeneration and Networks of Queues, Springer Verlag, New York, New York, 1987.
Kalashnikov, V. V.,Topics on Regenerative Processes, CRC Press, Boca Raton, Florida, 1994.
Strickland, S. G.,Importance Sampling for Quick Simulation of Rare Events, Unpublished Manuscript, University of Virginia, 1993.
Kleinrock, L.,Queueing Systems, Vol. 1, John Wiley and Sons, New York, New York, 1975.
Thorisson, H.,The Queue GI/G/1: Finite Moments of the Cycle Variables and Uniform Rates of Convergence, Stochastic Processes and Their Applications, Vol. 19, pp. 85–99, 1985.
Iglehart, D. L., andShedler, G. S.,Statistical Efficiency of Regenerative Simulation Methods for Networks of Queues, Advances in Applied Probability, Vol. 15, pp. 183–197, 1983.
Ho, Y. C., andCao, X. R.,Perturbation Analysis of Discrete Event Dynamic Systems, Kluwer Academic Publishers, Boston, Massachusetts, 1991.
Deuschel, J. D., andStrook, D. W.,Large Deviations, Academic Press, Boston, Massachusetts, 1989.
Kotz, S., andJohnson, N. L.,Encyclopedia of Statistical Sciences, John Wiley, New York, New York, Vol. 5, 1985.
Author information
Authors and Affiliations
Additional information
Communicated by D. Q. Mayne
The author would like to thank C. G. Cassandras, X. Chao, S. G. Strickland, X. Xie, and the reviewers for their helpful suggestions.
Rights and permissions
About this article
Cite this article
Dai, L. Convergence properties of ordinal comparison in the simulation of discrete event dynamic systems. J Optim Theory Appl 91, 363–388 (1996). https://doi.org/10.1007/BF02190101
Issue Date:
DOI: https://doi.org/10.1007/BF02190101