Projected Reflected Gradient Methods for Monotone Variational Inequalities

By Yura Malitsky. SIAM Journal on Optimization, 2015

368 citations recorded by the source corpus.

This paper is concerned with some new projection methods for solving variational inequality problems with monotone and Lipschitz-continuous mapping in Hilbert space. First, we propose the projected reflected gradient algorithm with a constant stepsize. It is similar to the projected gradient method, namely, the method requires only one projection onto the feasible set and only one value of the mapping per iteration. This distinguishes our method from most other projection-type methods for variational inequalities with monotone mapping. Also we prove that it has R-linear rate of convergence under the strong monotonicity assumption. The usual drawback of algorithms with constant stepsize is the requirement to know the Lipschitz constant of the mapping. To avoid this, we modify our first algorithm so that the algorithm needs at most two projections per iteration. In fact, our computational experience shows that such cases with two projections are very rare. This scheme, at least theoretically, seems to be ve...

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/3074d831b5a3bd1064a0c60cadba37a04019ed02

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

On the convergence of single-call stochastic extra-gradient methods (2019, methodology): “In the context of deterministic, strongly monotone variational inequalities with Lipschitz continuous operators, the last iterate of the method was shown to exhibit a geometric convergence rate [19, 26, 32, 44]; similar geometric convergence results also extend to bilinear saddle-point problems [19,”
Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence (2020, background): “A different line of work focused on reducing the number of gradient computation to one per iteration (Popov 1980; Gidel et al. 2019; Hsieh et al. 2019; Chambolle and Pock 2011; Malitsky 2015; Cui and Shanbhag 2016; Daskalakis et al. 2018; Mokhtari, Ozdaglar, and Pattathil 2020).”
Modified Tseng's extragradient methods for solving pseudo-monotone variational inequalities (2019, methodology): “Solution methods solving the variational inequality (1) have been developed extensively in the literature [4, 5, 6, 10, 16, 17, 18, 19, 23, 24, 28, 30, 31, 33, 34].”
Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities (2021, methodology): “Consequently, after the (twocall) extragradient method [22], several single-call extragradient methods [35, 3, 6, 27] have been analyzed under the monotone setting and share the same convergence rates with Mirror-Prox and dual extrapolation [17].”
A unified algorithm for solving variational inequality and fixed point problems with application to the split equality problem (2019, neutral): “Example 5.3 Finally, we consider the Kojima–Shindo nonlinear complementarity problem (NCP) which was considered in Malitsky (2015), where n = 4 and the mapping A is defined by A(x1, x2, x3, x4) = ⎡ ⎢ ⎢ ⎢ ⎣ 3x21 + 2x1x2 + 2x22 + x3 + 3x4 − 6 2x21 + x1 + x22 + 10x3 + 2x4 − 2 3x21 + x1x2 + 2x22 + 2x3…”
A self adaptive inertial subgradient extragradient algorithm for variational inequality and common fixed point of multivalued mappings in Hilbert spaces (2019, methodology): “Using only a single projection onto C, Maingé and Gobinddass [14] (see also Maingé [15]) also obtained a result relating to weak convergence algorithm for approximating solutions of the VIP in a real Hilbert space by means of a projected reflected gradient-type method [16] and inertial terms.”
Strong convergence of a double projection-type method for monotone variational inequalities in Hilbert spaces (2018, methodology): “Using only a single projection onto C, Maingé and Gobinddass [30] (see also Maingé [29]) also obtained weak convergence results for solving the VI(A,C) in real Hilbert spaces with a monotone and Lipschitz continuous mapping A, by means of a projected reflected gradient-type method [32] and inertial ”
Single projection method for pseudo-monotone variational inequality in Hilbert spaces (2018, background): “[12,14,18,19]) where the operator is assumed to be monotone.”