Some convergence results for Howard's algorithm - Archive ouverte HAL Access content directly
Journal Articles SIAM Journal on Numerical Analysis Year : 2009

Some convergence results for Howard's algorithm

(1) , (2) , (3, 4)
1
2
3
4

Abstract

This paper deals with convergence results of Howard's algorithm for the resolution of $\min_{a\in \cA} (B^a x - b^a)=0$ where $B^a$ is a matrix, $b^a$ is a vector (possibly of infinite dimension), and $\cA$ is a compact set. We show a global super-linear convergence result, under a monotonicity assumption on the matrices $B^a$. In the particular case of an obstacle problem of the form $\min(A x - b,\, x-g)=0$ where $A$ is an $N\times N$ matrix satisfying a monotonicity assumption, we show the convergence of Howard's algorithm in no more than $N$ iterations, instead of the usual $2^N$ bound. Still in the case of obstacle problem, we establish the equivalence between Howard's algorithm and a primal-dual active set algorithm (M. Hintermüller et al., {\em SIAM J. Optim.}, Vol 13, 2002, pp. 865-888). We also propose an Howard-type algorithm for a "double-obstacle" problem of the form $\max(\min(Ax-b,x-g),x-h)=0$. We finally illustrate the algorithms on the discretization of nonlinear PDE's arising in the context of mathematical finance (American option, and Merton's portfolio problem), and for the double-obstacle problem.
Fichier principal
Vignette du fichier
RR-zidani.pdf (405.62 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00179549 , version 1 (15-10-2007)

Identifiers

Cite

Olivier Bokanowski, Stefania Maroso, Hasnaa Zidani. Some convergence results for Howard's algorithm. SIAM Journal on Numerical Analysis, 2009, 47 (4), pp.3001--3026. ⟨10.1007/s00245-006-0865-2⟩. ⟨inria-00179549⟩
956 View
1786 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More