Optimization Online


Iteration-Complexity of a Newton Proximal Extragradient Method for Monotone Variational Inequalities and Inclusion Problems

Renato DC Monteiro (monteiro***at***isye.gatech.edu)
Benar F Svaiter (benar***at***impa.br)

Abstract: In a recent paper by Monteiro and Svaiter, a hybrid proximal extragradient framework has been used to study the iteration-complexity of a first-order (or, in the context of optimization, second-order) method for solving monotone nonlinear equations. The purpose of this paper is to extend this analysis to study a prox-type first-order method for monotone smooth variational inequalities and inclusion problems consisting of the sum of a smooth monotone map and a maximal monotone point-to-set operator. Each iteration of the method computes an approximate solution of a proximal subproblem, obtained by linearizing the smooth part of the operator in the corresponding proximal equation for the original problem, which is then used to perform an extragradient step as prescribed by the HPE framework. Both pointwise and ergodic iteration-complexity results are derived for the aforementioned first-order method using corresponding results obtained here for a subfamily of the HPE framework.

Keywords: complexity, extragradient, variational inequality, maximal monotone operator, proximal point, hybrid, Newton methods

Category 1: Convex and Nonsmooth Optimization

Category 2: Complementarity and Variational Inequalities


Download: [PDF]

Entry Submitted: 04/14/2011
Entry Accepted: 04/14/2011
Entry Last Modified: 05/26/2012

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 Optimization Society