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. Furthermore, we show theoretically that the method still converges under a new relaxed monotonicity condition and confirm numerically that it can robustly work even for some highly nonmonotone/nonconvex problems.
Keywords
All Related Versions
This publication has 36 references indexed in Scilit:
- An Inertial Forward-Backward Algorithm for Monotone InclusionsJournal of Mathematical Imaging and Vision, 2014
- An Extragradient Algorithm for Monotone Variational InequalitiesCybernetics and Systems Analysis, 2014
- Low-cost modification of Korpelevich’s methods for monotone equilibrium problemsCybernetics and Systems Analysis, 2011
- A First-Order Primal-Dual Algorithm for Convex Problems with Applications to ImagingJournal of Mathematical Imaging and Vision, 2010
- The Subgradient Extragradient Method for Solving Variational Inequalities in Hilbert SpaceJournal of Optimization Theory and Applications, 2010
- 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
- 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