A fast algorithm for the two dimensional HJB equation of stochastic control

J. Frédéric Bonnans; Élisabeth Ottenwaelter; Housnaa Zidani

doi:10.1051/m2an:2004034

A fast algorithm for the two dimensional HJB equation of stochastic control

J. Frédéric Bonnans
, Élisabeth Ottenwaelter
, Housnaa Zidani

INRIA Rocquencourt

Research output: Contribution to journal › Article › peer-review

41 Citations (Scopus)

Abstract

This paper analyses the implementation of the generalized finite differences method for the HJB equation of stochastic control, introduced by two of the authors in [Bonnans and Zidani, SIAM J. Numer. Anal. 41 (2003) 1008-1021]. The computation of coefficients needs to solve at each point of the grid (and for each control) a linear programming problem. We show here that, for two dimensional problems, this linear programming problem can be solved in O(p_max) operations, where p_max is the size of the stencil. The method is based on a walk on the Stern-Brocot tree, and on the related filling of the set of positive semidefinite matrices of size two.

Original language	English
Pages (from-to)	723-735
Number of pages	13
Journal	Mathematical Modelling and Numerical Analysis
Volume	38
Issue number	4
DOIs	https://doi.org/10.1051/m2an:2004034
Publication status	Published - 1 Jul 2004
Externally published	Yes

Keywords

Consistency
Finite differences
HJB equation
Stern-brocot tree
Stochastic control
Viscosity solutions

Access to Document

10.1051/m2an:2004034

Cite this

@article{fe0aa2cb89904da094a852698661fa33,

title = "A fast algorithm for the two dimensional HJB equation of stochastic control",

abstract = "This paper analyses the implementation of the generalized finite differences method for the HJB equation of stochastic control, introduced by two of the authors in [Bonnans and Zidani, SIAM J. Numer. Anal. 41 (2003) 1008-1021]. The computation of coefficients needs to solve at each point of the grid (and for each control) a linear programming problem. We show here that, for two dimensional problems, this linear programming problem can be solved in O(pmax) operations, where pmax is the size of the stencil. The method is based on a walk on the Stern-Brocot tree, and on the related filling of the set of positive semidefinite matrices of size two.",

keywords = "Consistency, Finite differences, HJB equation, Stern-brocot tree, Stochastic control, Viscosity solutions",

author = "Bonnans, \{J. Fr{\'e}d{\'e}ric\} and {\'E}lisabeth Ottenwaelter and Housnaa Zidani",

year = "2004",

month = jul,

day = "1",

doi = "10.1051/m2an:2004034",

language = "English",

volume = "38",

pages = "723--735",

journal = "Mathematical Modelling and Numerical Analysis",

issn = "0764-583X",

publisher = "EDP Sciences",

number = "4",

}

TY - JOUR

T1 - A fast algorithm for the two dimensional HJB equation of stochastic control

AU - Bonnans, J. Frédéric

AU - Ottenwaelter, Élisabeth

AU - Zidani, Housnaa

PY - 2004/7/1

Y1 - 2004/7/1

N2 - This paper analyses the implementation of the generalized finite differences method for the HJB equation of stochastic control, introduced by two of the authors in [Bonnans and Zidani, SIAM J. Numer. Anal. 41 (2003) 1008-1021]. The computation of coefficients needs to solve at each point of the grid (and for each control) a linear programming problem. We show here that, for two dimensional problems, this linear programming problem can be solved in O(pmax) operations, where pmax is the size of the stencil. The method is based on a walk on the Stern-Brocot tree, and on the related filling of the set of positive semidefinite matrices of size two.

AB - This paper analyses the implementation of the generalized finite differences method for the HJB equation of stochastic control, introduced by two of the authors in [Bonnans and Zidani, SIAM J. Numer. Anal. 41 (2003) 1008-1021]. The computation of coefficients needs to solve at each point of the grid (and for each control) a linear programming problem. We show here that, for two dimensional problems, this linear programming problem can be solved in O(pmax) operations, where pmax is the size of the stencil. The method is based on a walk on the Stern-Brocot tree, and on the related filling of the set of positive semidefinite matrices of size two.

KW - Consistency

KW - Finite differences

KW - HJB equation

KW - Stern-brocot tree

KW - Stochastic control

KW - Viscosity solutions

UR - https://www.scopus.com/pages/publications/4444313180

U2 - 10.1051/m2an:2004034

DO - 10.1051/m2an:2004034

M3 - Article

AN - SCOPUS:4444313180

SN - 0764-583X

VL - 38

SP - 723

EP - 735

JO - Mathematical Modelling and Numerical Analysis

JF - Mathematical Modelling and Numerical Analysis

IS - 4

ER -

A fast algorithm for the two dimensional HJB equation of stochastic control

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this