On the O(1/t) convergence rate of the projection and contraction methods for variational inequalities with Lipschitz continuous monotone operators
Bingsheng He (hebmanju.edu.cn)
Abstract: Recently, Nemirovski's analysis indicates that the extragradient method has the $O(1/t)$ convergence rate for variational inequalities with Lipschitz continuous monotone operators. For the same problems, in the last decades, we have developed a class of Fej\'er monotone projection and contraction methods. Until now, only convergence results are available to these projection and contraction methods, though the numerical experiments indicate that they always outperform the extragradient method. The reason is that the former benefits from the `optimal' step size in the contraction sense. In this paper, we prove the convergence rate under a unified conceptual framework, which includes the projection and contraction methods as special cases and thus perfects the theory of the existing projection and contraction methods. Preliminary numerical results demonstrate that the projection and contraction methods converge two times faster than the extragradient method.
Keywords: Variational inequality, projection and contraction method, convergence rate.
Category 1: Complementarity and Variational Inequalities
Category 2: Convex and Nonsmooth Optimization (Convex Optimization )
Entry Submitted: 07/14/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|