Solving monotone inclusions with linear multi-step methods

Teemu Pennanen; Benar Svaiter

doi:10.1007/s10107-002-0366-2

Solving monotone inclusions with linear multi-step methods

Teemu Pennanen, Benar Svaiter

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

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 −1 (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.

Original language	English
Pages (from-to)	469-487
Number of pages	19
Journal	MATHEMATICAL PROGRAMMING
Volume	96
Issue number	3
DOIs	https://doi.org/10.1007/s10107-002-0366-2
Publication status	Published - Jun 2003

Access to Document

10.1007/s10107-002-0366-2

Cite this

@article{2a89e86d17e0456ab07837f3bc7db0b1,

title = "Solving monotone inclusions with linear multi-step methods",

abstract = "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 −1 (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.",

author = "Teemu Pennanen and Benar Svaiter",

year = "2003",

month = jun,

doi = "10.1007/s10107-002-0366-2",

language = "English",

volume = "96",

pages = "469--487",

journal = "MATHEMATICAL PROGRAMMING",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "3",

}

TY - JOUR

T1 - Solving monotone inclusions with linear multi-step methods

AU - Pennanen, Teemu

AU - Svaiter, Benar

PY - 2003/6

Y1 - 2003/6

N2 - 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 −1 (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.

AB - 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 −1 (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.

U2 - 10.1007/s10107-002-0366-2

DO - 10.1007/s10107-002-0366-2

M3 - Article

SN - 0025-5610

VL - 96

SP - 469

EP - 487

JO - MATHEMATICAL PROGRAMMING

JF - MATHEMATICAL PROGRAMMING

IS - 3

ER -

Solving monotone inclusions with linear multi-step methods

Abstract

Access to Document

Fingerprint

Cite this