Source-linked AI summary
Projected Reflected Gradient Methods for Monotone Variational Inequalities
Yu. Malitsky
TL;DR
Monotone, Lipschitz-continuous variational inequalities require projection methods that avoid knowing the mapping’s Lipschitz constant. The paper proposes projected reflected-gradient schemes and proves convergence, including weak convergence generally and R-linear convergence under strong monotonicity.
Problem
Existing constant-stepsize methods require estimating the Lipschitz constant, which can make them impractical and often necessitates tiny stepsizes.
Method
The paper proposes projected reflected-gradient schemes using one projection per iteration, with a modified version that can avoid requiring the Lipschitz constant.
Results
The proposed algorithms converge globally to variational inequality solutions, with weak convergence generally and R-linear convergence under strong monotonicity.
Takeaways & Limitations
The schemes provide theoretically convergent projection methods, while numerical experiments report effectiveness and favorable performance for Algorithm 4.2 in tested problems.
Takeaways & Limitations
Algorithm 4.1 has a smaller interval of feasible stepsizes than other stationary algorithms, which can matter for simple problems.
Abstract
from arXiv · showhide
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 very effective. All methods are shown to be globally convergent to a solution of the variational inequality. Preliminary results from numerical experiments are quite promising.
1. Introduction.
The paper studies variational inequality problems with monotone, Lipschitz-continuous mappings over closed convex sets in Hilbert space. It proposes projected reflected-gradient schemes that reduce per-iteration computational costs, establish convergence and rates, and include a nonstationary variant that avoids knowing the Lipschitz constant.
- Problem setting: The problem is to find x∗∈C satisfying a variational inequality, where C is a closed convex subset of Hilbert space H and F is the underlying mapping.The solution set is assumed nonempty, and F is assumed monotone and Lipschitz-continuous with constant L > 0.
- Existing methods: The projected gradient method requires F to be strongly or inverse strongly monotone to converge, while extragradient-type methods overcome this restriction.The cited extragradient and related schemes generally require one projection onto C and two evaluations of F per iteration.
- Proposed methods: The paper proposes a projected reflected-gradient algorithm with a simple structure that uses one projection onto C and one value of F per iteration.The method evaluates the mapping at a point obtained by reflecting x_{n−1} in x_n, and preliminary numerical comparisons are promising.
- Convergence analysis: The proposed method is globally convergent, and under a more restrictive assumption its rate of convergence is established.The introduction states that the convergence of method (1.6) and its rate under stronger assumptions are proved later.
- Nonstationary variant: A nonstationary variant avoids using the Lipschitz constant of F, making it more flexible and convenient for practical applications.This variant is presented as Algorithm 4.2 and is studied after the convergence analysis of Algorithm 1.6.
2. Preliminaries.
Section 2 assembles classical projection, variational-inequality, convergence, and sequence lemmas used in the paper’s subsequent analysis. It also states a recursive inequality yielding geometric decay for a combined sequence quantity.
- Projection preliminaries: Projection onto a nonempty closed convex set satisfies a variational inequality and a squared-distance decrease estimate.These properties are stated for PMx and every y ∈ M.
- Variational-inequality preliminaries: Minty’s lemma characterizes variational-inequality solutions through inequalities involving F(y) for every y ∈ C.The equivalence assumes F is continuous and monotone.
- Variational-inequality preliminaries: The solution set S of variational inequality (1.1) is closed and convex.This is recorded as a preliminary remark.
- Convergence preliminaries: The preliminaries define weak convergence notation and invoke Opial’s lemma for weakly convergent sequences.The supplied passage states Opial’s lemma for a sequence (x_n) converging weakly to x.
- Rate-of-convergence preliminaries: For nonnegative sequences, the rate lemma establishes a geometric bound a_n ≤ γ^n M under its stated recursive conditions.It provides γ ∈ (0, 1) and M > 0; the displayed iteration gives a_{n+1} + δa_n + b_{n+1} ≤ γ^nM.
3. Algorithm and its convergence.
Section 3 establishes global convergence of Algorithm 3.1: generated iterates weakly converge to a solution under (C1)–(C3), and converge at least R-linearly when stronger monotonicity conditions hold.
- Global convergence: Algorithm 3.1 generates sequences whose iterates weakly converge to a solution of (1.1) under (C1)–(C3).The proof establishes boundedness, identifies weak cluster points as solutions, and rules out multiple weak cluster points.
- Global convergence: The convergence proof uses a bounded, monotone auxiliary sequence and vanishing successive differences between iterates.These properties support boundedness and the weak-cluster-point argument.
- Linear convergence: Under strong monotonicity, (1.1) has a unique solution and Algorithm 3.1 converges to it at least R-linearly.The strong-monotonicity assumption is imposed together with (C1), (C2*), and (C3).
4. Modified Algorithm.
The modified method removes the need to know the Lipschitz constant by using prediction-correction stepsizes, while requiring at most two projections per iteration and usually only one. A further modification handles problematic cases and is proved to converge weakly to a solution.
- Motivation and modification: The modified method replaces prior Lipschitz-constant requirements with a prediction-correction strategy using at most two projections per iteration.The direction uses the inexpensive formula y_n = 2x_n − x_{n−1}.
- Motivation and modification: Numerical experiments found two-projection iterations quite rare, so the method usually performs only one projection per iteration.The passage reports this computational observation without a theoretical explanation.
- Algorithm 4.1 limitation: Algorithm 4.1 appeared effective and reliable in tested problems, but its convergence could not be proved for all cases.The authors report no example where Algorithm 4.1 failed.
- Algorithm 4.2: Algorithm 4.2 modifies the extrapolated direction and stepsize in problematic cases to establish the required inequalities and enable a convergence proof.When needed, it replaces y_n = 2x_n − x_{n−1} with y_n = (1 + τ_n)x_n − τ_nx_{n−1}, where τ_n ∈ (0, 1).
- Convergence: Under assumptions (C1)–(C3), every sequence generated by Algorithm 4.2 converges weakly to a solution of the variational inequality.The convergence theorem applies to both sequences (x_n) and (y_n).
- Comparison of variants: Although the one-projection variant is always executable, computational experience indicates that it is less effective than Algorithm 4.2.The passage attributes this to frequent cases where t_n ≤ 0, even for unsuitable stepsizes.
5. Numerical illustration.
The numerical section benchmarks stationary and nonstationary methods on five problems, emphasizing iteration, execution time, projections, and mapping evaluations. Results favor Alg. 3.1 and especially Alg. 4.2 in several settings, while identifying computational limitations and rare unfavorable cases.
- Experimental setup: The experiments benchmark stationary methods on affine problems and nonstationary methods on nonlinear problems using iterations, time, projections, and F evaluations.Nonstationary comparisons include Alg. 4.2, Alg. Solod.-Svait., and TBFM-nst.
- Problem 1: Problem 1 confirms the classical example where the usual gradient method does not converge, while Alg. 3.1 and the compared methods are evaluated from x0 = (1, . . . , 1).For even m, the zero vector solves the problem; tests used ε = 10^-3 and λ = 0.4.
- Problem 2: Problem 2 shows EGM has the worst performance because it uses two projections per iteration, whereas the other algorithms behave similarly.The experiments used three random samples for every m, with L = ∥M∥ and ε = 10^-3.
- Problem 3: In Problem 3, Alg. Solod.-Svait. has a much higher nf/iter. ratio than Alg. 4.2, despite tests being aborted after 50 seconds.Tests used selected and random starting points with ε = 10^-3 and ε = 10^-6.