• Previous Article
    Speculative behavior and chaotic asset price dynamics: On the emergence of a bandcount accretion bifurcation structure
  • DCDS-B Home
  • This Issue
  • Next Article
    Asymptotic stability of traveling fronts to a chemotaxis model with nonlinear diffusion
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 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 & Continuous Dynamical Systems - B, 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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). Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9] R. M. Dudley, Real Analysis and Probability, Cambidge University Press, 2002.  doi: 10.1017/CBO9780511755347.  Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[22]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[28] J. E. Rubio, Control and Optimization. The Linear Treatment of Nonlinear Problems, Manchester University Press, Manchester, 1986.   Google Scholar
[29]

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

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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). Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[9] R. M. Dudley, Real Analysis and Probability, Cambidge University Press, 2002.  doi: 10.1017/CBO9780511755347.  Google Scholar
[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[22]

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

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[28] J. E. Rubio, Control and Optimization. The Linear Treatment of Nonlinear Problems, Manchester University Press, Manchester, 1986.   Google Scholar
[29]

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

[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.  Google Scholar

[1]

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

[2]

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

[3]

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, 2019, 24 (4) : 1743-1767. doi: 10.3934/dcdsb.2018235

[4]

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

[5]

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

[6]

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

[7]

Evelyn Herberg, Michael Hinze, Henrik Schumacher. Maximal discrete sparsity in parabolic optimal control with measures. Mathematical Control & Related Fields, 2020, 10 (4) : 735-759. doi: 10.3934/mcrf.2020018

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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 & Management Optimization, 2020, 16 (2) : 965-990. doi: 10.3934/jimo.2018188

[15]

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 & Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009

[16]

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 & Management Optimization, 2020  doi: 10.3934/jimo.2020108

[17]

Xinmin Yang, Xiaoqi Yang, Kok Lay Teo. Higher-order symmetric duality in multiobjective programming with invexity. Journal of Industrial & Management Optimization, 2008, 4 (2) : 385-391. doi: 10.3934/jimo.2008.4.385

[18]

Xinmin Yang, Xiaoqi Yang. A note on mixed type converse duality in multiobjective programming problems. Journal of Industrial & Management Optimization, 2010, 6 (3) : 497-500. doi: 10.3934/jimo.2010.6.497

[19]

Deepak Singh, Bilal Ahmad Dar, Do Sang Kim. Sufficiency and duality in non-smooth interval valued programming problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 647-665. doi: 10.3934/jimo.2018063

[20]

Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1873-1884. doi: 10.3934/jimo.2019033

2019 Impact Factor: 1.27

Metrics

  • PDF downloads (22)
  • HTML views (93)
  • Cited by (0)

Other articles
by authors

[Back to Top]