Incremental constraint projection methods for variational inequalities

Mengdi Wang, Dimitri P. Bertsekas

Research output: Contribution to journalArticlepeer-review

20 Scopus citations

Abstract

We consider the solution of strongly monotone variational inequalities of the form F(x∗)′(x-x∗)≥0, for all x∈X. We focus on special structures that lend themselves to sampling, such as when X is the intersection of a large number of sets, and/or F is an expected value or is the sum of a large number of component functions. We propose new methods that combine elements of incremental constraint projection and stochastic gradient. These methods are suitable for problems involving large-scale data, as well as problems with certain online or distributed structures. We analyze the convergence and the rate of convergence of these methods with various types of sampling schemes, and we establish a substantial rate of convergence advantage for random sampling over cyclic sampling.

Original languageEnglish (US)
Pages (from-to)321-363
Number of pages43
JournalMathematical Programming
Volume150
Issue number2
DOIs
StatePublished - Jan 1 2015

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • Alternate/cyclic projection
  • Incremental method
  • Random projection
  • Sampling
  • Stochastic approximation
  • Stochastic gradient
  • Variational inequalities

Fingerprint Dive into the research topics of 'Incremental constraint projection methods for variational inequalities'. Together they form a unique fingerprint.

Cite this