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

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.