Skip to Main content Skip to Navigation
Journal articles

Some convergence results for Howard's algorithm

Olivier Bokanowski 1 Stefania Maroso 2 Hasnaa Zidani 3, 4
CNRS - Centre National de la Recherche Scientifique : UMR7502, INPL - Institut National Polytechnique de Lorraine, Université Nancy 2, UHP - Université Henri Poincaré - Nancy 1, CRISAM - Inria Sophia Antipolis - Méditerranée , INRIA Lorraine
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
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 metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Hasnaa Zidani Connect in order to contact the contributor
Submitted on : Monday, October 15, 2007 - 11:09:40 PM
Last modification on : Friday, December 3, 2021 - 11:34:09 AM
Long-term archiving on: : Sunday, April 11, 2010 - 11:05:30 PM


Files produced by the author(s)



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⟩



Record views


Files downloads