Elsevier

Automatica

Volume 42, Issue 7, July 2006, Pages 1147-1157
Automatica

Numerical methods for controlled regime-switching diffusions and regime-switching jump diffusions

https://doi.org/10.1016/j.automatica.2006.03.016Get rights and content

Abstract

This work is concerned with numerical methods for controlled regime-switching diffusions, and regime-switching jump diffusions. Numerical procedures based on Markov chain approximation techniques are developed. Convergence of the algorithms is derived by means of weak convergence methods. In addition, examples are also provided for demonstration purpose.

Introduction

Many systems in the real world are complex, in which continuous dynamics and discrete events coexist. The need of successfully control such systems in practice leads to the resurgent effort in formulation, modeling, and optimization of regime-switching diffusions and regime-switching jump diffusions. It has attracted much needed attention in the last few years; see for example, Blair and Sworder (1986), Ji and Chizeck (1990), Mariton and Bertrand, 1985, Mao, 1999, among others. Recent study of stochastic hybrid systems has indicated that such a formulation is more general and appropriate for a wide variety of applications. One of the distinctive features of the underlying system is that there are a number of regimes across which the behavior of the system can be markedly different. For some recent applications in risk theory, financial engineering, and insurance modeling, we refer the reader to Di Masi, Kabanov, and Runggaldier (1994), Dufresne and Gerber (1991), Moller (1995), Rolski, Schmidli, Schmidt, and Teugels (1999), Yang and Yin (2004), Yin, Liu, and Zhang (2002), Zhang (2001) and references therein. Such a formulation has also been used in manufacturing, communication theory, signal processing, and wireless networks; see the many references cited in Kushner and Yin (2003), Yin and Zhang (2005). Loosely, the state of the system consists of two components. One of them describes the continuous dynamics, and the other models discrete events. The discrete event is modeled by a Markov chain representing the possible regimes, whereas the continuous dynamics are diffusion processes. It is well known that optimal controls of such systems lead to systems of Hamilton–Jacobi–Bellman (HJB) equations satisfied by the value functions. Even without regime switching, the HJB equations are usually nonlinear and difficult to solve in closed form. Thus numerical methods become viable alternative. One of the most effective methods is the Markov chain approximation approach; see Kushner (1990), Kushner and Dupuis (2001). Based on probabilistic methods, one constructs a Markov chain with specified transition probabilities leading to the approximation to the cost function, and the value functions etc. [Related numerical methods for solving stochastic differential equations can be found in for example, Kloeden and Platen, 1992, Milstein, 1995, Platen, 1999, Protter and Talay, 1997, among others]. Although regime-switching diffusions are important for many applications, the numerical methods for optimal controls of such systems are still scarce. In this work, we develop numerical algorithms for regime-switching controlled diffusions and regime-switching jump diffusions, prove their convergence, and demonstrate their performance by considering some examples. Different from existing results on numerical methods for controlled diffusions, in lieu of one scalar cost function and one scalar value function, we have a collection of such functions. Effectively, we are dealing with a system instead of a single equation. Although we also use Markov chain approximation method, compared with the existing results in Kushner and Dupuis (2001), the systems are hybrid containing both continuous dynamics and discrete events. The results of the aforementioned references are not directly applicable. In our problem, the approximating Markov chain has two components. One component is an approximation to the diffusion, whereas the other keeps track of the regimes.

The rest of the paper is arranged as follows. Problem formulation for controlled regime-switching diffusions is given next. In Section 3, we study the approximating Markov chain, and in Section 4, we consider interpolated processes of the approximation. In Section 5, relaxed control representation is introduced for our approximation. Section 6 establishes the convergence of the algorithms. Section 7 extends the formulation and results to regime-switching jump diffusions and discounted cost problems. Several numerical examples are given in Section 8. Section 9 makes additional remarks. Finally, an appendix is provided to include the detailed proofs of results.

Section snippets

Formulation

Consider a controlled hybrid diffusion system or controlled diffusions with regime switching. For simplicity, the system is assumed to be one dimensional; it can be easily generalized to multi-dimensional cases. Suppose that there is a finite set M={1,,m0} representing the possible regimes of the environment, that α(·) is a continuous-time Markov chain having state space M with generator Q=(qι), and that w(·) is a standard Wiener process. Let {Ft} be a filtration that measures at least {w(s),α

Approximating Markov chain

In this section, we construct a discrete-time, finite-state, controlled Markov chain to approximate the controlled diffusion processes with regime switching. The approximating Markov chain is locally consistent with (1), so that the weak limit of the Markov chain satisfies (1). Let h>0 be a discretization parameter. Define Sh={x:x=kh,k=0,±1,±2,}. Let {(ξnh,αnh),n<} be a controlled discrete-time Markov chain on a discrete state space Sh×M with transition probabilities from a state (x,ι)M to

Interpolations

Based on the Markov chain approximation constructed in the last section, piecewise constant interpolation is obtained here with appropriately chosen interpolation intervals. Using {(ξnh,αnh),n<} to approximate the continuous-time process (x(·),α(·)), we defined the continuous-time interpolation(ξh(·),αh(·)), uh(·) and zh(t) in (6). Using Nh given above (8), define the first exit time of ξh(·) from Gh0 by τh=tNhh. Denote the σ-algebra of {σh(s),αh(s),uh(s),zh(s),st} by Dth. Then τh is a Dth

Relaxed control

Sections 3 and 4 gave numerical method to approximate V(·) in (3). Only weak sense solution of (1) is important. Our primary goal is to prove convergence of our approximation to desired V(·) as h0. The sequence of ordinary controls might not converge in a traditional sense, and the use of the relaxed control terminology enables us to obtain and appropriately characterize the weak limit. To facilitate the proof of weak convergence, we introduce the relaxed control representation; see Kushner

Convergence

Consider the Markov chain {(ξnh,αnh),n<} with transition probabilities defined in (13). Using relaxed control representation, its interpolated process {ξh(·),αh(·),mh(·),wh(·)} can be represented by (18). We also obtain Vh(x,ι) the approximation of the value functions in (20) by dynamic programming equation. In this section, we will show that any weakly convergent subsequence of {ξh(·),αh(·),mh(·),wh(·)} has the weak limit, denoted by (x(·),α(·),m(·),w(·)), which satisfies (21). Also the

Regime-switching jump diffusion processes

Here we consider the optimal control problem for (3) subject to a controlled regime-switching jump diffusion given by dx(t)=b(x(t),α(t),u(t))dt+σ(x(t),α(t))dw(t)+dJ,J(t)=0tϒq(x(s-),α(s),ρ)N(ds,dρ),where N(·) is a Poisson measure with intensity λdt×Π(dρ) (see the details in Kushner & Dupuis, 2001, Section 1.5), Π(·) has a compact support ϒ, q(·) is a bounded and measurable function, and q(·,ι,ρ) is continuous for each ρ and each ιM. There is an equivalent way to define the process (24) by

Examples

In this section, we provide several examples for demonstration. All the numerical experiments were computed using MATLAB on a WinXP platform.

Example 9

Consider a LQ regulator system with regime-switching. The dynamic system is given by dx(t)=A(α(t))x(t)dt+B(α(t))u(t)dt+C(α(t))x(t)dw(t), where the control u(·) takes value in a subset of R; the Markov chain α(·)M with M={1,2} and generator Q, a 2×2 matrix with two columns (-0.5,0.5) and (0.5,-0.5). The set G is [0,2]. Coefficients are A(ι)=B(ι)=3-2ι

Further remarks

This paper is devoted to numerical methods for approximating regime-switching diffusions and regime-switching jump-diffusions. For notational simplicity, the problem is setup such that the x-component of the state is a scalar-valued function. The results obtained readily extend to systems with multi-dimensional diffusion processes.

For a regime-switching system in which the Markov chain has a large state space, we may use the ideas of two-time-scale approach presented in Yin and Zhang (1998)

Acknowledgement

Research of Q.S. Song was supported in part by Wayne State University Graduate Research Assistantship. Research of G. Yin was supported in part by the National Science Foundation, and in part by Wayne State University Research Enhancement Program. Research of Z. Zhang was supported in part by the National Science Foundation, and in part by Michigan Life Science Corridor.

Qingshuo Song received his B.S. in Automatic Control and Systems from Nankai University in 1996, M.A. in Computer Science from Nankai University in 1999 in China, and M.A. in Applied Mathematics from Wayne State University in 2003. He is currently a Ph.D. candidate in Applied Mathematics at Wayne State University. His research interests include stochastic control, numerical methods for stochastic systems, numerical analysis, stochastic differential games, and mathematical finance.

References (25)

  • F. Dufresne et al.

    Risk theory for the compound Poisson process that is perturbed by diffusion

    Insurance; Mathematics and Economics

    (1991)
  • X. Mao

    Stability of stochastic differential with Markovian switching

    Stochastic Process Applications

    (1999)
  • P. Billingsley

    Convergence of probability measures

    (1968)
  • W.P. Blair et al.

    Feedback control of a class of linear discrete systems with jump parameters and quadratic cost criteria

    International Journal of Control

    (1986)
  • G.B. Di Masi et al.

    Mean variance hedging of options on stocks with Markov volatility

    Theory of Probability and Applications

    (1994)
  • M.K. Ghosh et al.

    Optimal control of switching diffusions with application to flexible manufacturing systems

    SIAM Journal on Control and Optimization

    (1993)
  • Y. Ji et al.

    Controllability, stabilizability, and continuous-time Markovian jump linear quadratic control

    IEEE Transactions on Automatic Control

    (1990)
  • P.E. Kloeden et al.

    Numerical solution of stochastic differential equations

    (1992)
  • N.V. Krylov

    On the rate of convergence of finite-difference approximations for Bellman's equations with variable coefficients

    Probability Theory Related Fields

    (2000)
  • H.J. Kushner

    Numerical methods for stochastic control problems in continuous time

    SIAM Journal on Control and Optimization

    (1990)
  • H.J. Kushner

    Consistency issues for numerical methods for variance control with applications to optimization in finance

    IEEE Transactions on Automatic Control

    (2000)
  • H.J. Kushner et al.

    Numerical methods for stochastic control problems in continuous time

    (2001)
  • Cited by (53)

    View all citing articles on Scopus

    Qingshuo Song received his B.S. in Automatic Control and Systems from Nankai University in 1996, M.A. in Computer Science from Nankai University in 1999 in China, and M.A. in Applied Mathematics from Wayne State University in 2003. He is currently a Ph.D. candidate in Applied Mathematics at Wayne State University. His research interests include stochastic control, numerical methods for stochastic systems, numerical analysis, stochastic differential games, and mathematical finance.

    G. George Yin received his B.S. in mathematics from the University of Delaware in 1983, M.S. in Electrical Engineering and Ph.D. in Applied Mathematics from Brown University in 1987. He then joined the Department of Mathematics, Wayne State University, and became a professor in 1996. He is a fellow of IEEE. He severed on the Mathematical Review Date Base Committee, IFAC Technical Committee on Modeling, Identification and Signal Processing, and various conference program committees; he was the editor of SIAM Activity Group on Control and Systems Theory Newsletters, the SIAM Representative to the 34th CDC, Co-Chair of 1996 AMS-SIAM Summer Seminar in Applied Mathematics, Co-Chair of 2003 AMS-IMS-SIAM Summer Research Conference: Mathematics of Finance, and Co-organizer of 2005 IMA Workshop on Wireless Communications. He is an associate editor of Automatica and SIAM Journal on Control and Optimization, was an Associate Editor of IEEE Transactions on Automatic Control from 1994 to 1998, and is on the editorial board of six other journals.

    Zhimin Zhang received his B.S. degree in mathematics in 1982 and M.S. degree in computational mathematics in 1985 from the University of Science and Technology of China, and Ph.D. degree in applied mathematics in 1991 from University of Maryland at College Park. He was assistant professor and associate professor at Texas Tech University from 1991 to 1999 and is a professor in the Department of Mathematics at Wayne State University (USA). He is an Associate Editor of Discrete and Continuous Dynamical Systems – Series B and an Associated Editor of International Journal of Numerical Analysis and Modelling. He is joining the editorial board of Journal of Computational Mathematics in 2006. He was the organizer of the 2000 NSF-CBMS Regional Conference in the Mathematical Sciences: “Superconvergence in Finite Element Methods” at Texas Tech University. His research interests are numerical solutions for partial differential equations, computational mechanics, and scientific computing. His research has been continuously funded by the US National Science Foundation since 1996.

    This paper was not presented at any IFAC meeting. This paper was recommended for publication in revised form by the Associate Editor Rene Boel under the direction of the Editor Ian Petersen.

    View full text