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, ., ().

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

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

[4]

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

[5]

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

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

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

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

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

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

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

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

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

[24]

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

[25]

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

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

[27]

R. Schaback and H. Wendland, Numerical Techniques Based on Radial Basis Functions,, Technical report, (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. doi: 10.1137/S0036142901392742.

[29]

D. Shepard, A two-dimensional interpolation function for irregularly-spaced data,, in Proc. 23rd ACM, (1968), 517. 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. 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. 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, (1997). doi: 10.1007/978-0-8176-4755-1.

[4]

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

[5]

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

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

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

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

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

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

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

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

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

[24]

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

[25]

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

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

[27]

R. Schaback and H. Wendland, Numerical Techniques Based on Radial Basis Functions,, Technical report, (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. doi: 10.1137/S0036142901392742.

[29]

D. Shepard, A two-dimensional interpolation function for irregularly-spaced data,, in Proc. 23rd ACM, (1968), 517. 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. doi: 10.1007/BF02123482.

[1]

Martin D. Buhmann, Slawomir Dinew. Limits of radial basis function interpolants. Communications on Pure & 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 & 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 & Continuous Dynamical Systems - A, 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 & 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 & 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 & 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 & 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 & Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057

[10]

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 & Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

Haiying Liu, Wenjie Bi, Kok Lay Teo, Naxing Liu. Dynamic optimal decision making for manufacturers with limited attention based on sparse dynamic programming. Journal of Industrial & Management Optimization, 2019, 15 (2) : 445-464. doi: 10.3934/jimo.2018050

[18]

Najla Mohammed, Peter Giesl. Grid refinement in the construction of Lyapunov functions using radial basis functions. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2453-2476. doi: 10.3934/dcdsb.2015.20.2453

[19]

Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 651-669. doi: 10.3934/jimo.2009.5.651

[20]

Haibo Jin, Long Hai, Xiaoliang Tang. An optimal maintenance strategy for multi-state systems based on a system linear integral equation and dynamic programming. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-26. doi: 10.3934/jimo.2018188

2018 Impact Factor: 1.143

Metrics

  • PDF downloads (11)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]