Advanced Search
Article Contents
Article Contents

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

  • * Corresponding author

    * Corresponding author
Abstract Full Text(HTML) Figure(4) Related Papers Cited by
  • 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.

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


    \begin{equation} \\ \end{equation}
  • 加载中
  • 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] 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. AshMeasure, 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. BillingsleyConvergence 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. SchwartzLinear 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. RubioControl 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. ZaslavskiTurnpike 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.
  • 加载中



Article Metrics

HTML views(981) PDF downloads(237) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint