• Previous Article
    Limit cycles of discontinuous piecewise quadratic and cubic polynomial perturbations of a linear center
  • DCDS-B Home
  • This Issue
  • Next Article
    Pollution control for switching diffusion models: Approximation methods and numerical results
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

* Corresponding author

Received  September 2017 Revised  January 2018 Published  August 2018

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.

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 & Continuous Dynamical Systems - B, 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. BuckdahnD. 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. FinlayV. 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. GaitsgoryA. 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. GaitsgoryS. 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-HernandezO. 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. KamoutsiT. SutterP. 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. LasserreD. HenrionC. 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. BuckdahnD. 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. FinlayV. 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. GaitsgoryA. 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. GaitsgoryS. 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-HernandezO. 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. KamoutsiT. SutterP. 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. LasserreD. HenrionC. 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 1.  The state trajectory - 50 time steps
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 & 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 & Continuous Dynamical Systems - B, 2001, 1 (4) : 443-462. doi: 10.3934/dcdsb.2001.1.443

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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 & Management Optimization, 2010, 6 (1) : 15-28. doi: 10.3934/jimo.2010.6.15

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

Anthony M. Bloch, Peter E. Crouch, Nikolaj Nordkvist. Continuous and discrete embedded optimal control problems and their application to the analysis of Clebsch optimal control problems and mechanical systems. Journal of Geometric Mechanics, 2013, 5 (1) : 1-38. doi: 10.3934/jgm.2013.5.1

2017 Impact Factor: 0.972

Metrics

  • PDF downloads (13)
  • HTML views (150)
  • Cited by (0)

[Back to Top]