Source-linked AI summary
Golden Ratio Algorithms for Variational Inequalities
Yura Malitsky
TL;DR
Non-Lipschitz composite problems lack standard proximal-gradient convergence rates, motivating an adaptive variational-inequality method without linesearch. The proposed algorithm uses iterate-based stepsizes and converges to a solution under local Lipschitz and stated conditions.
Problem
Non-Lipschitz composite problems lack standard theoretical convergence rates for proximal-gradient methods, motivating adaptive variational-inequality algorithms.
Method
The paper proposes an adaptive variational-inequality algorithm whose iterate-based stepsizes approximate an inverse local Lipschitz constant without linesearch.
Results
The generated iterates converge to a solution when F is locally Lipschitz and conditions (C1)–(C3) hold.
Takeaways & Limitations
The variational-inequality framework can also find fixed points by setting F = Id − T and g ≡ 0.
Takeaways & Limitations
The global error bound condition used in some convergence settings is described as too restrictive and difficult to verify.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper frames monotone variational inequalities as a common model for optimization and other applications, then motivates an adaptive method that avoids linesearch while handling difficult operator regularity.
- Problem formulation: The problem is to find z∗ satisfying the variational inequality (1) over a finite-dimensional space, with nonempty solutions, convex lsc g, and monotone F.The function g may be nonsmooth, and indicator choices recover variational inequalities over closed convex sets.
- Motivation: Standard approaches face difficulties because forward-backward and Arrow-Hurwicz methods may fail for monotone nonlinear operators, while global Lipschitz stepsizes can be conservative.Linesearch is commonly used to address unknown or varying curvature, but it introduces an auxiliary iterative procedure within each algorithm iteration.
- Contributions: The proposed adaptive algorithm targets problem (1) with locally Lipschitz F, computes stepsizes from current iterates without linesearch, and approximates an inverse local Lipschitz constant.The contribution passage states that these stepsizes are separated from zero and that each iteration requires only the method’s explicit update operations.
- Paper organization: The paper develops a fixed-stepsize Golden Ratio Algorithm for Lipschitz-continuous F before treating dynamic steps, then derives algorithms for fixed-point problems.The fixed-stepsize case is presented as both independently interesting and informative for the dynamic-step case.
2 Golden Ratio Algorithms
The section introduces GRAAL and its adaptive variant, which use golden-ratio recursions and stepsizes approximating an inverse local Lipschitz constant without linesearch. Under local Lipschitz continuity and the stated conditions, the adaptive method converges to a solution, with ergodic O(1/k) and, under an error bound, at least R-linear convergence.
- Golden Ratio Algorithm: The golden ratio ϕ is selected as the largest constant satisfying 1/c ≥ c − 1, eliminating a cross-term in the convergence analysis.The resulting method also evaluates F at the feasible iterate z_k.
- Adaptive Golden Ratio Algorithm: aGRAAL preserves one F evaluation and one proximal mapping per iteration, requires no linesearch, and uses stepsizes approximating an inverse local Lipschitz constant.Locally Lipschitz continuity of F is sufficient.
- Convergence: Under locally Lipschitz F and conditions (C1)–(C3), both sequences generated by aGRAAL converge to a solution of (1).The result also holds under condition (C4).
- Convergence rates: The ergodic sequence achieves an O(1/k) convergence rate.This conclusion uses that the adaptive stepsizes are separated from zero.
- Convergence rates: With the error bound (42), the adaptive algorithm converges to a solution at least R-linearly.The iterates’ successive differences also converge R-linearly.
3 Fixed point algorithms
The section reformulates fixed-point problems as monotone variational inequalities and applies aGRAAL to locally Lipschitz demi-contractive operators. It establishes convergence to a fixed point and notes that the method can require similar computations to Krasnoselskii–Mann while choosing locally adaptive stepsizes.
- VI reformulation: Fixed-point equations x = Tx are equivalent to variational inequalities with F = Id − T and g ≡ 0.This reformulation enables variational-inequality algorithms to address fixed-point problems.
- Demi-contractive operators: A demi-contractive operator T corresponds to a monotone operator F = Id − T, allowing aGRAAL to find a fixed point.The equivalence follows from ⟨F(x), x − x̄⟩ = ⟨x − Tx, x − x̄⟩ ≥ 0.
- Demi-contractive operators: For locally Lipschitz demi-contractive T, aGRAAL with the modified stepsize rule converges to a fixed point of T.The result is stated as Theorem 4 after defining F = Id − T.
- Comparison with Krasnoselskii–Mann: The modified scheme requires roughly the same computations as Krasnoselskii–Mann but chooses λ_k from local properties of T, potentially making λ_k much larger than 1.This comparison is highlighted for the non-expansive subclass.
- Relaxed conditions: A relaxed condition can support convergence when F = Id − T satisfies a global error bound, although verifying that global condition is difficult.The convergence proof adapts aGRAAL by setting x* = P_S x_k at iteration k.
4 Generalizations
Section 4 generalizes GRAAL in two directions: to symmetric positive definite metrics and to weaker conditions based on a nonempty Minty variational inequality solution set. The metric variant converges under P-monotonicity, while the relaxed condition guarantees that all cluster points solve the original variational inequality.
- General metric settings: GRAAL extends to general metrics induced by symmetric positive definite operators M and P, allowing P-monotonicity and metric-adjusted proximal computations.The framework accommodates operators monotone in ⟨·,·⟩P and can choose M to avoid undesirable proximal computations in that metric.
- General metric settings: Under local Lipschitz continuity and conditions (D1)–(D3), Algorithm 2 generates sequences (zk) and (¯zk) that converge to a solution of (58).The matrices M and P are assumed given, while the choice of M is left dependent on the problem instance.
- Relaxed monotonicity: A more careful analysis relaxes monotonicity assumptions by requiring a nonempty solution set for the associated Minty variational inequality.For continuous F, the Minty solution set is generally only contained in the original VI solution set, unlike the equivalence under monotonicity.
- Relaxed monotonicity: Under local Lipschitz continuity, convex lower-semicontinuous g, and SMVI ≠ ∅, all cluster points generated by Algorithm 1 solve the original variational inequality (1).The proof establishes boundedness of (¯zk) and θk∥zk −¯zk∥→0 before identifying cluster points as elements of SVI.
- Relaxed monotonicity: The relaxed assumptions provide weaker convergence guarantees than Theorem 2 but apply in substantially more general settings.The stated guarantee concerns cluster points rather than the full sequence converging.
5 Numerical experiments
Numerical experiments apply aGRAAL to Nash–Cournot equilibrium and fixed-point feasibility problems, including tomography reconstruction and intersection of balls. Across the reported tests, aGRAAL substantially or significantly improves residual convergence, while requiring no tuning or a priori problem information.
- Nash–Cournot equilibrium: For 1,000-firm Nash–Cournot instances, aGRAAL substantially outperforms Tseng’s FBF method with linesearch despite using one operator evaluation per iteration.The model is challenging because F is not Lipschitz-continuous and is defined only on R^n+; FBF may also evaluate F outside its domain.
- Convex feasibility: aGRAAL with F = Id − T accelerates simultaneous projection for convex feasibility as a black-box method requiring no tuning or a priori information.Simultaneous projections are suitable for parallel implementation, and the framework can address consistent or inconsistent feasibility settings.
- Tomography reconstruction: For a 256 × 256 Shepp–Logan reconstruction from 2^15 measurements, experiments compare KM and aGRAAL using the residual ∥x_k − Tx_k∥ and report aGRAAL’s stepsize behavior.The noisy tomography problem uses a rank-deficient projection setting and a simple feasibility-only model for illustration.
- Intersection of balls: Across 100 random realizations of two synthetic intersection-of-balls scenarios, the residual results show a significant difference between the compared methods.The scenarios use (n = 1000, m = 2000) and (n = 2000, m = 1000), with approximately equal iteration costs.
6 Conclusions and further directions
The paper identifies future directions for GRAAL involving fixed-point analysis, inertial and Bregman extensions, stochastic and coordinate variants, and continuous-time formulations. Several directions remain technically challenging because existing operator properties or linear identities do not directly support convergence or extension arguments.
- Fixed point iteration: Fixed-point analysis rewrites scheme (10) as uk+1 = GRuk, but convergence is unclear because G is firmly nonexpansive whereas R is not.The difficulty concerns deriving meaningful properties for the composition G ◦R.
- Inertial extensions: Inertial extensions are promising because GRAAL averages all previous iterates, unlike inertial methods using zk + α(zk −zk−1) for α > 0.The paper notes that inertia often accelerates optimization algorithms and has been extended to monotone operators.
- Bregman distance: A Bregman-distance extension of GRAAL is nontrivial because the analysis uses identity (7), which explicitly relies on linear structure.Analogous extensions exist for several VI methods, including the extragradient method.
- Stochastic settings: Stochastic and coordinate extensions could make GRAAL advantageous for large-scale problems where computing F(zk) is prohibitively expensive.Stochastic VI methods approximate F(zk) and can improve on deterministic counterparts.
- Continuous dynamic: Deriving a continuous scheme for aGRAAL is challenging, although continuous perspectives can provide deeper understanding of discrete optimization and VI methods.The paper cites Nesterov acceleration as an example of insight gained from continuous analysis.