SOME CONVERGENCE RESULTS FOR HOWARD'S ALGORITHM

被引:84
作者
Bokanowski, Olivier [1 ,2 ]
Maroso, Stefania [3 ]
Zidani, Hasnaa [4 ,5 ]
机构
[1] Univ Paris 06, Lab Jacques Louis Lions, F-75252 Paris 05, France
[2] Univ Paris 07, UFR Math, F-75251 Paris 05, France
[3] INRIA Sophia Antipolis, Projet Tosca, F-06902 Sophia Antipolis, France
[4] UMA ENSTA, F-75015 Paris, France
[5] Ecole Polytech, Projet Commands, CMAP, INRIA Saclay, F-91128 Palaiseau, France
关键词
Howard's algorithm (policy iterations); primal-dual active set algorithm; semismooth Newton's method; superlinear convergence; double-obstacle problem; min-max problem; VARIATIONAL-INEQUALITIES; NEWTON METHOD; SEMI-SMOOTH; EQUATIONS; SEMISMOOTH; STRATEGY; MODEL;
D O I
10.1137/08073041X
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
This paper deals with convergence results of Howard's algorithm for the resolution of min(a is an element of A)(B(a)x-c(a)) = 0, where B-a is a matrix, c(a) is a vector, and A is a compact set. We show a global superlinear convergence result, under a monotonicity assumption on the matrices Ba. Extensions of Howard's algorithm for a max-min problem of the form max(b is an element of B) min(a is an element of 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 x 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. Hintermuller, 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.
引用
收藏
页码:3001 / 3026
页数:26
相关论文
共 36 条