Linear programming based optimality conditions and approximate solution of a deterministic infinite horizon discounted optimal control problem in discrete time

Vladimir Gaitsgory; Alex Parkinson; Ilya Shvartsman

doi:10.3934/dcdsb.2018235

Article Contents

2019, Volume 24, Issue 4: 1743-1767. Doi: 10.3934/dcdsb.2018235

This issue Previous Article Synchronization of first-order autonomous oscillators on Riemannian manifolds Next Article Limit cycles of discontinuous piecewise quadratic and cubic polynomial perturbations of a linear center

Linear programming based optimality conditions and approximate solution of a deterministic infinite horizon discounted optimal control problem 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: September 2017

Revised: January 2018

Early access: August 2018

Published: January 2019

Abstract / Introduction Full Text(HTML) Figure(4) Related Papers Cited by

Abstract

It has been recently established that a deterministic infinite horizon discounted optimal control problem in discrete time is closely related to a certain infinite dimensional linear programming problem and its dual, the latter taking the form of a certain max-min problem. In the present paper, we use these results to establish necessary and sufficient optimality conditions for this optimal control problem and to investigate a way how the latter can be used for the construction of a near optimal control.

Keywords:

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

Citation:

Full Text(HTML)

Figure 1. The state trajectory - 50 time steps

Download: Full-size image PowerPoint slide

Figure 2. The state trajectory - time step 1

Download: Full-size image PowerPoint slide

Figure 3. The state trajectory - time steps 1 and 2

Download: Full-size image PowerPoint slide

Figure 4. The state trajectory - 50 time steps

Download: Full-size image PowerPoint slide

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 HamiltonJacobi-Bellman Equations, Systems and Control: Foundations and Applications, Birkhäuser, Boston, 1997. doi: 10.1007/978-0-8176-4755-1.
[5]	D. Bertsekas, Dynamic Programming and Optimal Control, Athena Scientific, Belmont, MA, 2017.
[6]	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.
[7]	P. Billingsley, Convergence of Probability Measures, John Wiley & Sons, New York, 1968.
[8]	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.
[9]	V. S. Borkar, A convex analytic approach to Markov decision processes, Probability Theory and Related Fields, 78 (1988), 583-602. doi: 10.1007/BF00353877.
[10]	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.
[11]	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.
[12]	N. Dunford and J. T. Schwartz, Linear Operators, Part I, General Theory, Wiley & Sons, Inc., New York, 1988.
[13]	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.
[14]	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.
[15]	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.
[16]	V. Gaitsgory, A. Parkinson and I. Shvartsman, Linear programming formulation of a discrete time infinite horizon optimal control problem with time discounting criterion, Proceedings of 55th IEEE Conference on Decision and Control (CDC), 2016, Las Vegas, USA.
[17]	V. Gaitsgory, A. Parkinson and I. Shvartsman, Linear programming formulations of deterministic infinite horizon optimal control problems in discrete time, Discrete and Continuous Dynamical Systems, Series B, 22 (2017), 3821-3838. doi: 10.3934/dcdsb.2017192.
[18]	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.
[19]	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.
[20]	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.
[21]	V. Gaitsgory, S. Rossomakhine and N. Thatcher, Approximate solution of the HJB inequality related to the infinite horizon optimal control problem with discounting, Dynamics of Continuous, Discrete and Impulsive Systems Series B: Applications and Algorithms, 19 (2012), 65-92.
[22]	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.
[23]	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.
[24]	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.
[25]	D. Hernandez-Hernandez, O. Hernandez-Lerma and M. Taksar, The linear programming approach to deterministic optimal control problems, Appl. Math., 24 (1996), 17-33. doi: 10.4064/am-24-1-17-33.
[26]	O. Hernandez-Lerma and J. B. Lasserre, The linear Programmimg Approach, in the volume Handbook of Markov Decision Processes: Methods and Applications, Edited by E. A. Feinberg and A. Shwartz, Springer, 2012.
[27]	A. Kamoutsi, T. Sutter, P. M. Esfahani and J. Lygeros, On Infinite Linear Programming and the Moment Approach to Deterministic Infinite Horizon Discounted Optimal Control Problems, IEEE Control System Letters, 1 (2017), 134-139. doi: 10.1109/LCSYS.2017.2710234.
[28]	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.
[29]	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.
[30]	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.
[31]	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.
[32]	J. E. Rubio, Control and Optimization. The Linear Treatment of Nonlinear Problems, Manchester University Press, Manchester, 1986.
[33]	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.
[34]	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.
[35]	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.
[36]	R. Vinter, Convex duality and nonlinear optimal control, SIAM J. Control and Optim., 31 (1993), 518-538. doi: 10.1137/0331024.
[37]	A. Zaslavski, Stability of the Turnpike Phenomenon in Discrete-Time Optimal Control Problems, Springer, (2014). doi: 10.1007/978-3-319-08034-5.
[38]	A. Zaslavski, Turnpike Properties in the Calculus of Variations and Optimal Control, Springer, New York, 2006.
[39]	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.