A sparse Markov chain approximation of LQ-type stochastic control problems. (English) Zbl 1350.49031
Math. Control Relat. Fields 6, No. 3, 363-389 (2016); Addendum 7, No. 4, 623 (2017).
Summary: 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.
The addendum concerns incomplete acknowledgement.
The addendum concerns incomplete acknowledgement.
MSC:
| 49M25 | Discrete approximations in optimal control |
| 49J55 | Existence of optimal solutions to problems involving randomness |
| 93E20 | Optimal stochastic control |
| 49L20 | Dynamic programming in optimal control and differential games |
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 90C40 | Markov and semi-Markov decision processes |
| 90C39 | Dynamic programming |
| 65N30 | Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs |
Keywords:
stochastic optimal control; Galerkin discretization scheme; Markov chain approximation; dynamic programming; logarithmic transformation; Markov state modelReferences:
| [1] | T. Belytschko, Meshless methods: An overview and recent developments,, Comput. Methods Appl. M., 139, 3 (1995) · Zbl 0891.73075 · doi:10.1016/S0045-7825(96)01078-X |
| [2] | A. Berman, <em>Nonnegative Matrices in the Mathematical Sciences</em>,, Academic Press (1979) · Zbl 0484.15016 |
| [3] | O. Bokanowski, An adaptive sparse grid semi-lagrangian scheme for first order Hamilton-Jacobi-Bellman equations,, J. Sci. Comput., 55, 575 (2013) · Zbl 1269.65076 · doi:10.1007/s10915-012-9648-x |
| [4] | M. Boulbrachene, The finite element approximation of Hamilton-Jacobi-Bellman equations,, Comput. Math. Appl., 41, 993 (2001) · Zbl 0988.65092 · doi:10.1016/S0898-1221(00)00334-5 |
| [5] | A. Bovier, <em>Methods of Contemporary Statistical Mechanics</em>,, Metastability (2009) · Zbl 1162.82006 · doi:10.1007/978-3-540-92796-9 |
| [6] | D. Braess, <em>Finite Elements: Theory, Fast Solvers, and Applications in Solid Mechanics</em>,, Cambridge University Press (2007) · Zbl 1118.65117 · doi:10.1088/0957-0233/13/9/704 |
| [7] | G. Bussi, Canonical sampling through velocity rescaling,, J. Chem. Phys., 126 (2007) · doi:10.1063/1.2408420 |
| [8] | E. Carlini, An efficient algorithm for Hamilton-Jacobi equations in high dimension,, Comput. Visual. Sci., 7, 15 (2004) · Zbl 1070.65072 · doi:10.1007/s00791-004-0124-5 |
| [9] | T. Cecil, Numerical methods for high dimensional Hamilton-Jacobi equations using radial basis functions,, J. Comput. Phys., 196, 327 (2004) · Zbl 1053.65086 · doi:10.1016/j.jcp.2003.11.010 |
| [10] | P. Dai Pra, Connections between stochastic control and dynamic games,, Math. Control Signals Systems, 9, 303 (1996) · Zbl 0874.93096 · doi:10.1007/BF01211853 |
| [11] | T. Darden, Particle mesh Ewald: An \(N\cdot\log(N)\) method for Ewald sums in large systems · doi:10.1063/1.464397 |
| [12] | N. Djurdjevac, Estimating the eigenvalue error of Markov state models,, Multiscale Model. Simul., 10, 61 (2012) · Zbl 1253.65010 · doi:10.1137/100798910 |
| [13] | P. Dupuis, Importance sampling for multiscale diffusions,, Multiscale Model. Simul., 10, 1 (2012) · Zbl 1250.60031 · doi:10.1137/110842545 |
| [14] | A. Faradjian, Computing time scales from reaction coordinates by milestoning,, J. Chem. Phys., 120, 10880 (2004) · doi:10.1063/1.1738640 |
| [15] | W. Fleming, Exit probabilities and optimal stochastic control,, Appl. Math. Optim., 4, 329 (1977) · Zbl 0398.93068 · doi:10.1007/BF01442148 |
| [16] | W. Fleming, <em>Controlled Markov Processes and Viscosity Solutions</em>,, Springer (2006) · Zbl 1105.60005 |
| [17] | I. Gikhman, <em>The Theory of Stochastic Processes II</em>,, Springer-Verlag (2004) · Zbl 1068.60005 |
| [18] | C. Hartmann, Characterization of rare events in molecular dynamics,, Entropy, 16, 350 (2014) · doi:10.3390/e16010350 |
| [19] | C. Hartmann, Optimal control of multiscale systems using reduced-order models,, J. Comput. Dynamics, 1, 279 (2014) · Zbl 1303.93187 · doi:10.3934/jcd.2014.1.279 |
| [20] | C. Hartmann, Efficient rare event simulation by optimal nonequilibrium forcing,, J. Stat. Mech. Theor. Exp., 11 (2012) |
| [21] | B. Hess, LINCS: a linear constraint solver for molecular simulations,, J. Comp. Chem., 18, 1463 (1997) |
| [22] | R. H. Hoppe, Multi-grid methods for Hamilton-Jacobi-Bellman equations,, Numer. Math., 49, 239 (1986) · Zbl 0577.65088 · doi:10.1007/BF01389627 |
| [23] | V. Hornak, Comparison of multiple amber force fields and development of improved protein backbone parameters,, Proteins, 65, 712 (2006) · doi:10.1002/prot.21123 |
| [24] | C.-S. Huang, A radial basis collocation method for Hamilton-Jacobi-Bellman equations,, Automatica, 42, 2201 (2006) · Zbl 1104.49024 · 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, 284 (1940) · Zbl 0061.46405 · 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, 545 (1976) · Zbl 0351.60056 · doi:10.1137/1018112 |
| [27] | H. J. Kushner, Numerical methods for stochastic control problems in finance,, in Mathematics of Derivative Securities, 15, 504 (1997) · Zbl 0913.90018 |
| [28] | H. Kushner, <em>Numerical Methods for Stochastic Control Problems in Continuous Time</em>,, Springer Verlag (1992) · Zbl 0754.65068 · doi:10.1007/978-1-4684-0441-8 |
| [29] | J. Mattingly, Ergodicity for SDEs and approximations: Locally Lipschitz vector fields and degenerate noise,, Stochastic Process. Appl., 101, 185 (2002) · Zbl 1075.60072 · doi:10.1016/S0304-4149(02)00150-3 |
| [30] | J. Menaldi, Some estimates for finite difference approximations,, SIAM J. Control Optim., 27, 579 (1989) · Zbl 0684.93088 · doi:10.1137/0327031 |
| [31] | R. H. Momeya, The minimal entropy martingale measure (memm) for a markov-modulated exponential lévy model,, Asia-Pacific Financial Markets, 19, 63 (2012) · Zbl 1245.91092 · doi:10.1007/s10690-011-9142-8 |
| [32] | B. Øksendal, <em>Stochastic Differential Equations: An Introduction With Applications</em>,, Springer (2003) · Zbl 1025.60026 · doi:10.1007/978-3-642-14394-6 |
| [33] | M. Peletier, Chemical reactions as \(\Gamma \)-limit of diffusion,, SIAM Review, 54, 327 (2012) · Zbl 1252.35037 · doi:10.1137/110858781 |
| [34] | H. Rabitz, Whither the future of controlling quantum phenomena?,, Science, 288, 824 (2000) · doi:10.1126/science.288.5467.824 |
| [35] | M. Sarich, <em>Projected Transfer Operators</em>,, PhD thesis (2011) |
| [36] | M. Sarich, On the approximation quality of Markov state models,, Multiscale Model. Simul., 8, 1154 (2010) · Zbl 1210.60082 · doi:10.1137/090764049 |
| [37] | M. Sarich, <em>Metastability and Markov State Models in Molecular Dynamics: Modeling, Analysis, Algorithmic Approaches</em>,, AMS (2013) · Zbl 1305.60004 |
| [38] | C. Schütte, Markov state models based on milestoning,, J. Chem. Phys., 134 (2011) |
| [39] | C. Schütte, Optimal control of molecular dynamics using Markov state models,, Math. Program. (Series B), 134, 259 (2012) · Zbl 1262.49036 · doi:10.1007/s10107-012-0547-6 |
| [40] | S. Sheu, Stochastic control and exit probabilities of jump processes,, J. Control Optim., 23, 306 (1985) · Zbl 0567.60032 · doi:10.1137/0323022 |
| [41] | Q. Song, Convergence of Markov chain approximation on generalized HJB equation and its applications,, Automatica, 44, 761 (2008) · Zbl 1283.93319 · doi:10.1016/j.automatica.2007.07.014 |
| [42] | Q. Song, Numerical methods for controlled regime-switching diffusions and regime-switching jump diffusions,, Automatica, 42, 1147 (2006) · Zbl 1117.93370 · doi:10.1016/j.automatica.2006.03.016 |
| [43] | H. Stapelfeldt, Laser aligned molecules: Applications in physics and chemistry,, Physica Scripta, 2004, 132 (2004) · 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, 15, 505 (2010) · Zbl 1308.93159 · 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, 145 (1993) · Zbl 0810.65065 · doi:10.1080/01630569308816513 |
| [46] | D. Van Der Spoel, Gromacs: Fast, flexible, and free,, J. Comp. Chem., 26, 1701 (2005) |
| [47] | E. Vanden-Eijnden, Transition path theory,, Lect. Notes Phys., 703, 439 (2006) · Zbl 1101.82016 |
| [48] | S. Wang, Numerical solution of Hamilton-Jacobi-Bellman equations by an upwind finite volume method,, J. Global Optim., 27, 177 (2003) · Zbl 1047.49026 · doi:10.1023/A:1024980623095 |
| [49] | H. Wendland, Meshless galerkin methods using radial basis functions,, Math. Comput., 68, 1521 (1999) · Zbl 1020.65084 · doi:10.1090/S0025-5718-99-01102-3 |
| [50] | M. Zhong, Moving least-squares approximations for linearly-solvable stochastic optimal control problems,, J. Control Theory Appl., 9, 451 (2011) · Zbl 1249.93179 · doi:10.1007/s11768-011-0275-0 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
