Golden Ratio Algorithms for Variational Inequalities
This work provides a novel algorithmic framework for solving monotone variational inequalities and composite minimization problems, eliminating the need for Lipschitz continuity and linesearch, which is beneficial for practitioners in optimization and fixed point problems.
The paper proposes a fully explicit algorithm for monotone variational inequalities that uses variable stepsizes computed from two previous iterates, requiring only one evaluation of the monotone operator and one proximal mapping per iteration. The method achieves an ergodic O(1/k) convergence rate and R-linear rate under error bound conditions, without requiring Lipschitz continuity of the operator.
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.