| Issue |
ESAIM: M2AN
Volume 38, Number 4, July-August 2004
|
|
|---|---|---|
| Page(s) | 723 - 735 | |
| DOI | https://doi.org/10.1051/m2an:2004034 | |
| Published online | 15 August 2004 | |
A fast algorithm for the two dimensional HJB equation of stochastic control
1
Projet Sydoco,
Inria-Rocquencourt, Domaine de Voluceau, BP 105,
78153 Le Chesnay, France. Frederic.Bonnans@inria.fr.
2
IUT de Paris and Projet Sydoco,
Inria-Rocquencourt, Domaine de Voluceau, BP 105,
78153 Le Chesnay, France. Elisabeth.Ottenwaelter@inria.fr.
3
Projet Sydoco, Inria-Rocquencourt
and Unité de Mathématiques Appliquées,
ENSTA, 32 Boulevard Victor, 75739 Paris Cedex 15, France.
zidani@ensta.fr.
Received:
13
January
2004
Revised:
8
June
2004
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.
Mathematics Subject Classification: 49L99 / 93E20
Key words: Stochastic control / finite differences / viscosity solutions / consistency / HJB equation / Stern-Brocot tree.
© EDP Sciences, SMAI, 2004
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.