Dynamic programming using radial basis functions

Oliver Junge; Alex Schreiber

doi:10.3934/dcds.2015.35.4439

Article Contents

2015, Volume 35, Issue 9: 4439-4453. Doi: 10.3934/dcds.2015.35.4439

This issue Previous Article Stratified discontinuous differential equations and sufficient conditions for robustness Next Article Optimal control of differential inclusions on manifolds

Dynamic programming using radial basis functions

Oliver Junge^1, and
Alex Schreiber^1,

1.
Center for Mathematics, Technische Universität München, 85747 Garching bei München

Received: May 2014

Revised: October 2014

Published: May 2017

Abstract / Introduction Related Papers Cited by

Abstract

We propose a discretization of the optimality principle in dynamic programming based on radial basis functions and Shepard's moving least squares approximation method. We prove convergence of the value iteration scheme, derive a statement about the stability region of the closed loop system using the corresponding approximate optimal feedback law and present several numerical experiments.

Keywords:

Mathematics Subject Classification: Primary: 49L20, 49M25; Secondary: 93D15.

Citation:

Related Papers

Cited by

References

[1]	, href="http://www-m3.ma.tum.de/Allgemeines/JuSch_DP_RBF" target="_blank">http://www-m3.ma.tum.de/Allgemeines/JuSch_DP_RBF .
[2]	H. Alwardi, S. Wang, L. Jennings and S. Richardson, An adaptive least-squares collocation radial basis function method for the HJB equation, J. Glob. Opt., 52 (2012), 305-322.doi: 10.1007/s10898-011-9667-4.
[3]	M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Birkhäuser, Boston, Boston, MA, 1997.doi: 10.1007/978-0-8176-4755-1.
[4]	R. Bellman, Dynamic Programming, Princeton University Press, Princeton, NJ, 1957.
[5]	D. Bertsekas, Dynamic Programming, Prentice Hall Inc., Englewood Cliffs, NJ, 1987.
[6]	I. Capuzzo-Dolcetta, On a discrete approximation of the Hamilton-Jacobi equation of dynamic programming, Appl. Math. Optim., 10 (1983), 367-377.doi: 10.1007/BF01448394.
[7]	I. Capuzzo-Dolcetta and M. Falcone, Discrete dynamic programming and viscosity solutions of the Bellman equation, Ann. Inst. H. Poincaré Anal. Non Linéaire, 6 (1989), 161-183.
[8]	E. Carlini, M. Falcone and R. Ferretti, An efficient algorithm for Hamilton-Jacobi equations in high dimension, Comput. Vis. Sci., 7 (2004), 15-29.doi: 10.1007/s00791-004-0124-5.
[9]	T. Cecil, J. Qian and S. Osher, Numerical methods for high dimensional Hamilton-Jacobi equations using radial basis functions, J. Comp. Phys., 196 (2004), 327-347.doi: 10.1016/j.jcp.2003.11.010.
[10]	M. Falcone, A numerical approach to the infinite horizon problem of deterministic control theory, Appl. Math. Optim., 15 (1987), 1-13.doi: 10.1007/BF01442644.
[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, High-order approximations for viscosity solutions of Hamilton-Jacobi-Bellman equations, in Nonlinear variational problems and partial differential equations (Isola d'Elba, 1990), vol. 320 of Pitman Res. Notes Math. Ser., Longman Sci. Tech., Harlow, (1995), 197-209.
[13]	G. Fasshauer, Meshfree Approximation Methods with Matlab, World Scientific, 2007.doi: 10.1142/6437.
[14]	P. Giesl, On the determination of the basin of attraction of discrete dynamical systems, J. Diff. Eq. Appl., 13 (2007), 523-546.doi: 10.1080/10236190601135209.
[15]	P. Giesl, Construction of a local and global Lyapunov function for discrete dynamical systems using radial basis functions, Journal of Approximation Theory, 153 (2008), 184-211.doi: 10.1016/j.jat.2008.01.007.
[16]	E. Gottzein, R. Meisinger and L. Miller, Anwendung des "Magnetischen Rades" in Hochgeschwindigkeitsmagnetschwebebahnen, ZEV-Glasers Annalen, 103.
[17]	L. Grüne, An adaptive grid scheme for the discrete Hamilton-Jacobi-Bellman equation, Numer. Math., 75 (1997), 319-337.doi: 10.1007/s002110050241.
[18]	L. Grüne, Error estimation and adaptive discretization for the discrete stochastic Hamilton-Jacobi-Bellman equation, Numer. Math., 99 (2004), 85-112.doi: 10.1007/s00211-004-0555-4.
[19]	L. Grüne and O. Junge, A set oriented approach to optimal feedback stabilization, Syst. Cont. Lett., 54 (2005), 169-180.doi: 10.1016/j.sysconle.2004.08.005.
[20]	C. Huang, S. Wang, C. Chen and Z. Li, A radial basis collocation method for Hamilton-Jacobi-Bellman equations, Automatica, 42 (2006), 2201-2207.doi: 10.1016/j.automatica.2006.07.013.
[21]	O. Junge and H. M. Osinga, A set oriented approach to global optimal control, ESAIM Control Optim. Calc. Var., 10 (2004), 259-270.doi: 10.1051/cocv:2004006.
[22]	C.-Y. Kao, S. Osher and Y.-H. Tsai, Fast sweeping methods for static Hamilton-Jacobi equations, SIAM J. Numer. Anal., 42 (2005), 2612-2632.doi: 10.1137/S0036142902419600.
[23]	S. N. Kružkov, Generalized solutions of Hamilton-Jacobi equations of eikonal type. I, Mat. Sb. (N.S.), 98 (1975), 450-493, 496.
[24]	B. Lincoln and A. Rantzer, Relaxing dynamic programming, IEEE Trans. Auto. Ctrl., 51 (2006), 1249-1260.doi: 10.1109/TAC.2006.878720.
[25]	W. McEneaney, Max-plus Methods for Nonlinear Control and Estimation, Birkhäuser, Boston, 2006.
[26]	R. Schaback and H. Wendland, Adaptive greedy techniques for approximate solution of large rbf systems, Numerical Algorithms, 24 (2000), 239-254.doi: 10.1023/A:1019105612985.
[27]	R. Schaback and H. Wendland, Numerical Techniques Based on Radial Basis Functions, Technical report, DTIC Document, 2000.
[28]	J. A. Sethian and A. Vladimirsky, Ordered upwind methods for static Hamilton-Jacobi equations: theory and algorithms, SIAM J. Numer. Anal., 41 (2003), 325-363.doi: 10.1137/S0036142901392742.
[29]	D. Shepard, A two-dimensional interpolation function for irregularly-spaced data, in Proc. 23rd ACM, ACM, (1968), 517-524.doi: 10.1145/800186.810616.
[30]	H. Wendland, Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree, Adv. Comp. Math., 4 (1995), 389-396.doi: 10.1007/BF02123482.