Optimization Online


Accelerated Schemes For A Class of Variational Inequalities

Yuyuan Chen(yun***at***ufl.edu)
Guanghui Lan(glan***at***ise.ufl.edu)
Yuyuan Ouyang(ouyang***at***ufl.edu)

Abstract: We propose a novel method, namely the accelerated mirror-prox (AMP) method, for computing the weak solutions of a class of deterministic and stochastic monotone variational inequalities (VI). The main idea of this algorithm is to incorporate a multi-step acceleration scheme into the mirror-prox method. For both deterministic and stochastic VIs, the developed AMP method computes the weak solutions with optimal rate of convergence. In particular, if the monotone operator in VI consists of the gradient of a smooth function, the rate of convergence of the AMP method can be accelerated in terms of its dependence on the Lipschitz constant of the smooth function. For VIs with bounded feasible sets, the estimate of the rate of convergence of the AMP method depends on the diameter of the feasible set. For unbounded VIs, we adopt the modified gap function introduced by Monteiro and Svaiter for solving monotone inclusion, and demonstrate that the rate of convergence of the AMP method depends on the distance from the initial point to the set of strong solutions.


Category 1: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 03/17/2014
Entry Accepted: 03/17/2014
Entry Last Modified: 03/17/2014

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