# American Institute of Mathematical Sciences

• Previous Article
Necessary conditions for a weak minimum in optimal control problems with integral equations on a variable time interval
• DCDS Home
• This Issue
• Next Article
A semi-Lagrangian scheme for a degenerate second order mean field game system
September  2015, 35(9): 4293-4322. doi: 10.3934/dcds.2015.35.4293

## Higher order discrete controllability and the approximation of the minimum time function

 1 Università di Padova, Dipartimento di Matematica, via Trieste 63, 35121 Padova, Italy

Received  April 2014 Revised  October 2014 Published  April 2015

We give sufficient conditions to reach a target for a suitable discretization of a control affine nonlinear dynamics. Such conditions involve higher order Lie brackets of the vector fields driving the state and so the discretization method needs to be of a suitably high order as well. As a result, the discrete minimal time function is bounded by a fractional power of the distance to the target of the initial point. This allows to use methods based on Hamilton-Jacobi theory to prove the convergence of the solution of a fully discrete scheme to the (true) minimum time function, together with error estimates. Finally, we design an approximate suboptimal discrete feedback and provide an error estimate for the time to reach the target through the discrete dynamics generated by this feedback. Our results make use of ideas appearing for the first time in [3] and now extensively described in [12]. Numerical examples are presented.
Citation: Giovanni Colombo, Thuy T. T. Le. Higher order discrete controllability and the approximation of the minimum time function. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4293-4322. doi: 10.3934/dcds.2015.35.4293
##### References:
 [1] M. Bardi, A boundary value problem for the minimum-time function, SIAM J. Control Optim., 27 (1989), 776-785. doi: 10.1137/0327041. [2] M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Birkhäuser, Boston, 1997. doi: 10.1007/978-0-8176-4755-1. [3] M. Bardi and M. Falcone, An approximation scheme for the minimum time function, SIAM J. Control Optim., 28 (1990), 950-965. doi: 10.1137/0328053. [4] M. Bardi and M. Falcone, Discrete approximation of the minimal time function for systems with regular optimal trajectories, Analysis and optimization of systems (Antibes, 1990), Lecture Notes in Control and Inform. Sci., Springer, Berlin, 144 (1990), 103-112. doi: 10.1007/BFb0120033. [5] G. Barles and B. Perthame, Discontinuous solutions of deterministic optimal stopping time problems, RAIRO Modél. Math. Anal. Numér., 21 (1987), 557-579. [6] P. Cannarsa and C. Sinestrari, Semiconcave Functions, Hamilton-Jacobi Equations, and Optimal Control, Birkhäuser, 2004. [7] F. Clarke, Discontinuous Feedback and Nonlinear Systems, Proc. IFAC Conf. Nonlinear Control (NOLCOS), Bologna, (2010), 1-29. [8] F. H. Clarke, Yu. S. Ledyaev, R. J. Stern and P. R. Wolenski, Nonsmooth Analysis and Control Theory, Springer, New York, 1998. [9] M. Falcone, Numerical solution of Dynamic programming equations, Appendix A in the volume M. Bardi and I. Capuzzo Dolcetta, Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations, Birkhäuser, Boston, 1997. [10] M. Falcone, Numerical methods for differential games based on partial differential equations, Int. Game Theory Rev., 8 (2006), 231-272. doi: 10.1142/S0219198906000886. [11] M. Falcone and R. Ferretti, Discrete time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations, Numer. Math., 67 (1994), 315-344. doi: 10.1007/s002110050031. [12] M. Falcone and R. Ferretti, Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations, SIAM, 2014. doi: 10.1137/1.9781611973051. [13] H. Federer, Curvature measures, Trans. Amer. Math. Soc., 93 (1959), 418-491. doi: 10.1090/S0002-9947-1959-0110078-1. [14] R. Ferretti, High-Order Approximations of Linear Control Systems via Runge-Kutta Schemes, Computing, 58 (1997), 351-364. doi: 10.1007/BF02684347. [15] L. Grüne and P. E. Kloeden, Higher order numerical schemes for affinely controlled nonlinear systems, Numer. Math., 89 (2001), 669-690. doi: 10.1007/s002110000279. [16] E. Hairer, S. P. Nørsett and G. Wanner, Solving Ordinary Differential Equations I, Springer, 1993. [17] A. Marigonda, Second order conditions for the controllability of nonlinear systems with drift, Commun. Pur. Appl. Anal., 5 (2006), 861-885. doi: 10.3934/cpaa.2006.5.861. [18] A. Marigonda and S. Rigo, Controllability of some nonlinear systems with drift via generalized curvature properties, SIAM J. Control, 53 (2014), 434-474. doi: 10.1137/130920691. [19] C. Nour, R. J. Stern and J. Takche , Proximal smoothness and the exterior sphere condition, J. Convex Anal., 16 (2009), 501-514. [20] B. Piccoli and H. Sussmann, Regular synthesis and sufficiency conditions for optimality, SIAM J. Control Optim., 39 (2000), 359-410. doi: 10.1137/S0363012999322031. [21] P. Soravia, Estimates of convergence of fully discrete schemes for the Isaacs equation of pursuit-evasion differential games via maximum principle, SIAM J. Control Optim., 36 (1998), 1-11. doi: 10.1137/S0363012995291865. [22] M. Valadier, Quelques problèmes d'entraînement unilateral en dimension finie. (French) [Some problems of unilateral dragging in finite dimensions] Sém. Anal. Convexe, 18 (Montpellier, 1988), Exp. No. 8, 21 pp., Univ. Sci. Tech. Languedoc.

show all references

##### References:
 [1] M. Bardi, A boundary value problem for the minimum-time function, SIAM J. Control Optim., 27 (1989), 776-785. doi: 10.1137/0327041. [2] M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Birkhäuser, Boston, 1997. doi: 10.1007/978-0-8176-4755-1. [3] M. Bardi and M. Falcone, An approximation scheme for the minimum time function, SIAM J. Control Optim., 28 (1990), 950-965. doi: 10.1137/0328053. [4] M. Bardi and M. Falcone, Discrete approximation of the minimal time function for systems with regular optimal trajectories, Analysis and optimization of systems (Antibes, 1990), Lecture Notes in Control and Inform. Sci., Springer, Berlin, 144 (1990), 103-112. doi: 10.1007/BFb0120033. [5] G. Barles and B. Perthame, Discontinuous solutions of deterministic optimal stopping time problems, RAIRO Modél. Math. Anal. Numér., 21 (1987), 557-579. [6] P. Cannarsa and C. Sinestrari, Semiconcave Functions, Hamilton-Jacobi Equations, and Optimal Control, Birkhäuser, 2004. [7] F. Clarke, Discontinuous Feedback and Nonlinear Systems, Proc. IFAC Conf. Nonlinear Control (NOLCOS), Bologna, (2010), 1-29. [8] F. H. Clarke, Yu. S. Ledyaev, R. J. Stern and P. R. Wolenski, Nonsmooth Analysis and Control Theory, Springer, New York, 1998. [9] M. Falcone, Numerical solution of Dynamic programming equations, Appendix A in the volume M. Bardi and I. Capuzzo Dolcetta, Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations, Birkhäuser, Boston, 1997. [10] M. Falcone, Numerical methods for differential games based on partial differential equations, Int. Game Theory Rev., 8 (2006), 231-272. doi: 10.1142/S0219198906000886. [11] M. Falcone and R. Ferretti, Discrete time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations, Numer. Math., 67 (1994), 315-344. doi: 10.1007/s002110050031. [12] M. Falcone and R. Ferretti, Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations, SIAM, 2014. doi: 10.1137/1.9781611973051. [13] H. Federer, Curvature measures, Trans. Amer. Math. Soc., 93 (1959), 418-491. doi: 10.1090/S0002-9947-1959-0110078-1. [14] R. Ferretti, High-Order Approximations of Linear Control Systems via Runge-Kutta Schemes, Computing, 58 (1997), 351-364. doi: 10.1007/BF02684347. [15] L. Grüne and P. E. Kloeden, Higher order numerical schemes for affinely controlled nonlinear systems, Numer. Math., 89 (2001), 669-690. doi: 10.1007/s002110000279. [16] E. Hairer, S. P. Nørsett and G. Wanner, Solving Ordinary Differential Equations I, Springer, 1993. [17] A. Marigonda, Second order conditions for the controllability of nonlinear systems with drift, Commun. Pur. Appl. Anal., 5 (2006), 861-885. doi: 10.3934/cpaa.2006.5.861. [18] A. Marigonda and S. Rigo, Controllability of some nonlinear systems with drift via generalized curvature properties, SIAM J. Control, 53 (2014), 434-474. doi: 10.1137/130920691. [19] C. Nour, R. J. Stern and J. Takche , Proximal smoothness and the exterior sphere condition, J. Convex Anal., 16 (2009), 501-514. [20] B. Piccoli and H. Sussmann, Regular synthesis and sufficiency conditions for optimality, SIAM J. Control Optim., 39 (2000), 359-410. doi: 10.1137/S0363012999322031. [21] P. Soravia, Estimates of convergence of fully discrete schemes for the Isaacs equation of pursuit-evasion differential games via maximum principle, SIAM J. Control Optim., 36 (1998), 1-11. doi: 10.1137/S0363012995291865. [22] M. Valadier, Quelques problèmes d'entraînement unilateral en dimension finie. (French) [Some problems of unilateral dragging in finite dimensions] Sém. Anal. Convexe, 18 (Montpellier, 1988), Exp. No. 8, 21 pp., Univ. Sci. Tech. Languedoc.
 [1] Robert Baier, Thuy T. T. Le. Construction of the minimum time function for linear systems via higher-order set-valued methods. Mathematical Control and Related Fields, 2019, 9 (2) : 223-255. doi: 10.3934/mcrf.2019012 [2] Eduardo Martínez. Higher-order variational calculus on Lie algebroids. Journal of Geometric Mechanics, 2015, 7 (1) : 81-108. doi: 10.3934/jgm.2015.7.81 [3] Rui L. Fernandes, Yuxuan Zhang. Local and global integrability of Lie brackets. Journal of Geometric Mechanics, 2021, 13 (3) : 355-384. doi: 10.3934/jgm.2021024 [4] Weidong Zhao, Jinlei Wang, Shige Peng. Error estimates of the $\theta$-scheme for backward stochastic differential equations. Discrete and Continuous Dynamical Systems - B, 2009, 12 (4) : 905-924. doi: 10.3934/dcdsb.2009.12.905 [5] Leonardo Colombo, David Martín de Diego. Higher-order variational problems on lie groups and optimal control applications. Journal of Geometric Mechanics, 2014, 6 (4) : 451-478. doi: 10.3934/jgm.2014.6.451 [6] Maike Schulte, Anton Arnold. Discrete transparent boundary conditions for the Schrodinger equation -- a compact higher order scheme. Kinetic and Related Models, 2008, 1 (1) : 101-125. doi: 10.3934/krm.2008.1.101 [7] Johannes Huebschmann. On the history of Lie brackets, crossed modules, and Lie-Rinehart algebras. Journal of Geometric Mechanics, 2021, 13 (3) : 385-402. doi: 10.3934/jgm.2021009 [8] Xiaojie Wang. Weak error estimates of the exponential Euler scheme for semi-linear SPDEs without Malliavin calculus. Discrete and Continuous Dynamical Systems, 2016, 36 (1) : 481-497. doi: 10.3934/dcds.2016.36.481 [9] Anouar El Harrak, Hatim Tayeq, Amal Bergam. A posteriori error estimates for a finite volume scheme applied to a nonlinear reaction-diffusion equation in population dynamics. Discrete and Continuous Dynamical Systems - S, 2021, 14 (7) : 2183-2197. doi: 10.3934/dcdss.2021062 [10] Fasma Diele, Angela Martiradonna, Catalin Trenchea. Stability and errors estimates of a second-order IMSP scheme. Discrete and Continuous Dynamical Systems - S, 2022  doi: 10.3934/dcdss.2022076 [11] Giulia Cavagnari, Antonio Marigonda. Measure-theoretic Lie brackets for nonsmooth vector fields. Discrete and Continuous Dynamical Systems - S, 2018, 11 (5) : 845-864. doi: 10.3934/dcdss.2018052 [12] Mohamed Assellaou, Olivier Bokanowski, Hasnaa Zidani. Error estimates for second order Hamilton-Jacobi-Bellman equations. Approximation of probabilistic reachable sets. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 3933-3964. doi: 10.3934/dcds.2015.35.3933 [13] Liupeng Wang, Yunqing Huang. Error estimates for second-order SAV finite element method to phase field crystal model. Electronic Research Archive, 2021, 29 (1) : 1735-1752. doi: 10.3934/era.2020089 [14] Marina Ghisi, Massimo Gobbino. Hyperbolic--parabolic singular perturbation for mildly degenerate Kirchhoff equations: Global-in-time error estimates. Communications on Pure and Applied Analysis, 2009, 8 (4) : 1313-1332. doi: 10.3934/cpaa.2009.8.1313 [15] Konstantinos Chrysafinos. Error estimates for time-discretizations for the velocity tracking problem for Navier-Stokes flows by penalty methods. Discrete and Continuous Dynamical Systems - B, 2006, 6 (5) : 1077-1096. doi: 10.3934/dcdsb.2006.6.1077 [16] Svetlana Matculevich, Pekka Neittaanmäki, Sergey Repin. A posteriori error estimates for time-dependent reaction-diffusion problems based on the Payne--Weinberger inequality. Discrete and Continuous Dynamical Systems, 2015, 35 (6) : 2659-2677. doi: 10.3934/dcds.2015.35.2659 [17] Denis R. Akhmetov, Renato Spigler. $L^1$-estimates for the higher-order derivatives of solutions to parabolic equations subject to initial values of bounded total variation. Communications on Pure and Applied Analysis, 2007, 6 (4) : 1051-1074. doi: 10.3934/cpaa.2007.6.1051 [18] Giovanni Colombo, Khai T. Nguyen. On the minimum time function around the origin. Mathematical Control and Related Fields, 2013, 3 (1) : 51-82. doi: 10.3934/mcrf.2013.3.51 [19] E. Fossas, J. M. Olm. Galerkin method and approximate tracking in a non-minimum phase bilinear system. Discrete and Continuous Dynamical Systems - B, 2007, 7 (1) : 53-76. doi: 10.3934/dcdsb.2007.7.53 [20] Marita Holtmannspötter, Arnd Rösch, Boris Vexler. A priori error estimates for the space-time finite element discretization of an optimal control problem governed by a coupled linear PDE-ODE system. Mathematical Control and Related Fields, 2021, 11 (3) : 601-624. doi: 10.3934/mcrf.2021014

2021 Impact Factor: 1.588