March  2022, 27(3): 1591-1610. doi: 10.3934/dcdsb.2021102

Linear programming estimates for Cesàro and Abel limits of optimal values in optimal control problems

1. 

Department of Mathematics, Macquarie University, Macquarie Park, NSW 2113, Australia

2. 

Department of Mathematic and Computer Science, Penn State Harrisburg, Middletown, PA 17057, USA

* Corresponding author

Received  October 2020 Published  March 2022 Early access  March 2021

We consider infinite horizon optimal control problems with time averaging and time discounting criteria and give estimates for the Cesàro and Abel limits of their optimal values in the case when they depend on the initial conditions. We establish that these limits are bounded from above by the optimal value of a certain infinite dimensional (ID) linear programming (LP) problem and that they are bounded from below by the optimal value of the corresponding dual problem. (These estimates imply, in particular, that the Cesàro and Abel limits exist and are equal to each other if there is no duality gap). In addition, we obtain IDLP-based optimality conditions for the long run average optimal control problem, and we illustrate these conditions by an example.

Citation: Vladimir Gaitsgory, Ilya Shvartsman. Linear programming estimates for Cesàro and Abel limits of optimal values in optimal control problems. Discrete and Continuous Dynamical Systems - B, 2022, 27 (3) : 1591-1610. doi: 10.3934/dcdsb.2021102
References:
[1]

M. Arisawa and P.-L. Lions, On ergodic stochastic control, Commun. in Partial Differential Equations, 23 (1998), 2187-2217.  doi: 10.1080/03605309808821413.

[2]

M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Birkhauser, Boston, 1997. doi: 10.1007/978-0-8176-4755-1.

[3]

V. S. Borkar and V. Gaitsgory, Linear programming formulation of long run average optimal control problem, J. of Optimization Theory and Applications, 181 (2019), 101-125.  doi: 10.1007/s10957-018-1432-0.

[4]

V. S. BorkarV. Gaitsgory and I. Shvartsman, LP formulations of discrete time long-run average optimal control problems: The non-ergodic case, SIAM Journal on Control and Optimization, 57 (2019), 1783-1817.  doi: 10.1137/18M1229432.

[5]

V. S. Borkar, V. Gaitsgory and I. Shvartsman, On LP formulations of optimal control problems with time averaging and time discounting criteria in non-ergodic case, Proceedings of the 58th IEEE Conference on Decision and Control, (2019).

[6]

R. BuckdahnM. Quincampoix and J. Renault, On representation formulas for long run averaging optimal control problem, Journal of Differential Equations, 259 (2015), 5554-5581.  doi: 10.1016/j.jde.2015.06.039.

[7]

R. BuckdahnD. Goreac and M. Quincampoix, Stochastic optimal control and linear programming approach, Applied Mathematics and Optimization, 63 (2011), 257-276.  doi: 10.1007/s00245-010-9120-y.

[8]

M.-O. Czarnecki and L. Rifford, Approximation and regularization of Lipschitz functions: Convergence of the gradients, Trans. Amer. Math. Soc., 358 (2006), 4467-4520.  doi: 10.1090/S0002-9947-06-04103-1.

[9] R. M. Dudley, Real Analysis and Probability, Cambidge University Press, 2002.  doi: 10.1017/CBO9780511755347.
[10]

V. Gaitsgory, On a representation of the limit occupational measure of a control system with applications to singularly perturbed control systems, SIAM J. Control and Optim., 43 (2004), 325-340.  doi: 10.1137/S0363012903424186.

[11]

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.

[12]

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.

[13]

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.

[14]

V. GaitsgoryA. Parkinson and I. 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, Series B, 24 (2019), 1743-1767.  doi: 10.3934/dcdsb.2018235.

[15]

D. Goreac and O.-S. Serea, Linearization techniques for $L^{\infty} $ - control problems and dynamic programming principles in classical and $L^{\infty} $ control problems, ESAIM: Control, Optimization and Calculus of Variations, 18 (2012), 836-855.  doi: 10.1051/cocv/2011183.

[16]

L. Grüne, Asymptotic controllability and exponential stabilization of nonlinear control systems at singular points, SIAM J. Control Optim., 36 (1998), 1485-1503.  doi: 10.1137/S0363012997315919.

[17]

L. Grüne, On the relation between discounted and average optimal value functions, J. Diff. Equations, 148 (1998), 65-99.  doi: 10.1006/jdeq.1998.3451.

[18]

O. Hernández-Lerma and J. González-Hernandez, Infinite linear programming and multichain Markov control processes in uncountable spaces, SIAM J. Control Optim., 36 (1998), 313-335.  doi: 10.1137/S0363012995292238.

[19]

D. Hernández-HernandezO. Hernández-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.

[20]

A. Hordijk and L. C. M. Kallenberg, Linear programming and Markov decision chains, Management Science, 25 (1979), 352-362.  doi: 10.1287/mnsc.25.4.352.

[21]

A. Hordijk and L. C. M. Kallenberg, Constrained undiscounted stochastic dynamic programming, Mathematics of Operations Research, 9 (1984), 276-289.  doi: 10.1287/moor.9.2.276.

[22]

D. Khlopin, Tauberian theorem for value functions, Dynamic Games and Applications, 8 (2018), 401-422.  doi: 10.1007/s13235-017-0227-5.

[23]

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.

[24]

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.

[25]

M. Oliu-Barton and G. Vigeral, A uniform Tauberian theorem in optimal control, in Annals of International Society of Dynamic Games (eds. P. Cardaliaguet and R. Grossman), Birkhäuser/Springer, New York, 12 (2013), 199–215. doi: 10.1007/978-0-8176-8355-9.

[26]

M. Quincampoix and J. Renault, On existence of a limit value in some non-expansive optimal control problems, SIAM J. on Control and Optimization, 49 (2011), 2118-2132.  doi: 10.1137/090756818.

[27]

M. Quincampoix and O. S. 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. E. Rubio, Control and Optimization. The Linear Treatment of Nonlinear Problems, Manchester University Press, Manchester, 1986. 
[29]

R. Vinter, Convex duality and nonlinear optimal control, SIAM J. Control and Optim., 31 (1993), 518-538.  doi: 10.1137/0331024.

[30]

H. Whitney, Analytic extensions of functions defined in closed sets, Transactions of the American Mathematical Society, 36 (1934), 63-89.  doi: 10.1090/S0002-9947-1934-1501735-3.

show all references

References:
[1]

M. Arisawa and P.-L. Lions, On ergodic stochastic control, Commun. in Partial Differential Equations, 23 (1998), 2187-2217.  doi: 10.1080/03605309808821413.

[2]

M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Birkhauser, Boston, 1997. doi: 10.1007/978-0-8176-4755-1.

[3]

V. S. Borkar and V. Gaitsgory, Linear programming formulation of long run average optimal control problem, J. of Optimization Theory and Applications, 181 (2019), 101-125.  doi: 10.1007/s10957-018-1432-0.

[4]

V. S. BorkarV. Gaitsgory and I. Shvartsman, LP formulations of discrete time long-run average optimal control problems: The non-ergodic case, SIAM Journal on Control and Optimization, 57 (2019), 1783-1817.  doi: 10.1137/18M1229432.

[5]

V. S. Borkar, V. Gaitsgory and I. Shvartsman, On LP formulations of optimal control problems with time averaging and time discounting criteria in non-ergodic case, Proceedings of the 58th IEEE Conference on Decision and Control, (2019).

[6]

R. BuckdahnM. Quincampoix and J. Renault, On representation formulas for long run averaging optimal control problem, Journal of Differential Equations, 259 (2015), 5554-5581.  doi: 10.1016/j.jde.2015.06.039.

[7]

R. BuckdahnD. Goreac and M. Quincampoix, Stochastic optimal control and linear programming approach, Applied Mathematics and Optimization, 63 (2011), 257-276.  doi: 10.1007/s00245-010-9120-y.

[8]

M.-O. Czarnecki and L. Rifford, Approximation and regularization of Lipschitz functions: Convergence of the gradients, Trans. Amer. Math. Soc., 358 (2006), 4467-4520.  doi: 10.1090/S0002-9947-06-04103-1.

[9] R. M. Dudley, Real Analysis and Probability, Cambidge University Press, 2002.  doi: 10.1017/CBO9780511755347.
[10]

V. Gaitsgory, On a representation of the limit occupational measure of a control system with applications to singularly perturbed control systems, SIAM J. Control and Optim., 43 (2004), 325-340.  doi: 10.1137/S0363012903424186.

[11]

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.

[12]

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.

[13]

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.

[14]

V. GaitsgoryA. Parkinson and I. 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, Series B, 24 (2019), 1743-1767.  doi: 10.3934/dcdsb.2018235.

[15]

D. Goreac and O.-S. Serea, Linearization techniques for $L^{\infty} $ - control problems and dynamic programming principles in classical and $L^{\infty} $ control problems, ESAIM: Control, Optimization and Calculus of Variations, 18 (2012), 836-855.  doi: 10.1051/cocv/2011183.

[16]

L. Grüne, Asymptotic controllability and exponential stabilization of nonlinear control systems at singular points, SIAM J. Control Optim., 36 (1998), 1485-1503.  doi: 10.1137/S0363012997315919.

[17]

L. Grüne, On the relation between discounted and average optimal value functions, J. Diff. Equations, 148 (1998), 65-99.  doi: 10.1006/jdeq.1998.3451.

[18]

O. Hernández-Lerma and J. González-Hernandez, Infinite linear programming and multichain Markov control processes in uncountable spaces, SIAM J. Control Optim., 36 (1998), 313-335.  doi: 10.1137/S0363012995292238.

[19]

D. Hernández-HernandezO. Hernández-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.

[20]

A. Hordijk and L. C. M. Kallenberg, Linear programming and Markov decision chains, Management Science, 25 (1979), 352-362.  doi: 10.1287/mnsc.25.4.352.

[21]

A. Hordijk and L. C. M. Kallenberg, Constrained undiscounted stochastic dynamic programming, Mathematics of Operations Research, 9 (1984), 276-289.  doi: 10.1287/moor.9.2.276.

[22]

D. Khlopin, Tauberian theorem for value functions, Dynamic Games and Applications, 8 (2018), 401-422.  doi: 10.1007/s13235-017-0227-5.

[23]

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.

[24]

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.

[25]

M. Oliu-Barton and G. Vigeral, A uniform Tauberian theorem in optimal control, in Annals of International Society of Dynamic Games (eds. P. Cardaliaguet and R. Grossman), Birkhäuser/Springer, New York, 12 (2013), 199–215. doi: 10.1007/978-0-8176-8355-9.

[26]

M. Quincampoix and J. Renault, On existence of a limit value in some non-expansive optimal control problems, SIAM J. on Control and Optimization, 49 (2011), 2118-2132.  doi: 10.1137/090756818.

[27]

M. Quincampoix and O. S. 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. E. Rubio, Control and Optimization. The Linear Treatment of Nonlinear Problems, Manchester University Press, Manchester, 1986. 
[29]

R. Vinter, Convex duality and nonlinear optimal control, SIAM J. Control and Optim., 31 (1993), 518-538.  doi: 10.1137/0331024.

[30]

H. Whitney, Analytic extensions of functions defined in closed sets, Transactions of the American Mathematical Society, 36 (1934), 63-89.  doi: 10.1090/S0002-9947-1934-1501735-3.

[1]

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

[2]

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

[3]

Ferenc Weisz. Cesàro summability and Lebesgue points of higher dimensional Fourier series. Mathematical Foundations of Computing, 2022, 5 (3) : 241-257. doi: 10.3934/mfc.2021033

[4]

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

[5]

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

[6]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial and Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881

[7]

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

[8]

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

[9]

Giulia Cavagnari. Regularity results for a time-optimal control problem in the space of probability measures. Mathematical Control and Related Fields, 2017, 7 (2) : 213-233. doi: 10.3934/mcrf.2017007

[10]

Xinmin Yang. On second order symmetric duality in nondifferentiable multiobjective programming. Journal of Industrial and Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697

[11]

Tone-Yau Huang, Tamaki Tanaka. Optimality and duality for complex multi-objective programming. Numerical Algebra, Control and Optimization, 2022, 12 (1) : 121-134. doi: 10.3934/naco.2021055

[12]

Elimhan N. Mahmudov. Infimal convolution and duality in convex optimal control problems with second order evolution differential inclusions. Evolution Equations and Control Theory, 2021, 10 (1) : 37-59. doi: 10.3934/eect.2020051

[13]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437

[14]

Michael Basin, Pablo Rodriguez-Ramirez. An optimal impulsive control regulator for linear systems. Numerical Algebra, Control and Optimization, 2011, 1 (2) : 275-282. doi: 10.3934/naco.2011.1.275

[15]

Charles Fefferman. Interpolation by linear programming I. Discrete and Continuous Dynamical Systems, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477

[16]

Haibo Jin, Long Hai, Xiaoliang Tang. An optimal maintenance strategy for multi-state systems based on a system linear integral equation and dynamic programming. Journal of Industrial and Management Optimization, 2020, 16 (2) : 965-990. doi: 10.3934/jimo.2018188

[17]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009

[18]

Qingsong Duan, Mengwei Xu, Liwei Zhang, Sainan Zhang. Hadamard directional differentiability of the optimal value of a linear second-order conic programming problem. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3085-3098. doi: 10.3934/jimo.2020108

[19]

Zeya Mi. SRB measures for some diffeomorphisms with dominated splittings as zero noise limits. Discrete and Continuous Dynamical Systems, 2019, 39 (11) : 6441-6465. doi: 10.3934/dcds.2019279

[20]

Kazuki Himoto, Hideaki Matsunaga. The limits of solutions of a linear delay integral equation. Discrete and Continuous Dynamical Systems - B, 2020, 25 (8) : 3033-3048. doi: 10.3934/dcdsb.2020050

2021 Impact Factor: 1.497

Metrics

  • PDF downloads (264)
  • HTML views (394)
  • Cited by (0)

Other articles
by authors

[Back to Top]