American Institute of Mathematical Sciences

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

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

Vladimir Gaitsgory 1, , Alex Parkinson 1, and  Ilya Shvartsman 2,,

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.

Keywords: Optimal control, discrete systems, infinite horizon, long-run average, occupational measures, linear programming, duality.
Mathematics Subject Classification: Primary:49N15, 93C55.
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]

Jingang Zhao, Chi Zhang. Finite-horizon optimal control of discrete-time linear systems with completely unknown dynamics using Q-learning. Journal of Industrial & Management Optimization, 2021, 17 (3) : 1471-1483. doi: 10.3934/jimo.2020030
[5]

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
[6]

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
[7]

Jochen Jungeilges, Trygve Kastberg Nilssen, Tatyana Perevalova, Alexander Satov. Transitions between metastable long-run consumption behaviors in a stochastic peer-driven consumer network. Discrete & Continuous Dynamical Systems - B, 2021, 26 (11) : 5849-5871. doi: 10.3934/dcdsb.2021232
[8]

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
[9]

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
[10]

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
[11]

Evelyn Herberg, Michael Hinze, Henrik Schumacher. Maximal discrete sparsity in parabolic optimal control with measures. Mathematical Control & Related Fields, 2020, 10 (4) : 735-759. doi: 10.3934/mcrf.2020018
[12]

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
[13]

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
[14]

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
[15]

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
[16]

Yadong Shu, Bo Li. Linear-quadratic optimal control for discrete-time stochastic descriptor systems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021034
[17]

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
[18]

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
[19]

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
[20]

H. O. Fattorini. The maximum principle for linear infinite dimensional control systems with state constraints. Discrete & Continuous Dynamical Systems, 1995, 1 (1) : 77-101. doi: 10.3934/dcds.1995.1.77

2020 Impact Factor: 1.327

Tools

Metrics

  • PDF downloads (123)
  • HTML views (71)
  • Cited by (5)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy