American Institute of Mathematical Sciences

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

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, 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.
Keywords: optimal feedback., radial basis function, Dynamic programming, moving least squares, Shepard's method.
Mathematics Subject Classification: Primary: 49L20, 49M25; Secondary: 93D1.
Citation: Oliver Junge, Alex Schreiber. Dynamic programming using radial basis functions. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 4439-4453. doi: 10.3934/dcds.2015.35.4439
References:
[1]

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.

show all references

References:
[1]

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.

[1]

Martin D. Buhmann, Slawomir Dinew. Limits of radial basis function interpolants. Communications on Pure and Applied Analysis, 2007, 6 (3) : 569-585. doi: 10.3934/cpaa.2007.6.569
[2]

Runchang Lin, Huiqing Zhu. A discontinuous Galerkin least-squares finite element method for solving Fisher's equation. Conference Publications, 2013, 2013 (special) : 489-497. doi: 10.3934/proc.2013.2013.489
[3]

Peter Giesl. Construction of a global Lyapunov function using radial basis functions with a single operator. Discrete and Continuous Dynamical Systems - B, 2007, 7 (1) : 101-124. doi: 10.3934/dcdsb.2007.7.101
[4]

JaEun Ku. Maximum norm error estimates for Div least-squares method for Darcy flows. Discrete and Continuous Dynamical Systems, 2010, 26 (4) : 1305-1318. doi: 10.3934/dcds.2010.26.1305
[5]

H. D. Scolnik, N. E. Echebest, M. T. Guardarucci. Extensions of incomplete oblique projections method for solving rank-deficient least-squares problems. Journal of Industrial and Management Optimization, 2009, 5 (2) : 175-191. doi: 10.3934/jimo.2009.5.175
[6]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353
[7]

Sigurdur Hafstein, Skuli Gudmundsson, Peter Giesl, Enrico Scalas. Lyapunov function computation for autonomous linear stochastic differential equations using sum-of-squares programming. Discrete and Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049
[8]

Rein Luus. Optimal control of oscillatory systems by iterative dynamic programming. Journal of Industrial and Management Optimization, 2008, 4 (1) : 1-15. doi: 10.3934/jimo.2008.4.1
[9]

Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial and Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057
[10]

Zhuoyi Xu, Yong Xia, Deren Han. On box-constrained total least squares problem. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 439-449. doi: 10.3934/naco.2020043
[11]

Xiao-Wen Chang, David Titley-Peloquin. An improved algorithm for generalized least squares estimation. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 451-461. doi: 10.3934/naco.2020044
[12]

Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial and Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705
[13]

Sohana Jahan, Hou-Duo Qi. Regularized multidimensional scaling with radial basis functions. Journal of Industrial and Management Optimization, 2016, 12 (2) : 543-563. doi: 10.3934/jimo.2016.12.543
[14]

Quyen Tran, Harbir Antil, Hugo Díaz. Optimal control of parameterized stationary Maxwell's system: Reduced basis, convergence analysis, and a posteriori error estimates. Mathematical Control and Related Fields, 2022  doi: 10.3934/mcrf.2022003
[15]

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

Ryan Loxton, Qun Lin. Optimal fleet composition via dynamic programming and golden section search. Journal of Industrial and Management Optimization, 2011, 7 (4) : 875-890. doi: 10.3934/jimo.2011.7.875
[17]

Guy Barles, Ariela Briani, Emmanuel Trélat. Value function for regional control problems via dynamic programming and Pontryagin maximum principle. Mathematical Control and Related Fields, 2018, 8 (3&4) : 509-533. doi: 10.3934/mcrf.2018021
[18]

Hassan Mohammad, Mohammed Yusuf Waziri, Sandra Augusta Santos. A brief survey of methods for solving nonlinear least-squares problems. Numerical Algebra, Control and Optimization, 2019, 9 (1) : 1-13. doi: 10.3934/naco.2019001
[19]

Ya-Xiang Yuan. Recent advances in numerical methods for nonlinear equations and nonlinear least squares. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 15-34. doi: 10.3934/naco.2011.1.15
[20]

Mila Nikolova. Analytical bounds on the minimizers of (nonconvex) regularized least-squares. Inverse Problems and Imaging, 2008, 2 (1) : 133-149. doi: 10.3934/ipi.2008.2.133

2021 Impact Factor: 1.588

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy