Abstract
We consider continuous and impulse control of a Markov chain (MC) with a finite set of states in continuous time. Continuous control determines the intensity of transitions between MC states, while transition times and their directions are random. Nevertheless, sometimes it is necessary to ensure a transition that leads to an instantaneous change in the state of the MC. Since such transitions require different influences and can produce different effects on the state of the MC, such controls can be interpreted as impulse controls. In this work, we use the martingale representation of a controllable MC and give an optimality condition, which, using the principle of dynamic programming, is reduced to a form of quasi-variational inequality. The solution to this inequality can be obtained in the form of a dynamic programming equation, which for an MC with a finite set of states reduces to a system of ordinary differential equations with one switching line. We prove a sufficient optimality condition and give examples of problems with deterministic and random impulse action.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bensoussan, A. and Lions, J.L., Contrôle Impulsionnel et Inéquations Quasivariationnelles, Paris: Dunod, 1982.
Bensoussan, A. and Lions, J.L., Translated under the title Impul’snoe upravlenie i kvazivariatsionnye neravenstva, Moscow: Nauka, 1987.
Yushkevich, A.A., Markov Decision Processes with Both Continuous and Impulsive Control, in Stochastic Optimization. Lect. Notes in Control and Information Sci., Arkin, V.I., Shiraev, A., and Wets, R., Eds., Berlin: Springer, 1986, vol. 81, pp. 234–246. https://doi.org/10.1007/BFb0007100
Gatarek, D., Impulsive Control of Piecewise-Deterministic Processes, in Stochastic Systems and Optimization. Lect. Notes in Control and Information Sci., Zabczyk, J., Ed., Berlin: Springer, 1989, vol. 136, pp. 298–308. https://doi.org/10.1007/BFb0002690
Dempster, M.A.H. and Ye, J.J., Impulse Control of Piecewise Deterministic Markov Processes, Ann. Appl. Prob., 1995, vol. 5, no. 2, pp. 399–423. https://doi.org/10.1214/aoap/1177004771
Dufour, F. and Miller, B.M., Generalized Solutions in Nonlinear Stochastic Control Problems, SIAM J. Control Optim., 2002, vol. 40, pp. 1724–1745. https://doi.org/10.1137/S0363012900374221
Miller, B.M. and Rubinovich, E.Ya., Impulsive Control in Continuous and Discrete-Continuous Systems, New York: Kluwer, 2003. https://doi.org/10.1007/978-1-4615-0095-7
Miller, B.M. and Rubinovich, E.Ya., Optimizatsiya dinamicheskikh sistem s impul’snymi upravleniyami (Optimization of Dynamical Systems with Impulse Controls), Moscow: Nauka, 2005.
Miller, B.M. and Rubinovich, E.Ya., Optimizatsiya dinamicheskikh sistem s impul’snymi upravleniyami i udarnymi vozdeistviyami (Optimization of Dynamical Systems with Impulse Controls and Impact Influences), Moscow: LENAND/URSS, 2019.
Dufour, F., Horiguchi, M., and Piunovskiy, A.B., Optimal Impulsive Control of Piecewise Deterministic Markov Processes, Stoch., 2016, vol. 88, no. 7, pp. 1073–109. https://doi.org/10.1080/17442508.2016.1197925
Shujun Wang and Zhen Wu, Maximum Principle for Optimal Control Problems of Forward-Backward Regime-Switching Systems Involving Impulse Controls, Math. Probl. Eng., 2015, Article ID 892304. https://doi.org/10.1155/2015/892304
Dufour, F. and Piunovskiy, A.B., Impulsive Control for Continuous-Time Markov Decision Processes: A Linear Programming Approach, Appl. Math. Optim., 2016, vol. 74, pp. 129–161. https://doi.org/10.1007/s00245-015-9310-8
Delebecque, F. and Quadrat, J.-P., Optimal Control of Markov Chains Admitting Strong and Weak Interactions, Automatica, 1981, vol. 17, no. 2, pp. 281–296. https://doi.org/10.1016/0005-1098(81)90047-9
Bae, J., Kim, S., and Lee, E.Y., Average Cost under the p Mλ,τ Policy in a Finite Dam with Compound Poisson Inputs, J. Appl. Probab., 2003, vol. 40, no. 2, pp. 519–526. https://doi.org/10.1239/jap/1053003561
Filar, J.A. and Vrieze, K., Competitive Markov Decision Processes—Theory, Algorithms and Applications, New York: Springer, 1997. https://doi.org/10.1007/978-1-4612-4054-9
Williams, B.K., Markov Decision Processes in Natural Resources Management: Observability and Uncertainty, Ecological Modelling, 2009, vol. 220, no. 6, pp. 830–840. https://doi.org/10.1016/j.ecolmodel.2008.12.023
Miller, A., Dynamic Access Control with Active Users, J. Commun. Technol. Electron., 2010, vol. 55, no. 12, pp. 1432–1441. https://doi.org/10.1134/S1064226910120168
Miller, A. and Miller, B., Control of Connected Markov Chains. Application to Congestion Avoidance in the Internet, Proc. 50th IEEE Conf. on Decision and Control and European Control Conf. (CDC-ECC), Orlando, USA, 2011, pp. 7242–7248. https://doi.org/10.1109/CDC.2011.6161029
Miller, B. and McInnes, D., Optimal Management of a Two Dam System via Stochastic Control: Parallel Computing Approach, Proc. 50th IEEE Conf. on Decision and Control and Eur. Control Conf. (CDC-ECC), Orlando, USA, December 12–15, 2011, pp. 1417–1423. https://doi.org/10.1109/CDC.2011.6160566
McInnes, D. and Miller, B., Optimal Control of Large Dam Using Time-Inhomogeneous Markov Chains with an Application to Flood Control, IFAC-PapersOnLine, 2017, vol. 50, no. 1, pp. 3499–3504. https://doi.org/10.1016/j.ifacol.2017.08.936
McInnes, D., Miller, B., and Schreider, S., Optimisation of Gas Flows in South Eastern Australia via Controllable Markov Chains, Proc. Australian Control Conf., Newcastle: Engineers Australia, 2016, November 3–4, pp. 341–346. https://doi.org/10.1109/AUCC.2016.7868213
Avrachenkov, K., Habachi, O., Piunovskiy, A., and Zhang, Y., Infinite Horizon Optimal Impulsive Control with Applications to Internet Congestion Control, Int. J. Control, 2015, vol. 88, no. 4, pp. 703–716. https://doi.org/10.1080/00207179.2014.971436
McInnes, D. and Miller, B., Optimal Control of Time-Inhomogeneous Markov Chains with Application to Dam Management, Proc. Australian Control Conf., Perth, Australia, 2013, pp. 230–237. https://doi.org/10.1109/AUCC.2013.6697278
Kushner, H.J. and Dupuis, P.G., Numerical Methods for Stochastic Control Problems in Continuous Time, New York: Springer Science+Business Media, 2001, 2nd ed. https://doi.org/10.1007/978-1-4613-0007-6
Elliott, R.J., Aggoun, L., and Moore, J.B., Hidden Markov Models. Estimation and Control, New York: Springer-Verlag, 2008. https://doi.org/10.1007/978-0-387-84854-9
Miller, B., Miller, G., and Semenikhin, K., Torwards the Optimal Control of Markov Chains with Constraints, Automatica, 2010, vol. 46, pp. 1495–1502. https://doi.org/10.1016/j.automatica.2010.06.003
Miller, B.M., Miller, G.B., and Semenikhin, K.V., Methods to Design Optimal Control of Markov Process with Finite State Set in the Presence of Constraints, Autom. Remote Control, 2011, vol. 72, no. 2, pp. 323–341.
Miller, B.M., Miller, G.B., and Semenikhin, K.V., Optimal Control Problem Regularization for the Markov Process with Finite Number of States and Constraints, Autom. Remote Control, 2016, vol. 77, no. 9, pp. 1589–1611. https://doi.org/10.1134/S0005117916090071
Brémaud, P., Point Processes and Queues: Martingale Dynamics, New York: Springer, 1981.
Liptser, R.Sh. and Shiryaev, A.N., Statistics of Random Processes, New York: Springer, 1979.
Miller, B., Miller, G., and Semenikhin, K., Optimization of the Data Transmission Flow from Moving Object to Nonhomogeneous Network of Base Stations, IFAC-PapersOnLine, 2017, vol. 50, no. 1, pp. 6160–6165. https://doi.org/10.1016/j.ifacol.2017.08.981
Miller, A., Miller, B., Popov, A., and Stepanyan, K., Towards the Development of Numerical Procedure for Control of Connected Markov Chains, Proc. 5th Australian Control Conf. (AUCC), Gold Coast, Australia, November 5–6, 2015, 2015, pp. 336–341.
Miller, B., Stepanyan, K., Miller, A., and Popov, A., Towards One Nonconvex Connected Markov Chain Control Problem. An Approach to Numerical Solution, 2018 Australian New Zealand Control Conf. (ANZCC), Swinburne University of Technology, Melbourne, Australia, Dec. 7–8, 2018, pp. 172–177. https://doi.org/10.1109/ANZCC.2018.8606576
Miller, A., Miller, B., and Stepanyan, K., A Numerical Approach to Joint Continuous and Impulsive Control of Markov Chains, IFAC-PapersOnLine, 2018, vol. 51, no. 32, pp. 462–467. https://doi.org/10.1016/j.ifacol.2018.11.428
Karatzas, I. and Shreve, S.E., Connection Between Optimal Stopping and Singular Stochastic Control I. Monotone Follower Problems, SIAM J. Control Optim., 1984, vol. 22, no. 6, pp. 856–877. https://doi.org/10.1137/0322054
Miller, B.M., Miller, G.B., and Semenikhin, K.V., Optimal Channel Choice for Lossy Data Flow Transmission, Autom. Remote Control, 2018, vol. 79, no. 1, pp. 66–77. https://doi.org/10.1134/S000511791801006X
Funding
The work done by A.B. Miller and B.M. Miller was partially financially supported within the framework of State support for the Kazan (Volga) Federal University in order to increase its competitiveness among the world’s leading research and educational centers.
Author information
Authors and Affiliations
Corresponding authors
Additional information
This paper was recommended for publication by E. Ya. Rubinovich, a member of the Editorial Board
Russian Text © The Author(s), 2020, published in Avtomatika i Telemekhanika, 2020, No. 3, pp. 114–131.
Rights and permissions
About this article
Cite this article
Miller, A.B., Miller, B.M. & Stepanyan, K.V. Simultaneous Impulse and Continuous Control of a Markov Chain in Continuous Time. Autom Remote Control 81, 469–482 (2020). https://doi.org/10.1134/S0005117920030066
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0005117920030066