Golden Ratio Algorithms for Variational Inequalities
Author:
Preprint
Abstract
The paper presents a fully explicit algorithm for monotone variational inequalities. The method uses variable stepsizes that are computed using two previous iterates as an approximation of the local Lipschitz constant without running a linesearch. Thus, each iteration of the method requires only one evaluation of a monotone operator $F$ and a proximal mapping $g$. The operator $F$ need not be Lipschitz-continuous, which also makes the algorithm interesting in the area of composite minimization where one cannot use the descent lemma. The method exhibits an ergodic $O(1/k)$ convergence rate and $R$-linear rate, if $F, g$ satisfy the error bound condition. We discuss possible applications of the method to fixed point problems. We discuss possible applications of the method to fixed point problems as well as its different generalizations.
Keywords
All Related Versions
This publication has 41 references indexed in Scilit:
- Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosityMathematical Programming, 2016
- On the ergodic convergence rates of a first-order primal–dual algorithmMathematical Programming, 2015
- Low-cost modification of Korpelevich’s methods for monotone equilibrium problemsCybernetics and Systems Analysis, 2011
- Dual extrapolation and its applications to solving variational inequalities and related problemsMathematical Programming, 2006
- Convergence rate analysis of iteractive algorithms for solving variational inequality problemsMathematical Programming, 2003
- Error bounds in mathematical programmingMathematical Programming, 1997
- A Dynamical Approach to Convex Minimization Coupling Approximation with the Steepest Descent MethodJournal of Differential Equations, 1996
- A new method for a class of linear variational inequalitiesMathematical Programming, 1994
- A variational inequality approach for the determination of oligopolistic market equilibriumMathematical Programming, 1984
- A mathematical programming approach for determining oligopolistic market equilibriumMathematical Programming, 1982