|
|
|
Stochastic learning and optimization — Ideas vs mathematics? |
Xi-Ren CAO1,2( ) |
| 1. Department of Automation, School of Electronic, Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China; 2. Department of Finance, Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai 200240, China |
|
|
|
|
Abstract What are the roles that ideas and mathematics play in research of engineering subjects? This article tries to answer this question with the author’s own research experience. In the past 30 years, the author’s research started from perturbation analysis (PA) of queueing networks, to PA of Markov systems, to Markov decision processes (MDP), and to stochastic control; and based on these research, the author has successfully developed a sensitivity-based optimization approach to the area of learning and optimization of stochastic systems, leading to a simple and unified framework for the area, new research directions, and new results in the area. This paper reviews the above research topics and the history of their development with an emphasis on what the roles that ideas and mathematics play in each of the advances along the path.
|
| Keywords
perturbation analysis (PA)
Markov decision processes (MDP)
sensitivity-based optimization
perturbation realization factors
performance potentials
|
|
Corresponding Author(s):
CAO Xi-Ren,Email:xrcao@sjtu.edu.cn, eecao@ust.edu.hk
|
|
Issue Date: 05 September 2011
|
|
| 1 |
Ho Y C, Eyler A, Chien T T. A gradient technique for general buffer-storage design in a serial production line. International Journal of Production Research , 1979, 17(6): 557-580
doi: 10.1080/00207547908919637
|
| 2 |
Ho Y C, Eyler A, Chien T T. A new approach to determine parameter sensitivities on transfer lines. Management Science , 1983, 29(6): 700-714
doi: 10.1287/mnsc.29.6.700
|
| 3 |
Bryson A E, Ho Y C. Applied Optimal Control: Optimiza tion, Estimation, and Control. Waltham , MA: Blaisdell, 1969
|
| 4 |
Ho Y C, Cao X R. Perturbation analysis and optimization of queueing networks. Journal of Optimization Theory and Applications , 1983, 40(4): 559-582
doi: 10.1007/BF00933971
|
| 5 |
Cao X R. Stochastic Learning and Optimization — A Sensitivity-Based Approach. New York , NY: Springer, 2007
|
| 6 |
Xia L, Cao X R. Performance optimization of queueing systems with perturbation realization. European Journal of Operations Research, invited survey paper, 2011 (submitted)
|
| 7 |
Cao X R. First-order perturbation analysis of a single multiclass finite source queue. Performance Evaluation , 1987, 7(1): 31-41
doi: 10.1287/opre.15.2.254
|
| 9 |
Heidelberger P, Cao X R, Zazanis M A, Suri R. Convergence properties of infinitesimal rerturbation analysis estimates. Management Science , 1988, 34(11): 1281-1302
doi: 10.1287/mnsc.34.11.1281
|
| 10 |
Cao X R. A Sample performance function of Jackson queueing networks. Operations Research , 1988, 36(1): 128-136
doi: 10.1287/opre.36.1.128
|
| 11 |
Cao X R. Realization Probabilities — The Dynamics of Queueing Systems. New York , NY: Springer Verlag, 1994
|
| 12 |
Cao X R. Convergence of parameter sensitivity estimates in a stochastic experiment. IEEE Transactions on Automatic Control , 1985, 30(9): 834-843
|
| 13 |
Glasserman P. Gradient Estimation via Perturbation Analysis. Boston , MA: Kluwer Academic Publishers, 1991
|
| 14 |
Cao X R. Realization probability in closed Jackson queueing networks and its application. Advances in Applied Probability , 1987, 19(3): 708-738
doi: 10.2307/1427414
|
| 15 |
Fu M C, Hu J Q. Conditional Monte Carlo: Gradient Estimation and Optimization Applications. Boston , MA: Kluwer Academic Publishers, 1997
|
| 16 |
Gong W B, Ho Y C. Smoothed (conditional) perturbation analysis for discrete event dynamic systems. IEEE Transactions on Automatic Control , 1987, 32(10): 858-866
doi: 10.1109/TAC.1987.1104464
|
| 17 |
Ho Y C, Cao X R, Cassandras C G. Infinitesimal and finite perturbation analysis for queueing networks. Automatica , 1983, 19(4): 439-445
doi: 10.1016/0005-1098(83)90060-2
|
| 18 |
Ho Y C, Cao X R. Perturbation Analysis of Discrete Event Systems. Norwell , MA: Kluwer Academic Publishers, 1991
doi: 10.1007/978-1-4615-4024-3
|
| 19 |
Cassandras C G, Wardi Y, Melamed B, Sun G, Panayiotou C G. Perturbation analysis for online control and optimization of stochastic fluid models. IEEE Transactions on Automatic Control , 2002, 47(8): 1234-1248
doi: 10.1109/TAC.2002.800739
|
| 20 |
Liu Y, Gong W B. Perturbation analysis for stochastic fluid queueing systems. Discrete Event Dynamic Systems: Theory and Applications , 2002, 12(4): 391-416
doi: 10.1023/A:1019707508130
|
| 21 |
Wardi Y, Melamed B, Cassandras C G, Panayiotou C G. Online IPA gradient estimators in stochastic continuous fluid models. Journal of Optimization Theory and Applications , 2002, 115(2): 369-405
doi: 10.1023/A:1020892306506
|
| 22 |
Cao X R, Chen H F. Perturbation realization, potentials, and sensitivity analysis of Markov processes. IEEE Transactions on Automatic Control , 1997, 42(10): 1382-1393
doi: 10.1109/9.633827
|
| 23 |
Cao X R, Yuan X M, Qiu L. A single sample path-based performance sensitivity formula for Markov chains. IEEE Transactions on Automatic Control , 1996, 41(12): 1814-1817
doi: 10.1109/9.545747
|
| 24 |
Cao X R. The potential structure of sample paths and performance sensitivities of Markov systems. IEEE Transactions on Automatic Control , 2004, 49(12): 2129-2142
doi: 10.1109/TAC.2004.838494
|
| 25 |
Cao X R. A unified approach to Markov decision problems and performance sensitivity analysis. Automatica , 2000, 36(5): 771-774
doi: 10.1016/S0005-1098(99)00207-1
|
| 26 |
Cao X R. From perturbation analysis to Markov decision processes and reinforcement learning. Discrete Event Dynamic Systems: Theory and Applications , 2003, 13(1-2): 9-39
doi: 10.1023/A:1022188803039
|
| 27 |
Fang H T, Cao X R. Potential-based on-line policy iteration algorithms for Markov decision processes. IEEE Transactions on Automatic Control , 2004, 49(4): 493-505
doi: 10.1109/TAC.2004.825647
|
| 28 |
Marbach P, Tsitsiklis T N. Simulation-based optimization of Markov reward processes. IEEE Transactions on Automatic Control , 2001, 46(2): 191-209
doi: 10.1109/9.905687
|
| 29 |
Zhang J Y, Cao X R. Continuous-time Markov decision processes with nth-bias optimality criteria. Automatica , 2009, 45(7): 1628-1638
doi: 10.1016/j.automatica.2009.03.009
|
| 30 |
Cao X R, Zhang J Y. The nth-order bias optimality for multichain Markov decision processes. IEEE Transactions on Automatic Control , 2008, 53(2): 496-508
doi: 10.1109/TAC.2007.915168
|
| 31 |
Puterman M L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. New York , NY: John Wiley & Sons, 1994
|
| 32 |
Veinott A F. Discrete dynamic programming with sensitive discount optimality criteria. The Annals of Mathematical Statistics , 1969, 40(5): 1635-1660
doi: 10.1214/aoms/1177697379
|
| 33 |
Cao X R. Basic ideas for event-based optimization of Markov systems. Discrete Event Dynamic Systems: Theory and Applications , 2005, 15(2): 169-197
doi: 10.1007/s10626-004-6211-4
|
| 34 |
Cao X R, Zhang J Y. Event-based optimization of Markov systems. IEEE Transactions on Automatic Control , 2008, 53(4): 1076-1082
doi: 10.1109/TAC.2008.919557
|
| 35 |
Xu Y K, Cao X R. Optimal control with Lebesgue sampling and time aggregation. IEEE Transactions on Automatic Control (to appear)
|
| 36 |
Xia L, Chen X, Cao X R. Policy iteration for customeraverage performance optimization of closed queueing systems. Automatica , 2009, 45(7): 1639-1648
doi: 10.1016/j.automatica.2009.03.007
|
| 37 |
Xia L, Cao X R. Aggregation of perturbation realization factors and service rate-based policy iteration for queueing systems. In: Proceedings of the 45th IEEE Conference on Decision and Control . 2006, 1063-1068
doi: 10.1109/CDC.2006.377674
|
| 38 |
Xia L, Cao X R. Relationship between perturbation realization factors with queueing models and Markov models. IEEE Transactions on Automatic Control , 2006, 51(10): 1699-1704
doi: 10.1109/TAC.2006.883022
|
| 39 |
Cao X R. Stochastic control of continuous-time and continuous-state systems via direct comparison. In: Proceedings of the 48th IEEE Conference on Decision and Control . 2009, 1593-1598
|
| 40 |
Cao X R. A new model of continuous-time Markov processes and impulse stochastic control. In: Proceedings of the 48th IEEE Conference on Decision and Control . 2009, 525-530
|
| 41 |
Cao X R, Wang D X, Lu T, Xu Y F. Stochastic control via direct comparison. 2011 (submitted)
|
| 42 |
Oksendal B, Sulem A. Applied Stochastic Control of Jump Diffusions. 2nd ed. Berlin: Springer, 2007
doi: 10.1007/978-3-540-69826-5
|
| 43 |
Ho Y C. What is experimental system engineering? ScienceNet , 2010. http://www.sciencenet.cn/m/user content. aspx?id=382212
|
| 44 |
Cao X R. Mathematics, analysis, and engineering. Guest article, Prof. Y. C. Ho’s blog at ScineceNet , 2008. http://www.sciencenet.cn/m/user content.aspx?id=38753
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
