September  2015, 35(9): 4439-4453. doi: 10.3934/dcds.2015.35.4439

Dynamic programming using radial basis functions

1. 

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

Received  May 2014 Revised  October 2014 Published  April 2015

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.
Citation: Oliver Junge, Alex Schreiber. Dynamic programming using radial basis functions. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4439-4453. doi: 10.3934/dcds.2015.35.4439
References:
[1]

http://www-m3.ma.tum.de/Allgemeines/JuSch_DP_RBF, ., ().   Google Scholar

[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.  doi: 10.1007/s10898-011-9667-4.  Google Scholar

[3]

M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations,, Birkhäuser, (1997).  doi: 10.1007/978-0-8176-4755-1.  Google Scholar

[4]

R. Bellman, Dynamic Programming,, Princeton University Press, (1957).   Google Scholar

[5]

D. Bertsekas, Dynamic Programming,, Prentice Hall Inc., (1987).   Google Scholar

[6]

I. Capuzzo-Dolcetta, On a discrete approximation of the Hamilton-Jacobi equation of dynamic programming,, Appl. Math. Optim., 10 (1983), 367.  doi: 10.1007/BF01448394.  Google Scholar

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

[8]

E. Carlini, M. Falcone and R. Ferretti, An efficient algorithm for Hamilton-Jacobi equations in high dimension,, Comput. Vis. Sci., 7 (2004), 15.  doi: 10.1007/s00791-004-0124-5.  Google Scholar

[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.  doi: 10.1016/j.jcp.2003.11.010.  Google Scholar

[10]

M. Falcone, A numerical approach to the infinite horizon problem of deterministic control theory,, Appl. Math. Optim., 15 (1987), 1.  doi: 10.1007/BF01442644.  Google Scholar

[11]

M. Falcone and R. Ferretti, Discrete time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations,, Numer. Math., 67 (1994), 315.  doi: 10.1007/s002110050031.  Google Scholar

[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, (1995), 197.   Google Scholar

[13]

G. Fasshauer, Meshfree Approximation Methods with Matlab,, World Scientific, (2007).  doi: 10.1142/6437.  Google Scholar

[14]

P. Giesl, On the determination of the basin of attraction of discrete dynamical systems,, J. Diff. Eq. Appl., 13 (2007), 523.  doi: 10.1080/10236190601135209.  Google Scholar

[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.  doi: 10.1016/j.jat.2008.01.007.  Google Scholar

[16]

E. Gottzein, R. Meisinger and L. Miller, Anwendung des "Magnetischen Rades" in Hochgeschwindigkeitsmagnetschwebebahnen,, ZEV-Glasers Annalen, 103 ().   Google Scholar

[17]

L. Grüne, An adaptive grid scheme for the discrete Hamilton-Jacobi-Bellman equation,, Numer. Math., 75 (1997), 319.  doi: 10.1007/s002110050241.  Google Scholar

[18]

L. Grüne, Error estimation and adaptive discretization for the discrete stochastic Hamilton-Jacobi-Bellman equation,, Numer. Math., 99 (2004), 85.  doi: 10.1007/s00211-004-0555-4.  Google Scholar

[19]

L. Grüne and O. Junge, A set oriented approach to optimal feedback stabilization,, Syst. Cont. Lett., 54 (2005), 169.  doi: 10.1016/j.sysconle.2004.08.005.  Google Scholar

[20]

C. Huang, S. Wang, C. Chen and Z. Li, A radial basis collocation method for Hamilton-Jacobi-Bellman equations,, Automatica, 42 (2006), 2201.  doi: 10.1016/j.automatica.2006.07.013.  Google Scholar

[21]

O. Junge and H. M. Osinga, A set oriented approach to global optimal control,, ESAIM Control Optim. Calc. Var., 10 (2004), 259.  doi: 10.1051/cocv:2004006.  Google Scholar

[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.  doi: 10.1137/S0036142902419600.  Google Scholar

[23]

S. N. Kružkov, Generalized solutions of Hamilton-Jacobi equations of eikonal type. I,, Mat. Sb. (N.S.), 98 (1975), 450.   Google Scholar

[24]

B. Lincoln and A. Rantzer, Relaxing dynamic programming,, IEEE Trans. Auto. Ctrl., 51 (2006), 1249.  doi: 10.1109/TAC.2006.878720.  Google Scholar

[25]

W. McEneaney, Max-plus Methods for Nonlinear Control and Estimation,, Birkhäuser, (2006).   Google Scholar

[26]

R. Schaback and H. Wendland, Adaptive greedy techniques for approximate solution of large rbf systems,, Numerical Algorithms, 24 (2000), 239.  doi: 10.1023/A:1019105612985.  Google Scholar

[27]

R. Schaback and H. Wendland, Numerical Techniques Based on Radial Basis Functions,, Technical report, (2000).   Google Scholar

[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.  doi: 10.1137/S0036142901392742.  Google Scholar

[29]

D. Shepard, A two-dimensional interpolation function for irregularly-spaced data,, in Proc. 23rd ACM, (1968), 517.  doi: 10.1145/800186.810616.  Google Scholar

[30]

H. Wendland, Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree,, Adv. Comp. Math., 4 (1995), 389.  doi: 10.1007/BF02123482.  Google Scholar

show all references

References:
[1]

http://www-m3.ma.tum.de/Allgemeines/JuSch_DP_RBF, ., ().   Google Scholar

[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.  doi: 10.1007/s10898-011-9667-4.  Google Scholar

[3]

M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations,, Birkhäuser, (1997).  doi: 10.1007/978-0-8176-4755-1.  Google Scholar

[4]

R. Bellman, Dynamic Programming,, Princeton University Press, (1957).   Google Scholar

[5]

D. Bertsekas, Dynamic Programming,, Prentice Hall Inc., (1987).   Google Scholar

[6]

I. Capuzzo-Dolcetta, On a discrete approximation of the Hamilton-Jacobi equation of dynamic programming,, Appl. Math. Optim., 10 (1983), 367.  doi: 10.1007/BF01448394.  Google Scholar

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

[8]

E. Carlini, M. Falcone and R. Ferretti, An efficient algorithm for Hamilton-Jacobi equations in high dimension,, Comput. Vis. Sci., 7 (2004), 15.  doi: 10.1007/s00791-004-0124-5.  Google Scholar

[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.  doi: 10.1016/j.jcp.2003.11.010.  Google Scholar

[10]

M. Falcone, A numerical approach to the infinite horizon problem of deterministic control theory,, Appl. Math. Optim., 15 (1987), 1.  doi: 10.1007/BF01442644.  Google Scholar

[11]

M. Falcone and R. Ferretti, Discrete time high-order schemes for viscosity solutions of Hamilton-Jacobi-Bellman equations,, Numer. Math., 67 (1994), 315.  doi: 10.1007/s002110050031.  Google Scholar

[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, (1995), 197.   Google Scholar

[13]

G. Fasshauer, Meshfree Approximation Methods with Matlab,, World Scientific, (2007).  doi: 10.1142/6437.  Google Scholar

[14]

P. Giesl, On the determination of the basin of attraction of discrete dynamical systems,, J. Diff. Eq. Appl., 13 (2007), 523.  doi: 10.1080/10236190601135209.  Google Scholar

[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.  doi: 10.1016/j.jat.2008.01.007.  Google Scholar

[16]

E. Gottzein, R. Meisinger and L. Miller, Anwendung des "Magnetischen Rades" in Hochgeschwindigkeitsmagnetschwebebahnen,, ZEV-Glasers Annalen, 103 ().   Google Scholar

[17]

L. Grüne, An adaptive grid scheme for the discrete Hamilton-Jacobi-Bellman equation,, Numer. Math., 75 (1997), 319.  doi: 10.1007/s002110050241.  Google Scholar

[18]

L. Grüne, Error estimation and adaptive discretization for the discrete stochastic Hamilton-Jacobi-Bellman equation,, Numer. Math., 99 (2004), 85.  doi: 10.1007/s00211-004-0555-4.  Google Scholar

[19]

L. Grüne and O. Junge, A set oriented approach to optimal feedback stabilization,, Syst. Cont. Lett., 54 (2005), 169.  doi: 10.1016/j.sysconle.2004.08.005.  Google Scholar

[20]

C. Huang, S. Wang, C. Chen and Z. Li, A radial basis collocation method for Hamilton-Jacobi-Bellman equations,, Automatica, 42 (2006), 2201.  doi: 10.1016/j.automatica.2006.07.013.  Google Scholar

[21]

O. Junge and H. M. Osinga, A set oriented approach to global optimal control,, ESAIM Control Optim. Calc. Var., 10 (2004), 259.  doi: 10.1051/cocv:2004006.  Google Scholar

[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.  doi: 10.1137/S0036142902419600.  Google Scholar

[23]

S. N. Kružkov, Generalized solutions of Hamilton-Jacobi equations of eikonal type. I,, Mat. Sb. (N.S.), 98 (1975), 450.   Google Scholar

[24]

B. Lincoln and A. Rantzer, Relaxing dynamic programming,, IEEE Trans. Auto. Ctrl., 51 (2006), 1249.  doi: 10.1109/TAC.2006.878720.  Google Scholar

[25]

W. McEneaney, Max-plus Methods for Nonlinear Control and Estimation,, Birkhäuser, (2006).   Google Scholar

[26]

R. Schaback and H. Wendland, Adaptive greedy techniques for approximate solution of large rbf systems,, Numerical Algorithms, 24 (2000), 239.  doi: 10.1023/A:1019105612985.  Google Scholar

[27]

R. Schaback and H. Wendland, Numerical Techniques Based on Radial Basis Functions,, Technical report, (2000).   Google Scholar

[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.  doi: 10.1137/S0036142901392742.  Google Scholar

[29]

D. Shepard, A two-dimensional interpolation function for irregularly-spaced data,, in Proc. 23rd ACM, (1968), 517.  doi: 10.1145/800186.810616.  Google Scholar

[30]

H. Wendland, Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree,, Adv. Comp. Math., 4 (1995), 389.  doi: 10.1007/BF02123482.  Google Scholar

[1]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136

[2]

Peter Frolkovič, Karol Mikula, Jooyoung Hahn, Dirk Martin, Branislav Basara. Flux balanced approximation with least-squares gradient for diffusion equation on polyhedral mesh. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 865-879. doi: 10.3934/dcdss.2020350

[3]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[4]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443

[5]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012

[6]

Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013

[7]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[8]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[9]

Wenya Qi, Padmanabhan Seshaiyer, Junping Wang. A four-field mixed finite element method for Biot's consolidation problems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020127

[10]

Maika Goto, Kazunori Kuwana, Yasuhide Uegata, Shigetoshi Yazaki. A method how to determine parameters arising in a smoldering evolution equation by image segmentation for experiment's movies. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 881-891. doi: 10.3934/dcdss.2020233

[11]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[12]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

[13]

Joel Kübler, Tobias Weth. Spectral asymptotics of radial solutions and nonradial bifurcation for the Hénon equation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3629-3656. doi: 10.3934/dcds.2020032

[14]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016

[15]

Elvio Accinelli, Humberto Muñiz. A dynamic for production economies with multiple equilibria. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021002

[16]

Ilyasse Lamrani, Imad El Harraki, Ali Boutoulout, Fatima-Zahrae El Alaoui. Feedback stabilization of bilinear coupled hyperbolic systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020434

[17]

Bernold Fiedler. Global Hopf bifurcation in networks with fast feedback cycles. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 177-203. doi: 10.3934/dcdss.2020344

[18]

Leslaw Skrzypek, Yuncheng You. Feedback synchronization of FHN cellular neural networks. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021001

[19]

Hong Fu, Mingwu Liu, Bo Chen. Supplier's investment in manufacturer's quality improvement with equity holding. Journal of Industrial & Management Optimization, 2021, 17 (2) : 649-668. doi: 10.3934/jimo.2019127

[20]

Skyler Simmons. Stability of broucke's isosceles orbit. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021015

2019 Impact Factor: 1.338

Metrics

  • PDF downloads (158)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]