×

Convergence analysis of gradient descent stochastic algorithms. (English) Zbl 0873.93084

The paper provides convergence analysis results for a sample-path based stochastic gradient-descent algorithm for optimizing expected-value performance measures in discrete event systems. The algorithm requires that the distance between two consecutive iteration points converge to zero as the iterate count goes to infinity. The paper gives two convergence results: one for the case where the expected-value function is continuously differentiable and the other when the function is nondifferentiable but the sample performance functions are convex. The proofs are based on a version of the uniform law of large numbers which is provable for many discrete event systems where infinitesimal perturbation analysis is known to be strongly consistent.

MSC:

93E25 Computational methods in stochastic control (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ho, Y. C., andCao X. R.,Perturbation Analysis of Discrete Event Dynamic Systems, Kluwer Academic Publishers, Boston, Massachusetts, 1991. · Zbl 0744.90036
[2] Rubinstein, R. Y., andShapiro, A.,Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method, John Wiley and Sons, New York, New York, 1993. · Zbl 0805.93002
[3] Shapiro, A., andWardi, Y.,Nondifferentiability of the Steady-State Function in Discrete Event Dynamic Systems, IEEE Transactions on Automatic Control, Vol. 39, pp. 1707–1711, 1994. · Zbl 0800.93040
[4] Clarke, F. H.,Optimization and Nonsmooth Analysis, John Wiley and Sons, New York, New York, 1983. · Zbl 0582.49001
[5] Rockefellar, R. T.,Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.
[6] Robinson, S. M.,Convergence of Subdifferentials under Strong Stochastic Convexity, Management Science (to appear). · Zbl 0859.90101
[7] Shapiro, A., andWardi, Y.,Convergence Analysis of Stochastic Algorithms, Mathematics of Operations Research (to appear). · Zbl 0868.90114
[8] Correa, R., andLemaréchal, C.,Convergence of Some Algorithms for Convex Minimization, Mathematical Programming, Vol. 62, pp. 261–275, 1993. · Zbl 0805.90083
[9] Demyanov, V. F., andVasilev, L. V.,Nondifferentiable Optimization, Optimization Software, Publications Division, New York, New York, 1985.
[10] Fu, M. C.,Optimization via Simulation: A Review, Annals of Operations Research, Vol. 53, pp. 199–247, 1994. · Zbl 0833.90089
[11] Chong, E. K. P., andRamadge, P. J.,Optimization of Queues Using Infinitessimal Perturbation Analysis-Based Stochastic Algorithm with General Update Times, SIAM Journal on Control and Optimization, Vol 31, pp. 698–732, 1993. · Zbl 0770.60082
[12] L’ecuyer, P., andGlynn, P.,Stochastic Optimization by Simulation: Convergence Proofs for the GI/G1 Queue in Steady State, Management Science, Vol. 40, pp. 1562–1578, 1994. · Zbl 0823.90046
[13] Chong, E. K. P., andRamadge, P. J.,Stochastic Optimization of Regenerative Systems Using Infinitestimal Perturbation Analysis, IEEE Transactions on Automatic Control, Vol. 39, pp. 1400–1410, 1994. · Zbl 0806.93058
[14] Shantikumar, J. G., andYao, D. D.,Second-Order Stochastic Properties of Queuering Systems, Proceedings of the IEEE, Vol. 77, pp. 162–170, 1989.
[15] Bartusek, J. D., andMarkowski, A. M.,On Stochastic Approximations Driven by Sample Averages: Convergence Results via the ODE Method, Manuscript, Institute for Systems Research, University of Maryland, 1993.
[16] Dupuis, P., andSimha, R.,On Sampling Controlled Stochastic Approximation, IEEE Transactions on Automatic Control, Vol. 36, pp. 915–924, 1991. · Zbl 0749.93081
[17] Meheshwari, S., andMukai, H.,An Optimization Algorithm Driven by Probabilistic Simulation, Proceedings of the Conference on Decision and Control, Athens, Greece, pp. 1703–1705, 1986.
[18] Yan, D., andMukai, H.,An Optimization Algorithm with Probabilistic Simulation, Journal of Optimization Theory and Applications, Vol. 79, pp. 345–371, 1993. · Zbl 0797.90072
[19] Wardi, Y.,Stochastic Algorithms with Armijo Stepsizes for Minimization of functions, Journal of Optimization Theory and Applications, Vol. 64, pp. 399–417, 1990. · Zbl 0687.90086
[20] Hiriart-Urruty, J. B., andLemaréchal, C.,Convex Analysis and Minimization Algorithms, Part 1, Springer Verlag, Berlin, Germany, 1993. · Zbl 0795.49001
[21] Hiriart-Urruty, J. B., andLemaréchal, C.,Convex Analysis and Minimization Algorithms, Part 2, Springer Verlag, Berlin, Germany, 1993. · Zbl 0795.49001
[22] Shapiro, A.,Asymptotic Properties of Statistical Estimators in Stochastic Programming, Annals of Statistics, Vol. 17, pp. 841–858, 1989. · Zbl 0688.62025
[23] Wardi, Y.,Interchangeability of Expectation and Differentiation of Waiting Times in GI/G1 Queues, Stochastic Processes and Their Applications, Vol. 45, pp. 141–154, 1993. · Zbl 0764.60102
[24] Glasserman, P.,Gradient Estimation via Perturbation Analysis, Kluwer Academic Publishers, Boston, Massachusetts, 1991. · Zbl 0746.90024
[25] Asmussen, S.,Applied Probability and Queues, John Wiley and Sons, New York, New York, 1987. · Zbl 0624.60098
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.