# 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, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7641
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.
Type de document :
Article dans une revue
SIAM Journal on Numerical Analysis, Society for Industrial and Applied Mathematics, 2009, 47 (4), pp.3001--3026. 〈10.1007/s00245-006-0865-2〉
Domaine :

Littérature citée [22 références]

https://hal.inria.fr/inria-00179549
Contributeur : Hasnaa Zidani <>
Soumis le : lundi 15 octobre 2007 - 23:09:40
Dernière modification le : vendredi 12 janvier 2018 - 02:00:23
Document(s) archivé(s) le : dimanche 11 avril 2010 - 23:05:30

### Fichier

RR-zidani.pdf
Fichiers produits par l'(les) auteur(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〉

### Métriques

Consultations de la notice

## 1438

Téléchargements de fichiers