Figure 1.
The state trajectory - 50 time steps
-
Previous Article
Limit cycles of discontinuous piecewise quadratic and cubic polynomial perturbations of a linear center
- DCDS-B Home
- This Issue
-
Next Article
Synchronization of first-order autonomous oscillators on Riemannian manifolds
April
2019, 24(4): 1743-1767.
doi: 10.3934/dcdsb.2018235
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 |
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:
Optimal control,
discrete systems,
infinite horizon,
occupational measures,
linear programming,
duality,
numerical methods.
Mathematics Subject Classification:
Primary: 49N15, 49M29, 93C55.
Citation:
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 and Continuous Dynamical Systems - B,
2019, 24
(4)
: 1743-1767.
doi: 10.3934/dcdsb.2018235
![]()
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. |
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. |
| [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. |
Figure 2.
The state trajectory - time step 1
Figure 3.
The state trajectory - time steps 1 and 2
Figure 4.
The state trajectory - 50 time steps
| [1] |
Vladimir Gaitsgory, Alex Parkinson, Ilya Shvartsman. Linear programming formulations of deterministic infinite horizon optimal control problems in discrete time. Discrete and Continuous Dynamical Systems - B, 2017, 22 (10) : 3821-3838. doi: 10.3934/dcdsb.2017192 |
| [2] |
Fabio Bagagiolo. An infinite horizon optimal control problem for some switching systems. Discrete and Continuous Dynamical Systems - B, 2001, 1 (4) : 443-462. doi: 10.3934/dcdsb.2001.1.443 |
| [3] |
Jingang Zhao, Chi Zhang. Finite-horizon optimal control of discrete-time linear systems with completely unknown dynamics using Q-learning. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1471-1483. doi: 10.3934/jimo.2020030 |
| [4] |
Jianhui Huang, Xun Li, Jiongmin Yong. A linear-quadratic optimal control problem for mean-field stochastic differential equations in infinite horizon. Mathematical Control and 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 and Optimization, 2018, 8 (2) : 211-235. doi: 10.3934/naco.2018013 |
| [6] |
Vincenzo Basco, Piermarco Cannarsa, Hélène Frankowska. Necessary conditions for infinite horizon optimal control problems with state constraints. Mathematical Control and Related Fields, 2018, 8 (3&4) : 535-555. doi: 10.3934/mcrf.2018022 |
| [7] |
Naïla Hayek. Infinite-horizon multiobjective optimal control problems for bounded processes. Discrete and Continuous Dynamical Systems - S, 2018, 11 (6) : 1121-1141. doi: 10.3934/dcdss.2018064 |
| [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] |
Evelyn Herberg, Michael Hinze, Henrik Schumacher. Maximal discrete sparsity in parabolic optimal control with measures. Mathematical Control and Related Fields, 2020, 10 (4) : 735-759. doi: 10.3934/mcrf.2020018 |
| [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 and 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 and Optimization, 2013, 3 (3) : 389-406. doi: 10.3934/naco.2013.3.389 |
| [12] |
Rein Luus. Optimal control of oscillatory systems by iterative dynamic programming. Journal of Industrial and Management Optimization, 2008, 4 (1) : 1-15. doi: 10.3934/jimo.2008.4.1 |
| [13] |
Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003 |
| [14] |
Yadong Shu, Bo Li. Linear-quadratic optimal control for discrete-time stochastic descriptor systems. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1583-1602. doi: 10.3934/jimo.2021034 |
| [15] |
Z. Foroozandeh, Maria do rosário de Pinho, M. Shamsi. On numerical methods for singular optimal control problems: An application to an AUV problem. Discrete and Continuous Dynamical Systems - B, 2019, 24 (5) : 2219-2235. doi: 10.3934/dcdsb.2019092 |
| [16] |
Martin Benning, Elena Celledoni, Matthias J. Ehrhardt, Brynjulf Owren, Carola-Bibiane Schönlieb. Deep learning as optimal control problems: Models and numerical methods. Journal of Computational Dynamics, 2019, 6 (2) : 171-198. doi: 10.3934/jcd.2019009 |
| [17] |
Xiaowei Pang, Haiming Song, Xiaoshen Wang, Jiachuan Zhang. Efficient numerical methods for elliptic optimal control problems with random coefficient. Electronic Research Archive, 2020, 28 (2) : 1001-1022. doi: 10.3934/era.2020053 |
| [18] |
Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial and Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 |
| [19] |
Satoshi Ito, Soon-Yi Wu, Ting-Jang Shiu, Kok Lay Teo. A numerical approach to infinite-dimensional linear programming in $L_1$ spaces. Journal of Industrial and Management Optimization, 2010, 6 (1) : 15-28. doi: 10.3934/jimo.2010.6.15 |
| [20] |
Qiying Hu, Wuyi Yue. Optimal control for resource allocation in discrete event systems. Journal of Industrial and Management Optimization, 2006, 2 (1) : 63-80. doi: 10.3934/jimo.2006.2.63 |
2021 Impact Factor: 1.497
Tools
Metrics
Other articles
by authors
[Back to Top]