# Some convergence results for Howard's algorithm

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.
Document type :
Journal articles
Domain :

Cited literature [22 references]

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

### File

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

### 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⟩

Record views