Convergence rate analysis of interactive algorithms for solving variational inequality problems

Convergence rate analysis of interactive algorithms for solving variational inequality problems

0.00 Avg rating0 Votes
Article ID: iaor20041763
Country: Germany
Volume: 96
Issue: 3
Start Page Number: 513
End Page Number: 528
Publication Date: Jan 2003
Journal: Mathematical Programming
Authors:
Abstract:

We present a unified convergence rate analysis of iterative methods for solving the variational inequality problem. Our results are based on certain error bounds; they subsume and extend the linear and sublinear rates of convergence established in several previous studies. We also derive a new error bound for γ-strictly monotone variational inequalities. The class of algorithms covered by our analysis is fairly board. It includes some classical methods for variational inequalities, e.g., the extragradient, matrix splitting, and proximal point methods. For these methods, our analysis gives estimates not only for linear convergence (which had been studied extensively), but also sublinear, depending on the properties of the solution. In addition, our framework includes a number of algorithms to which previous studies are not applicable, such as the infeasible projection methods, a separation-projection method, (inexact) hybrid proximal point methods, and some splitting techniques. Finally, our analysis covers certain feasible descent methods of optimization, for which similar convergence rate estimates have been recently obtained by Luo.

Reviews

Required fields are marked *. Your email address will not be published.