Some convergence results for Howard's algorithm

Olivier Bokanowski 1 Stefania Maroso 2 Hasnaa Zidani 3
2 TOSCA
INRIA Lorraine, CRISAM - Inria Sophia Antipolis - Méditerranée , UHP - Université Henri Poincaré - Nancy 1, Université Nancy 2, INPL - Institut National Polytechnique de Lorraine, CNRS - Centre National de la Recherche Scientifique : UMR7502
3 Commands - Control, Optimization, Models, Methods and Applications for Nonlinear Dynamical Systems
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, UMA - Unité de Mathématiques Appliquées
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.
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/inria-00179549
Contributor : Hasnaa Zidani <>
Submitted on : Monday, October 15, 2007 - 11:09:40 PM
Last modification on : Monday, September 30, 2019 - 10:46:02 AM
Long-term archiving on : Sunday, April 11, 2010 - 11:05:30 PM

File

RR-zidani.pdf
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

1647

Files downloads

859