Optimization Online


Complexity of variants of Tseng's modified F-B splitting and Korpelevich's methods for generalized variational inequalities with applications to saddle point and convex optimization problems

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

Abstract: In this paper, we consider both a variant of Tseng's modified forward-backward splitting method and an extension of Korpelevich's method for solving generalized variational inequalities with Lipschitz continuous operators. By showing that these methods are special cases of the hybrid proximal extragradient (HPE) method introduced by Solodov and Svaiter, we derive iteration-complexity bounds for them to obtain different types of approximate solutions. In the context of saddle-point problems, we also derive complexity bounds for these methods to obtain another type of an approximate solution, namely that of an approximate saddle point. Finally, we illustrate the usefulness of the above results by applying them to a large class of linearly constrained convex programming problems, including for example cone programming and problems whose objective functions converge to infinity as the boundary of its domain is approached.

Keywords: variational inequality, saddle point, complexity, Korpelevich method, hybrid extragradient proximal, convex optimization

Category 1: Convex and Nonsmooth Optimization

Category 2: Complementarity and Variational Inequalities

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 07/09/2010
Entry Accepted: 07/09/2010
Entry Last Modified: 07/09/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