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 & 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, ., ().   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-322. 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, Boston, Boston, MA, 1997. doi: 10.1007/978-0-8176-4755-1.  Google Scholar

[4]

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

[5]

D. Bertsekas, Dynamic Programming, Prentice Hall Inc., Englewood Cliffs, NJ, 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-377. 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-183.  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-29. 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-347. 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-13. 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-344. 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, 1990), vol. 320 of Pitman Res. Notes Math. Ser., Longman Sci. Tech., Harlow, (1995), 197-209.  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-546. 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-211. 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-337. 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-112. 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-180. 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-2207. 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-270. 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-2632. 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-493, 496.  Google Scholar

[24]

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

[25]

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

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

[27]

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

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

[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.  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-322. 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, Boston, Boston, MA, 1997. doi: 10.1007/978-0-8176-4755-1.  Google Scholar

[4]

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

[5]

D. Bertsekas, Dynamic Programming, Prentice Hall Inc., Englewood Cliffs, NJ, 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-377. 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-183.  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-29. 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-347. 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-13. 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-344. 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, 1990), vol. 320 of Pitman Res. Notes Math. Ser., Longman Sci. Tech., Harlow, (1995), 197-209.  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-546. 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-211. 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-337. 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-112. 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-180. 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-2207. 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-270. 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-2632. 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-493, 496.  Google Scholar

[24]

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

[25]

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

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

[27]

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

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

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

[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, 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]

Zhuoyi Xu, Yong Xia, Deren Han. On box-constrained total least squares problem. Numerical Algebra, Control & 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 & 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 & 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 & Management Optimization, 2016, 12 (2) : 543-563. doi: 10.3934/jimo.2016.12.543
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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
[19]

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
[20]

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

2020 Impact Factor: 1.392

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy