Some Convergence Results for Howard's Algorithm

This paper deals with convergence results of Howard's algorithm for the resolution of minₐ (Bᵃ x - cᵃ) = 0, where Bᵃ is a matrix, cᵃ is a vector, and A is a compact set. We show a global superlinear convergence result, under a monotonicity assumption on the matrices Bᵃ. Extensions of Howard's algorithm for a max-min problem of the form maxb minₐ (Ba,bx - ca,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 × N matrix satisfying a monotonicity assumption, we show the convergence of Howard's algorithm in no more than N iterations, instead of the usual 2N 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.