Article Contents

2016, Volume 6, Issue 3: 363-389. Doi: 10.3934/mcrf.2016007

This issue Previous Article Next Article On the convergence of the Sakawa-Shindo algorithm in stochastic control

A sparse Markov chain approximation of LQ-type stochastic control problems

Ralf Banisch^1, and
Carsten Hartmann^2,

1.
School of Mathematics, University of Edinburgh, Edinburgh EH9 3JZ, Scotland
2.
Institut für Mathematik, Brandenburgische Technische Universitat Cottbus-Senftenberg, Platz der Deutschen Einheit 1, 03046 Cottbus

Received: March 2015

Revised: October 2015

Published: September 2016

Abstract / Introduction Related Papers Cited by

Abstract

We propose a novel Galerkin discretization scheme for stochastic optimal control problems on an indefinite time horizon. The control problems are linear-quadratic in the controls, but possibly nonlinear in the state variables, and the discretization is based on the fact that problems of this kind admit a dual formulation in terms of linear boundary value problems. We show that the discretized linear problem is dual to a Markov decision problem, prove an $L^{2}$ error bound for the general scheme and discuss the sparse discretization using a basis of so-called committor functions as a special case; the latter is particularly suited when the dynamics are metastable, e.g., when controlling biomolecular systems. We illustrate the method with several numerical examples, one being the optimal control of Alanine dipeptide to its helical conformation.

Keywords:

Mathematics Subject Classification: Primary: 49M25; Secondary: 65N30.

Citation:

Related Papers

Cited by

References

[1]	T. Belytschko, Y. Krongauz, D. Organ, M. Fleming and P. Krysl, Meshless methods: An overview and recent developments, Comput. Methods Appl. M., 139 (1995), 3-47.doi: 10.1016/S0045-7825(96)01078-X.
[2]	A. Berman and R. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Academic Press, 1979.
[3]	O. Bokanowski, J. Garcke, M. Griebel and I. Klompmaker, An adaptive sparse grid semi-lagrangian scheme for first order Hamilton-Jacobi-Bellman equations, J. Sci. Comput., 55 (2013), 575-605.doi: 10.1007/s10915-012-9648-x.
[4]	M. Boulbrachene and M. Haiour, The finite element approximation of Hamilton-Jacobi-Bellman equations, Comput. Math. Appl., 41 (2001), 993-1007.doi: 10.1016/S0898-1221(00)00334-5.
[5]	A. Bovier, Methods of Contemporary Statistical Mechanics, Metastability, Springer, 2009.doi: 10.1007/978-3-540-92796-9.
[6]	D. Braess, Finite Elements: Theory, Fast Solvers, and Applications in Solid Mechanics, Cambridge University Press, 2007.doi: 10.1088/0957-0233/13/9/704.
[7]	G. Bussi, D. Donadio and M. Parrinello, Canonical sampling through velocity rescaling, J. Chem. Phys., 126 (2007), 014101.doi: 10.1063/1.2408420.
[8]	E. Carlini, M. Falcone and R. Ferretti, An efficient algorithm for Hamilton-Jacobi equations in high dimension, Comput. Visual. 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. Comput. Phys., 196 (2004), 327-347.doi: 10.1016/j.jcp.2003.11.010.
[10]	P. Dai Pra, L. Meneghini and W. Runggaldier, Connections between stochastic control and dynamic games, Math. Control Signals Systems, 9 (1996), 303-326.doi: 10.1007/BF01211853.
[11]	T. Darden, D. York and L. Pedersen, Particle mesh Ewald: An $N\cdot\log(N)$ method for Ewald sums in large systems}, J. Chem. Phys., 98 (1993), 10089-10092.doi: 10.1063/1.464397.
[12]	N. Djurdjevac, M. Sarich and C. Schütte, Estimating the eigenvalue error of Markov state models, Multiscale Model. Simul., 10 (2012), 61-81.doi: 10.1137/100798910.
[13]	P. Dupuis, K. Spiliopoulos and H. Wang, Importance sampling for multiscale diffusions, Multiscale Model. Simul., 10 (2012), 1-27.doi: 10.1137/110842545.
[14]	A. Faradjian and R. Elber, Computing time scales from reaction coordinates by milestoning, J. Chem. Phys., 120 (2004), 10880-10889.doi: 10.1063/1.1738640.
[15]	W. Fleming, Exit probabilities and optimal stochastic control, Appl. Math. Optim., 4 (1977), 329-346.doi: 10.1007/BF01442148.
[16]	W. Fleming and H. Soner, Controlled Markov Processes and Viscosity Solutions, Springer, 2006.
[17]	I. Gikhman and A. Skorokhod, The Theory of Stochastic Processes II, Springer-Verlag, Berlin, 2004.
[18]	C. Hartmann, R. Banisch, M. Sarich, T. Badowski and C. Schütte, Characterization of rare events in molecular dynamics, Entropy, 16 (2014), 350-376.doi: 10.3390/e16010350.
[19]	C. Hartmann, J. Latorre, G. Pavliotis and W. Zhang, Optimal control of multiscale systems using reduced-order models, J. Comput. Dynamics, 1 (2014), 279-306.doi: 10.3934/jcd.2014.1.279.
[20]	C. Hartmann and C. Schütte, Efficient rare event simulation by optimal nonequilibrium forcing, J. Stat. Mech. Theor. Exp., 11 (2012), 4pp.
[21]	B. Hess, H. Bekker, H. Berendsen and J. Fraaije, LINCS: a linear constraint solver for molecular simulations, J. Comp. Chem., 18 (1997), 1463-1472.
[22]	R. H. Hoppe, Multi-grid methods for Hamilton-Jacobi-Bellman equations, Numer. Math., 49 (1986), 239-254.doi: 10.1007/BF01389627.
[23]	V. Hornak, R. Abel, A. Okur, B. Strockbine, A. Roitberg and C. Simmerling, Comparison of multiple amber force fields and development of improved protein backbone parameters, Proteins, 65 (2006), 712-725.doi: 10.1002/prot.21123.
[24]	C.-S. Huang, S. Wang, C. Chen and Z.-C. Li, A radial basis collocation method for Hamilton-Jacobi-Bellman equations, Automatica, 42 (2006), 2201-2207.doi: 10.1016/j.automatica.2006.07.013.
[25]	H. Kramers, Brownian motion in a field of force and the diffusion model of chemical reactions, Physica, 7 (1940), 284-304.doi: 10.1016/S0031-8914(40)90098-2.
[26]	H. J. Kushner, A survey of some applications of probability and stochastic control theory to finite difference methods for degenerate elliptic and parabolic equations, SIAM Review, 18 (1976), 545-577.doi: 10.1137/1018112.
[27]	H. J. Kushner, Numerical methods for stochastic control problems in finance, in Mathematics of Derivative Securities, Cambridge University Press, 15 (1997), 504-527.
[28]	H. Kushner and P. Dupuis, Numerical Methods for Stochastic Control Problems in Continuous Time, Springer Verlag, 1992.doi: 10.1007/978-1-4684-0441-8.
[29]	J. Mattingly, A. Stuart and D. Higham, Ergodicity for SDEs and approximations: Locally Lipschitz vector fields and degenerate noise, Stochastic Process. Appl., 101 (2002), 185-232.doi: 10.1016/S0304-4149(02)00150-3.
[30]	J. Menaldi, Some estimates for finite difference approximations, SIAM J. Control Optim., 27 (1989), 579-607.doi: 10.1137/0327031.
[31]	R. H. Momeya and Z. B. Salah, The minimal entropy martingale measure (memm) for a markov-modulated exponential lévy model, Asia-Pacific Financial Markets, 19 (2012), 63-98.doi: 10.1007/s10690-011-9142-8.
[32]	B. Øksendal, Stochastic Differential Equations: An Introduction With Applications, Springer, 2003.doi: 10.1007/978-3-642-14394-6.
[33]	M. Peletier, G. Savaré and M. Veneroni, Chemical reactions as $\Gamma$-limit of diffusion, SIAM Review, 54 (2012), 327-352.doi: 10.1137/110858781.
[34]	H. Rabitz, R. de Vivie-Riedle, M. Motzkus and K. Kompa, Whither the future of controlling quantum phenomena?, Science, 288 (2000), 824-828.doi: 10.1126/science.288.5467.824.
[35]	M. Sarich, Projected Transfer Operators, PhD thesis, FU Berlin, 2011.
[36]	M. Sarich, F. Noé and C. Schütte, On the approximation quality of Markov state models, Multiscale Model. Simul., 8 (2010), 1154-1177.doi: 10.1137/090764049.
[37]	M. Sarich and C. Schütte, Metastability and Markov State Models in Molecular Dynamics: Modeling, Analysis, Algorithmic Approaches, AMS, Providence, RI, 2013.
[38]	C. Schütte, F. Noé, J. Lu, M. Sarich and E. Vanden-Eijnden, Markov state models based on milestoning, J. Chem. Phys., 134 (2011), 204105.
[39]	C. Schütte, S. Winkelmann and C. Hartmann, Optimal control of molecular dynamics using Markov state models, Math. Program. (Series B), 134 (2012), 259-282.doi: 10.1007/s10107-012-0547-6.
[40]	S. Sheu, Stochastic control and exit probabilities of jump processes, J. Control Optim., 23 (1985), 306-328.doi: 10.1137/0323022.
[41]	Q. Song, Convergence of Markov chain approximation on generalized HJB equation and its applications, Automatica, 44 (2008), 761-766.doi: 10.1016/j.automatica.2007.07.014.
[42]	Q. Song, G. Yin and Z. Zhang, Numerical methods for controlled regime-switching diffusions and regime-switching jump diffusions, Automatica, 42 (2006), 1147-1157.doi: 10.1016/j.automatica.2006.03.016.
[43]	H. Stapelfeldt, Laser aligned molecules: Applications in physics and chemistry, Physica Scripta, 2004 (2004), 132-136.doi: 10.1238/Physica.Topical.110a00132.
[44]	A. Steinbrecher, Optimal control of robot guided laser material treatment, in Progress in Industrial Mathematics at ECMI 2008 (eds. A. Fitt, J. Norbury, H. Ockendon and E. Wilson), Springer Berlin Heidelberg, 15 (2010), 505-511.doi: 10.1007/978-3-642-12110-4_79.
[45]	M. Sun, Domain decomposition algorithms for solving Hamilton-Jacobi-Bellman equations, Numer. Func. Anal. Optim., 14 (1993), 145-166.doi: 10.1080/01630569308816513.
[46]	D. Van Der Spoel, E. Lindahl, B. Hess, G. Groenhof, A. Mark and H. C. Berendsen, Gromacs: Fast, flexible, and free, J. Comp. Chem., 26 (2005), 1701-1718.
[47]	E. Vanden-Eijnden, Transition path theory, Lect. Notes Phys., 703 (2006), 439-478.
[48]	S. Wang, L. Jennings and K. Teo, Numerical solution of Hamilton-Jacobi-Bellman equations by an upwind finite volume method, J. Global Optim., 27 (2003), 177-192.doi: 10.1023/A:1024980623095.
[49]	H. Wendland, Meshless galerkin methods using radial basis functions, Math. Comput., 68 (1999), 1521-1531.doi: 10.1090/S0025-5718-99-01102-3.
[50]	M. Zhong and E. Todorov, Moving least-squares approximations for linearly-solvable stochastic optimal control problems, J. Control Theory Appl., 9 (2011), 451-463.doi: 10.1007/s11768-011-0275-0.