Accelerated schemes for a class of variational inequalities

• 成果类型: Article
• 署名作者: Chen, Yunmei; Lan, Guanghui; Ouyang, Yuyuan
• 署名单位: State University System of Florida; University of Florida; University System of Georgia; Georgia Institute of Technology; Clemson University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1161-4
• 发表日期: 2017
• 页码: 113-149
• 关键词: sample average approximation; proximal point algorithm; stochastic mathematical programs; monotone-operators; saddle-point; equilibrium constraints; convex-optimization; minimization; complexity; selection

摘要

We propose a novel stochastic method, namely the stochastic accelerated mirror-prox (SAMP) method, for solving a class of monotone stochastic variational inequalities (SVI). The main idea of the proposed algorithm is to incorporate a multi-step acceleration scheme into the stochastic mirror-prox method. The developed SAMP method computes weak solutions with the optimal iteration complexity for SVIs. In particular, if the operator in SVI consists of the stochastic gradient of a smooth function, the iteration complexity of the SAMP method can be accelerated in terms of their dependence on the Lipschitz constant of the smooth function. For SVIs with bounded feasible sets, the bound of the iteration complexity of the SAMP method depends on the diameter of the feasible set. For unbounded SVIs, we adopt the modified gap function introduced by Monteiro and Svaiter for solving monotone inclusion, and show that the iteration complexity of the SAMP method depends on the distance from the initial point to the set of strong solutions. It is worth noting that our study also significantly improves a few existing complexity results for solving deterministic variational inequality problems. We demonstrate the advantages of the SAMP method over some existing algorithms through our preliminary numerical experiments.