Name
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/08073041X | SIAM J. Numerical Analysis |
Keywords | Field | DocType |
semi- smooth newton's method,obstacle problem,primal-dual active set algorithm,howard's algorithm policy iterations,double-obstacle problem,convergence results,k. ito,global superlinear convergence result,portfolio problem,superlinear convergence,front propagation problem,convergence result,min-max problem.,monotonicity assumption,max-min problem,mathematical finance,satisfiability | Convergence (routing),Monotonic function,Discretization,Mathematical optimization,Active set method,Mathematical analysis,Matrix (mathematics),Algorithm,Compact space,Obstacle problem,Mathematics,Newton's method | Journal |
Volume | Issue | ISSN |
47 | 4 | 0036-1429 |
Citations | PageRank | References |
22 | 1.53 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Olivier Bokanowski | 1 | 98 | 12.07 |
| Stefania Maroso | 2 | 25 | 2.18 |
| Hasnaa Zidani | 3 | 101 | 17.27 |