Solving monotone inclusions with linear multi-step methods

 In this paper a new class of proximal-like algorithms for solving monotone inclusions of the form T(x)∋0 is derived. It is obtained by applying linear multi-step methods (LMM) of numerical integration in order to solve the differential inclusion , which can be viewed as a generalization of the steepest decent method for a convex function. It is proved that under suitable conditions on the parameters of the LMM, the generated sequence converges weakly to a point in the solution set T ⁻¹(0). The LMM is very similar to the classical proximal point algorithm in that both are based on approximately evaluating the resolvants of T. Consequently, LMM can be used to derive multi-step versions of many of the optimization methods based on the classical proximal point algorithm. The convergence analysis allows errors in the computation of the iterates, and two different error criteria are analyzed, namely, the classical scheme with summable errors, and a recently proposed more constructive criterion.

Authors and Affiliations

1. Department of Management Science, Helsinki School of Economics, PL 1210 00101 Helsinki, Finland, e-mail: pennanen@hkkkfi. Partially supported by Foundation for Economic Education and IMPA, , , , , , FI

   Teemu Pennanen

2. Instituto de Matemática Pura e Aplicada, Estrada Dona Castorina 110, Rio de Janeiro RJ, CEP 22460-320, Brazil, e-mail: benar@impa.br Partially supported by CNPq Grant 301200/93-9 (RN) and by PRONEX-Optimization, , , , , , BR

   B. F. Svaiter

Received: April 2001 / Accepted: November 2002 Published online: February 14, 2003

Key Words. proximal point algorithm – monotone operator – numerical integration – strong stability – relative error criterion

Mathematics Subject Classification (1991): 20E28, 20G40, 20C20

Reprints and permissions