Some Convergence Results for Howard's Algorithm

Olivier Bokanowski, Stefania Maroso, Hasnaa Zidani

SIAM Journal on Numerical Analysis · 2009 · 134 citations · 29 references

Concepts

Abstract

This paper deals with convergence results of Howard's algorithm for the resolution of $\min_{a\in\mathcal{A}} (B^a x - c^a) = 0$, where $B^a$ is a matrix, $c^a$ is a vector, and $\mathcal{A}$ is a compact set. We show a global superlinear convergence result, under a monotonicity assumption on the matrices $B^a$. Extensions of Howard's algorithm for a max-min problem of the form $\max_{b\in\mathcal{B}} \min_{a\in\mathcal{A}} (B^{a,b}x - c^{a,b}) = 0$ are also proposed. In the particular case of an obstacle problem of the form $\min (Ax - 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 an obstacle problem, we establish the equivalence between Howard's algorithm and a primal-dual active set algorithm [M. Hintermüller, K. Ito, and K. Kunisch, SIAM J. Optim., 13 (2002), pp. 865–888]. The algorithms are illustrated on the discretization of nonlinear PDEs arising in the context of mathematical finance (American option and Merton's portfolio problem), of front propagation problems, and for the double-obstacle problem.

References

29