Error bounds for proximal point subproblems and associated inexact proximal point algorithms

Citation
Mv. Solodov et Bf. Svaiter, Error bounds for proximal point subproblems and associated inexact proximal point algorithms, MATH PROGR, 88(2), 2000, pp. 371-389
Citations number
41
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
00255610 → ACNP
Volume
88
Issue
2
Year of publication
2000
Pages
371 - 389
Database
ISI
SICI code
0025-5610(200008)88:2<371:EBFPPS>2.0.ZU;2-Q
Abstract
We study various error measures for approximate solution of proximal point regularizations of the variational inequality problem, and of the closely r elated problem of finding a zero of a maximal monotone operator. A new meri t function is proposed for proximal point subproblems associated with the l atter. This merit function is based on Burachik-Iusem-Svaiter's concept of epsilon-enlargement of a maximal monotone operator. For variational inequal ities, we establish a precise relationship between the regularized gap func tion, which is a natural error measure in this context, and our new merit f unction. Some error bounds are derived using both merit functions for the c orresponding formulations of the proximal subproblem. We further use the re gularized gap function to devise a new inexact proximal point algorithm for solving monotone variational inequalities. This inexact proximal point met hod preserves all the desirable global and local convergence properties of the classical exact/inexact method, while providing a constructive error to lerance criterion, suitable for further practical applications. The use of other tolerance rules is also discussed.