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

Vladimir Gaitsgory; Alex Parkinson; Ilya Shvartsman

doi:10.3934/dcdsb.2017192

Article Contents

2017, Volume 22, Issue 10: 3821-3838. Doi: 10.3934/dcdsb.2017192

This issue Previous Article Threshold dynamics of a reaction-diffusion epidemic model with stage structure Next Article Asymptotic dynamics in a two-species chemotaxis model with non-local terms

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
* Corresponding author

Received: December 31, 2016

Revised: February 28, 2017

Published: September 2017

Abstract Full Text(HTML) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary:49N15, 93C55.

Citation:

Full Text(HTML)

Related Papers

Cited by

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.
[2]	R. Ash, Measure, Integration and Functional Analysis, Academic Press, 1972.
[3]	J. -P. Aubin, Viability Theory Birkhäuser, 1991.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[11]	N. Dunford and J. T. Schwartz, Linear Operators, Part I, General Theory, Wiley & Sons, Inc. , New York, 1988.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[28]	J. Renault, Uniform value in dynamic programming, J. European Mathematical Society, 13 (2011), 309-330. doi: 10.4171/JEMS/254.
[29]	J. E. Rubio, Control and Optimization. The Linear Treatment of Nonlinear Problems, Manchester University Press, Manchester, 1986.
[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.
[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.
[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.
[33]	R. Vinter, Convex duality and nonlinear optimal control, SIAM J. Control and Optim, 31 (1993), 518-538. doi: 10.1137/0331024.
[34]	A. Zaslavski, Stability of the Turnpike Phenomenon in Discrete-Time Optimal Control Problems, Springer, 2014. doi: 10.1007/978-3-319-08034-5.
[35]	A. Zaslavski, Turnpike Properties in the Calculus of Variations and Optimal Control, Springer, New York, 2006.
[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.