Optimization Online


On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean

R D C Monteiro (monteiro***at***isye.gatech.edu)
B F Svaiter (benar***at***impa.br)

Abstract: In this paper we analyze the iteration-complexity of the hybrid proximal extragradient (HPE) method for finding a zero of a maximal monotone operator recently proposed by Solodov and Svaiter. One of the key points of our analysis is the use of new termination criteria based on the $\varepsilon$-enlargement of a maximal monotone operator. The advantage of using these termination criteria is that their definition do not depend on the boundedness of the domain of the operator. We then show that Korpelevich's extragradient method for solving monotone variational inequalities falls in the framework of the HPE method. As a consequence, using the complexity analysis of the HPE method, we obtain new complexity bounds for Korpelevich's extragradient method which do not require the feasible set to be bounded, as assumed in a recent paper by Nemirovski. Another feature of our analysis it that the derived iteration-complexity bounds are proportional to the distance of the initial point to the solution set. The HPE framework is also used to obtain the first iteration-complexity result for Tseng's modified forward-backward splitting method for finding a zero of the sum of a monotone Lipschitz continuous map with an arbitrary maximal monotone operator whose resolvent is assumed to be easily computable. Using also the framework of the HPE method, we study the complexity of a variant of a Newton-type extragradient algorithm proposed by Solodov and Svaiter for finding a zero of a smooth monotone function with Lipschitz continuous Jacobian.

Keywords: extragradient, variational inequality, maximal monotone operator, complexity, complementarity problems

Category 1: Complementarity and Variational Inequalities

Category 2: Convex and Nonsmooth Optimization

Category 3: Linear, Cone and Semidefinite Programming

Citation: SIAM Journal on Optimization, 20 (2010) 2755-2787.


Entry Submitted: 03/17/2009
Entry Accepted: 03/17/2009
Entry Last Modified: 10/17/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society