# American Institute of Mathematical Sciences

December  2017, 22(10): 3821-3838. doi: 10.3934/dcdsb.2017192

## Linear programming formulations of deterministic infinite horizon optimal control problems in discrete time

 1 Department of Mathematics, Macquarie University, Macquarie Park, NSW 2113, Australia 2 Department of Mathematics and Computer Science, Penn State Harrisburg, Middletown, PA 17057, USA

* Corresponding author

Received  January 2017 Revised  March 2017 Published  July 2017

This paper is devoted to a study of infinite horizon optimal control problems with time discounting and time averaging criteria in discrete time. We establish that these problems are related to certain infinite-dimensional linear programming (IDLP) problems. We also establish asymptotic relationships between the optimal values of problems with time discounting and long-run average criteria.

Citation: Vladimir Gaitsgory, Alex Parkinson, Ilya Shvartsman. Linear programming formulations of deterministic infinite horizon optimal control problems in discrete time. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3821-3838. doi: 10.3934/dcdsb.2017192
##### References:
 [1] D. Adelman and D. Klabjan, Duality and existence of optimal policies in generalized joint replenishment, Mathematics of Operations Research, 30 (2005), 28-50.  doi: 10.1287/moor.1040.0109.  Google Scholar [2] R. Ash, Measure, Integration and Functional Analysis, Academic Press, 1972.  Google Scholar [3] J. -P. Aubin, Viability Theory Birkhäuser, 1991.  Google Scholar [4] M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Systems and Control: Foundations and Applications, Birkhäuser, Boston, 1997. doi: 10.1007/978-0-8176-4755-1.  Google Scholar [5] A. G. Bhatt and V. S. Borkar, Occupation measures for controlled Markov processes: Characterization and optimality, Annals of Probability, 24 (1996), 1531-1562.  doi: 10.1214/aop/1065725192.  Google Scholar [6] C. J. Bishop, E. A. Feinberg and J. Zhang, Examples concerning Abel and Cesaro limits, Journal of Mathematical Analysis and Applications, 420 (2014), 1654-1661.  doi: 10.1016/j.jmaa.2014.06.017.  Google Scholar [7] J. Blot, A Pontryagin principle for infinite-horizon problems under constraints, Dynamics of Continuous, Discrete and Impulsive Systems Series B: Applications and Algorithms, 19 (2012), 267-275.   Google Scholar [8] V. S. Borkar, A convex analytic approach to Markov decision processes, Probability Theory and Related Fields, 78 (1988), 583-602.  doi: 10.1007/BF00353877.  Google Scholar [9] R. Buckdahn, D. Goreac and M. Quincampoix, Stochastic optimal control and linear programming approach, Appl. Math. Optim, 63 (2011), 257-276.  doi: 10.1007/s00245-010-9120-y.  Google Scholar [10] D. A. Carlson, A. B. Haurier and A. Leizarowicz, Infinite Horizon Optimal Control. Deterministic and Stochastic Processes, Springer, Berlin, 1991. doi: 10.1007/978-3-642-76755-5.  Google Scholar [11] N. Dunford and J. T. Schwartz, Linear Operators, Part I, General Theory, Wiley & Sons, Inc. , New York, 1988.  Google Scholar [12] L. Finlay, V. Gaitsgory and I. Lebedev, Duality in linear programming problems related to deterministic long run average problems of optimal control, SIAM J. Control and Optimization, 47 (2008), 1667-1700.  doi: 10.1137/060676398.  Google Scholar [13] W. H. Fleming and D. Vermes, Convex duality approach to the optimal control of diffusions, SIAM J. Control Optimization, 27 (1989), 1136-1155.  doi: 10.1137/0327060.  Google Scholar [14] V. Gaitsgory, On representation of the limit occupational measures set of control systems with applications to singularly perturbed control systems, SIAM J. Control and Optimization, 43 (2004), 325-340.  doi: 10.1137/S0363012903424186.  Google Scholar [15] V. Gaitsgory and M. Quincampoix, Linear programming approach to deterministic infinite horizon optimal control problems with discounting, SIAM J. Control and Optim, 48 (2009), 2480-2512.  doi: 10.1137/070696209.  Google Scholar [16] V. Gaitsgory and M. Quincampoix, On sets of occupational measures generated by a deterministic control system on an infinite time horizon, Nonlinear Analysis (Theory, Methods & Applications), 88 (2013), 27-41.  doi: 10.1016/j.na.2013.03.015.  Google Scholar [17] V. Gaitsgory and S. Rossomakhine, Linear programming approach to deterministic long run average problems of optimal control, SIAM J. of Control and Optimization, 44 (2006), 2006-2037.  doi: 10.1137/040616802.  Google Scholar [18] D. Goreac and O.-S. Serea, Linearization techniques for $L^{∞}$ -control problems and dynamic programming principles in classical and $L^{∞}$ control problems, ESAIM: Control, Optimization and Calculus of Variations, 18 (2012), 836-855.  doi: 10.1051/cocv/2011183.  Google Scholar [19] L. Grüne, Asymptotic controllability and exponential stabilization of nonlinear control systems at singular points, SIAM J. Control Optim, 36 (1998), 1495-1503.  doi: 10.1137/S0363012997315919.  Google Scholar [20] L. Grüne, On the relation between discounted and average optimal value functions, J. Diff. Equations, 148 (1998), 65-69.  doi: 10.1006/jdeq.1998.3451.  Google Scholar [21] D. Hernandez-Hernandez, O. Hernandez-Lerma and M. Taksar, The linear programming approach to deterministic optimal control problems, Appl. Math., 24 (1996), 17-33.   Google Scholar [22] O. Hernandez-Lerma and J. B. Lasserre, The linear programmimg approach, Handbook of Markov Decision Processes: Methods and Applications, 32 (2007), 528-550.  doi: 10.1007/978-1-4615-0805-2_12.  Google Scholar [23] D. Klabjan and D. Adelman, An Infinite-dimensional linear programming algorithm for deterministic semi-Markov decision processes on Borel spaces, Mathematics of Operations Research, 32 (2007), 528-550.  doi: 10.1287/moor.1070.0252.  Google Scholar [24] T. G. Kurtz and R. H. Stockbridge, Existence of Markov controls and characterization of optimal Markov controls, SIAM J. on Control and Optimization, 36 (1998), 609-653.  doi: 10.1137/S0363012995295516.  Google Scholar [25] J. B. Lasserre, D. Henrion, C. Prieur and E. Trélat, Nonlinear optimal control via occupation measures and LMI-relaxations, SIAM J. Control Optim, 47 (2008), 1643-1666.  doi: 10.1137/070685051.  Google Scholar [26] E. Lehrer and S. Sorin, A uniform Tauberian theorem in dynamic programming, Mathematics of Operations Research, 17 (1992), 303-307.  doi: 10.1287/moor.17.2.303.  Google Scholar [27] M. Quincampoix and O. Serea, The problem of optimal control with reflection studied through a linear optimization problem stated on occupational measures, Nonlinear Anal, 72 (2010), 2803-2815.  doi: 10.1016/j.na.2009.11.024.  Google Scholar [28] J. Renault, Uniform value in dynamic programming, J. European Mathematical Society, 13 (2011), 309-330.  doi: 10.4171/JEMS/254.  Google Scholar [29] J. E. Rubio, Control and Optimization. The Linear Treatment of Nonlinear Problems, Manchester University Press, Manchester, 1986.  Google Scholar [30] R. H. Stockbridge, Time-Average control of a martingale problem. Existence of a stationary solution, Annals of Probability, 18 (1990), 190-205.  doi: 10.1214/aop/1176990944.  Google Scholar [31] R. H. Stockbridge, Time-average control of a martingale problem: A linear programming formulation, Annals of Probability, 18 (1990), 206-217.  doi: 10.1214/aop/1176990945.  Google Scholar [32] R. Sznajder and J. A. Filar, Some comments on a theorem of Hardy and Littlewood, J. Optimization Theory and Applications, 75 (1992), 201-208.  doi: 10.1007/BF00939913.  Google Scholar [33] R. Vinter, Convex duality and nonlinear optimal control, SIAM J. Control and Optim, 31 (1993), 518-538.  doi: 10.1137/0331024.  Google Scholar [34] A. Zaslavski, Stability of the Turnpike Phenomenon in Discrete-Time Optimal Control Problems, Springer, 2014. doi: 10.1007/978-3-319-08034-5.  Google Scholar [35] A. Zaslavski, Turnpike Properties in the Calculus of Variations and Optimal Control, Springer, New York, 2006.  Google Scholar [36] A. Zaslavski, Turnpike Phenomenon and Infinite Horizon Optimal Control, Springer Optimization and Its Applications, New York, 2014. doi: 10.1007/978-3-319-08828-0.  Google Scholar

show all references

##### References:
 [1] D. Adelman and D. Klabjan, Duality and existence of optimal policies in generalized joint replenishment, Mathematics of Operations Research, 30 (2005), 28-50.  doi: 10.1287/moor.1040.0109.  Google Scholar [2] R. Ash, Measure, Integration and Functional Analysis, Academic Press, 1972.  Google Scholar [3] J. -P. Aubin, Viability Theory Birkhäuser, 1991.  Google Scholar [4] M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Systems and Control: Foundations and Applications, Birkhäuser, Boston, 1997. doi: 10.1007/978-0-8176-4755-1.  Google Scholar [5] A. G. Bhatt and V. S. Borkar, Occupation measures for controlled Markov processes: Characterization and optimality, Annals of Probability, 24 (1996), 1531-1562.  doi: 10.1214/aop/1065725192.  Google Scholar [6] C. J. Bishop, E. A. Feinberg and J. Zhang, Examples concerning Abel and Cesaro limits, Journal of Mathematical Analysis and Applications, 420 (2014), 1654-1661.  doi: 10.1016/j.jmaa.2014.06.017.  Google Scholar [7] J. Blot, A Pontryagin principle for infinite-horizon problems under constraints, Dynamics of Continuous, Discrete and Impulsive Systems Series B: Applications and Algorithms, 19 (2012), 267-275.   Google Scholar [8] V. S. Borkar, A convex analytic approach to Markov decision processes, Probability Theory and Related Fields, 78 (1988), 583-602.  doi: 10.1007/BF00353877.  Google Scholar [9] R. Buckdahn, D. Goreac and M. Quincampoix, Stochastic optimal control and linear programming approach, Appl. Math. Optim, 63 (2011), 257-276.  doi: 10.1007/s00245-010-9120-y.  Google Scholar [10] D. A. Carlson, A. B. Haurier and A. Leizarowicz, Infinite Horizon Optimal Control. Deterministic and Stochastic Processes, Springer, Berlin, 1991. doi: 10.1007/978-3-642-76755-5.  Google Scholar [11] N. Dunford and J. T. Schwartz, Linear Operators, Part I, General Theory, Wiley & Sons, Inc. , New York, 1988.  Google Scholar [12] L. Finlay, V. Gaitsgory and I. Lebedev, Duality in linear programming problems related to deterministic long run average problems of optimal control, SIAM J. Control and Optimization, 47 (2008), 1667-1700.  doi: 10.1137/060676398.  Google Scholar [13] W. H. Fleming and D. Vermes, Convex duality approach to the optimal control of diffusions, SIAM J. Control Optimization, 27 (1989), 1136-1155.  doi: 10.1137/0327060.  Google Scholar [14] V. Gaitsgory, On representation of the limit occupational measures set of control systems with applications to singularly perturbed control systems, SIAM J. Control and Optimization, 43 (2004), 325-340.  doi: 10.1137/S0363012903424186.  Google Scholar [15] V. Gaitsgory and M. Quincampoix, Linear programming approach to deterministic infinite horizon optimal control problems with discounting, SIAM J. Control and Optim, 48 (2009), 2480-2512.  doi: 10.1137/070696209.  Google Scholar [16] V. Gaitsgory and M. Quincampoix, On sets of occupational measures generated by a deterministic control system on an infinite time horizon, Nonlinear Analysis (Theory, Methods & Applications), 88 (2013), 27-41.  doi: 10.1016/j.na.2013.03.015.  Google Scholar [17] V. Gaitsgory and S. Rossomakhine, Linear programming approach to deterministic long run average problems of optimal control, SIAM J. of Control and Optimization, 44 (2006), 2006-2037.  doi: 10.1137/040616802.  Google Scholar [18] D. Goreac and O.-S. Serea, Linearization techniques for $L^{∞}$ -control problems and dynamic programming principles in classical and $L^{∞}$ control problems, ESAIM: Control, Optimization and Calculus of Variations, 18 (2012), 836-855.  doi: 10.1051/cocv/2011183.  Google Scholar [19] L. Grüne, Asymptotic controllability and exponential stabilization of nonlinear control systems at singular points, SIAM J. Control Optim, 36 (1998), 1495-1503.  doi: 10.1137/S0363012997315919.  Google Scholar [20] L. Grüne, On the relation between discounted and average optimal value functions, J. Diff. Equations, 148 (1998), 65-69.  doi: 10.1006/jdeq.1998.3451.  Google Scholar [21] D. Hernandez-Hernandez, O. Hernandez-Lerma and M. Taksar, The linear programming approach to deterministic optimal control problems, Appl. Math., 24 (1996), 17-33.   Google Scholar [22] O. Hernandez-Lerma and J. B. Lasserre, The linear programmimg approach, Handbook of Markov Decision Processes: Methods and Applications, 32 (2007), 528-550.  doi: 10.1007/978-1-4615-0805-2_12.  Google Scholar [23] D. Klabjan and D. Adelman, An Infinite-dimensional linear programming algorithm for deterministic semi-Markov decision processes on Borel spaces, Mathematics of Operations Research, 32 (2007), 528-550.  doi: 10.1287/moor.1070.0252.  Google Scholar [24] T. G. Kurtz and R. H. Stockbridge, Existence of Markov controls and characterization of optimal Markov controls, SIAM J. on Control and Optimization, 36 (1998), 609-653.  doi: 10.1137/S0363012995295516.  Google Scholar [25] J. B. Lasserre, D. Henrion, C. Prieur and E. Trélat, Nonlinear optimal control via occupation measures and LMI-relaxations, SIAM J. Control Optim, 47 (2008), 1643-1666.  doi: 10.1137/070685051.  Google Scholar [26] E. Lehrer and S. Sorin, A uniform Tauberian theorem in dynamic programming, Mathematics of Operations Research, 17 (1992), 303-307.  doi: 10.1287/moor.17.2.303.  Google Scholar [27] M. Quincampoix and O. Serea, The problem of optimal control with reflection studied through a linear optimization problem stated on occupational measures, Nonlinear Anal, 72 (2010), 2803-2815.  doi: 10.1016/j.na.2009.11.024.  Google Scholar [28] J. Renault, Uniform value in dynamic programming, J. European Mathematical Society, 13 (2011), 309-330.  doi: 10.4171/JEMS/254.  Google Scholar [29] J. E. Rubio, Control and Optimization. The Linear Treatment of Nonlinear Problems, Manchester University Press, Manchester, 1986.  Google Scholar [30] R. H. Stockbridge, Time-Average control of a martingale problem. Existence of a stationary solution, Annals of Probability, 18 (1990), 190-205.  doi: 10.1214/aop/1176990944.  Google Scholar [31] R. H. Stockbridge, Time-average control of a martingale problem: A linear programming formulation, Annals of Probability, 18 (1990), 206-217.  doi: 10.1214/aop/1176990945.  Google Scholar [32] R. Sznajder and J. A. Filar, Some comments on a theorem of Hardy and Littlewood, J. Optimization Theory and Applications, 75 (1992), 201-208.  doi: 10.1007/BF00939913.  Google Scholar [33] R. Vinter, Convex duality and nonlinear optimal control, SIAM J. Control and Optim, 31 (1993), 518-538.  doi: 10.1137/0331024.  Google Scholar [34] A. Zaslavski, Stability of the Turnpike Phenomenon in Discrete-Time Optimal Control Problems, Springer, 2014. doi: 10.1007/978-3-319-08034-5.  Google Scholar [35] A. Zaslavski, Turnpike Properties in the Calculus of Variations and Optimal Control, Springer, New York, 2006.  Google Scholar [36] A. Zaslavski, Turnpike Phenomenon and Infinite Horizon Optimal Control, Springer Optimization and Its Applications, New York, 2014. doi: 10.1007/978-3-319-08828-0.  Google Scholar
 [1] Vladimir Gaitsgory, Alex Parkinson, Ilya Shvartsman. Linear programming based optimality conditions and approximate solution of a deterministic infinite horizon discounted optimal control problem in discrete time. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1743-1767. doi: 10.3934/dcdsb.2018235 [2] Fabio Bagagiolo. An infinite horizon optimal control problem for some switching systems. Discrete & Continuous Dynamical Systems - B, 2001, 1 (4) : 443-462. doi: 10.3934/dcdsb.2001.1.443 [3] Andrew Vlasic. Long-run analysis of the stochastic replicator dynamics in the presence of random jumps. Journal of Dynamics & Games, 2018, 5 (4) : 283-309. doi: 10.3934/jdg.2018018 [4] Jianhui Huang, Xun Li, Jiongmin Yong. A linear-quadratic optimal control problem for mean-field stochastic differential equations in infinite horizon. Mathematical Control & Related Fields, 2015, 5 (1) : 97-139. doi: 10.3934/mcrf.2015.5.97 [5] Valery Y. Glizer, Oleg Kelis. Asymptotic properties of an infinite horizon partial cheap control problem for linear systems with known disturbances. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 211-235. doi: 10.3934/naco.2018013 [6] Naïla Hayek. Infinite-horizon multiobjective optimal control problems for bounded processes. Discrete & Continuous Dynamical Systems - S, 2018, 11 (6) : 1121-1141. doi: 10.3934/dcdss.2018064 [7] Vincenzo Basco, Piermarco Cannarsa, Hélène Frankowska. Necessary conditions for infinite horizon optimal control problems with state constraints. Mathematical Control & Related Fields, 2018, 8 (3&4) : 535-555. doi: 10.3934/mcrf.2018022 [8] Galina Kurina, Sahlar Meherrem. Decomposition of discrete linear-quadratic optimal control problems for switching systems. Conference Publications, 2015, 2015 (special) : 764-774. doi: 10.3934/proc.2015.0764 [9] Rein Luus. Optimal control of oscillatory systems by iterative dynamic programming. Journal of Industrial & Management Optimization, 2008, 4 (1) : 1-15. doi: 10.3934/jimo.2008.4.1 [10] Senda Ounaies, Jean-Marc Bonnisseau, Souhail Chebbi, Halil Mete Soner. Merton problem in an infinite horizon and a discrete time with frictions. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1323-1331. doi: 10.3934/jimo.2016.12.1323 [11] Alexander Tarasyev, Anastasia Usova. Application of a nonlinear stabilizer for localizing search of optimal trajectories in control problems with infinite horizon. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 389-406. doi: 10.3934/naco.2013.3.389 [12] Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003 [13] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [14] Qiying Hu, Wuyi Yue. Optimal control for resource allocation in discrete event systems. Journal of Industrial & Management Optimization, 2006, 2 (1) : 63-80. doi: 10.3934/jimo.2006.2.63 [15] Michael Basin, Pablo Rodriguez-Ramirez. An optimal impulsive control regulator for linear systems. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 275-282. doi: 10.3934/naco.2011.1.275 [16] H. O. Fattorini. The maximum principle for linear infinite dimensional control systems with state constraints. Discrete & Continuous Dynamical Systems - A, 1995, 1 (1) : 77-101. doi: 10.3934/dcds.1995.1.77 [17] Qiying Hu, Wuyi Yue. Optimal control for discrete event systems with arbitrary control pattern. Discrete & Continuous Dynamical Systems - B, 2006, 6 (3) : 535-558. doi: 10.3934/dcdsb.2006.6.535 [18] Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397 [19] Radu Ioan Boţ, Sorin-Mihai Grad. On linear vector optimization duality in infinite-dimensional spaces. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 407-415. doi: 10.3934/naco.2011.1.407 [20] Thomas Jordan, Mark Pollicott. The Hausdorff dimension of measures for iterated function systems which contract on average. Discrete & Continuous Dynamical Systems - A, 2008, 22 (1&2) : 235-246. doi: 10.3934/dcds.2008.22.235

2018 Impact Factor: 1.008