Source-linked AI summary
A hybrid method without extrapolation step for solving variational inequality problems
Yu. V. Malitsky, V. V. Semenov
TL;DR
The paper addresses strongly convergent solution methods for variational inequalities with monotone, Lipschitz-continuous mappings in Hilbert spaces. It combines projection and hybrid methods while removing an extrapolation step, and proves strong convergence with one operator evaluation per iteration; preliminary examples report competitive performance.
Problem
The paper seeks a strongly convergent method for variational inequalities with monotone and Lipschitz-continuous mappings in Hilbert space.
Method
The method combines projection and hybrid outer-approximation ideas, using different sets to omit the extrapolation step.
Results
The generated sequences converge strongly to PSx0, and each iteration requires only one evaluation of the operator A.
Takeaways & Limitations
The method offers strong convergence with reduced per-iteration operator and projection computation, while showing competitive performance on the reported examples.
Takeaways & Limitations
The computational study is preliminary and its reported result depends on the feasible set.
Abstract
from arXiv · showhide
In this paper, we introduce a new method for solving variational inequality problems with monotone and Lipschitz-continuous mapping in Hilbert space. The iterative process is based on two well-known projection method and the hybrid (or outer approximation) method. However we do not use an extrapolation step in the projection method. The absence of one projection in our method is explained by slightly different choice of sets in hybrid method. We prove a strong convergence of the sequences generated by our method.
1 Introduction
The paper studies variational inequalities in Hilbert space under monotonicity and Lipschitz continuity, and introduces a projection–hybrid method designed for strong convergence.
- Problem setting: The problem is to find x* in a closed convex set C satisfying a variational inequality for a mapping A in Hilbert space.The solution set is assumed nonempty.
- Assumptions: The analysis assumes that A is monotone and Lipschitz-continuous on C with constant L > 0.
- Motivation: Variational inequality theory provides a unified framework for obstacle, unilateral, and equilibrium problems across pure and applied sciences.
2 Relation to the previous work
The paper positions its method against extragradient and hybrid projection schemes, targeting strong convergence with lower per-iteration computational cost.
- Motivation: Strong convergence in infinite-dimensional Hilbert spaces motivates hybrid projection algorithms beyond the classical extragradient method.
- Previous methods: Earlier hybrid methods achieved strong convergence but could require three metric projections and two evaluations of A per iteration.
- Previous methods: Related schemes use halfspace projections and hybrid outer-approximation sets to simplify projection onto C_n ∩ Q_n.
- Contribution: The proposed method changes the sets C_n so it can remove the extrapolation step used in earlier projection schemes.
- Computational cost: Each iteration of the proposed method requires only one projection and one evaluation of the operator A.The paper highlights this reduction for problems with computationally costly operators.
3 Preliminaries
The preliminaries establish projection properties, Minty’s characterization, solution-set geometry, sequence-convergence notation, and a Hilbert-space norm-to-strong-convergence property.
- Projection and sequence lemmas: The preliminaries introduce standard metric-projection properties and a sequence inequality used in the convergence proof.
- Variational inequality tools: Minty’s lemma characterizes solutions of the variational inequality through an equivalent inequality involving (Ay, y − x) for every y in C.
- Solution-set properties: The solution set S of the variational inequality is closed and convex.
- Convergence tools: In a Hilbert space, weak convergence together with convergence of norms implies strong convergence by the Kadec–Klee property.
4 Algorithm and its convergence
Algorithm 1 combines projection and hybrid outer-approximation steps without an extrapolation step, using iteratively constructed halfspaces and projections. Under the stated monotonicity and Lipschitz assumptions, its generated sequences converge strongly to the projection of x0 onto S.
- Algorithm: Algorithm 1 starts from x0, z0 ∈C with parameters k > 0 and λ > 0, then updates iterates and constructs sets Cn and Qn.The method returns to the update step until the stopping condition is met.
- Algorithm: The sets Cn are halfspaces computationally, despite appearing more complicated than the earlier formulation.
- Algorithm: The stopping condition zn+1 = xn = zn is valid because it implies xn ∈S.
- Convergence proof: The proof establishes that S remains contained in Cn and Qn, ensuring each projection xn+1 = PCn∩Qnx0 is well-defined.
- Convergence proof: The sequence (xn) is bounded, its successive squared differences are summable, and (zn) is bounded.
- Convergence proof: Monotonicity places every weak cluster point in S, while the projection argument identifies it with x̄ = PSx0 and yields xn → x̄ and zn → x̄.
5 Computational Experience
The experiments compare strongly convergent algorithms in finite-dimensional examples, emphasizing Algorithm 1’s one-operator computation and competitive performance. The authors qualify these findings as preliminary and dependent on the feasible set.
- The comparison targets Algorithms 1, 3, and 4, which provide strong convergence in Hilbert space.
- Each test uses specified parameters, cyclic projections with error ε, and a termination criterion based on ∥x − PC(x − λAx)∥≤ε.
- The first example uses a random polygon in R5, Ax = x − u, and three starting points, with results reported in Table 1.
- The authors caution that the observed result depends on the feasible set and that the examples were selected to study where Algorithm 1 is effective.
- Algorithm 1 has competitive performance on the reported examples, although the study is explicitly preliminary.