PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallel hybrid extragradient methods for pseudomonotone equilibrium problems and nonexpansive mappings

Dang Van Hieu, Le Dung Muu, Pham Ky Anh

arXiv:1512.07296v1math.OC

TL;DR

The paper studies finding common solutions of pseudomonotone equilibrium problems and nonexpansive-map fixed-point problems. It proposes parallel hybrid extragradient methods; under the stated assumptions, the generated iterates converge strongly to the projection of the initial point onto the common solution set.

Abstract

from arXiv · show

In this paper we propose and analyze three parallel hybrid extragradient methods for finding a common element of the set of solutions of equilibrium problems involving pseudomonotone bifunctions and the set of fixed points of nonexpansive mappings in a real Hilbert space. Based on parallel computation we can reduce the overall computational effort under widely used conditions on the bifunctions and the nonexpansive mappings.A simple numerical example is given to illustrate the proposed parallel algorithms.

1 Introduction

The introduction motivates finding common equilibrium and fixed-point solutions, then proposes three parallel hybrid extragradient algorithms for finite families of pseudomonotone bifunctions and nonexpansive mappings. Their convergence analysis establishes strong convergence, and a simple numerical experiment illustrates the methods.

1 Introduction

  • Equilibrium problems include optimization, saddle-point, Nash-equilibrium, fixed-point, variational-inequality, and complementarity problems, and the introduction illustrates their relevance with a Nash-Cournot model.In that model, firms choose production quantities to maximize profit while treating competitors' production as input.Source: §1 · p. 2
  • Earlier methods addressed monotone equilibrium problems, while one described hybrid method requires solving a strongly monotone regularized equilibrium problem at each intermediate step.The introduction contrasts this setting with the challenge posed by pseudomonotone bifunctions.Source: §1 · p. 3
  • For pseudomonotone bifunctions, the regularized subproblem need not be strongly monotone or pseudomonotone, so algorithms relying on its monotonicity cannot be applied.The introduction identifies this as the difficulty motivating the proposed methods.Source: §1 · p. 3
  • The paper proposes three parallel hybrid extragradient algorithms for common solutions of finite families of pseudomonotone equilibrium problems and nonexpansive-map fixed-point problems in Hilbert spaces.The methods combine extragradient steps with Mann or Halpern iterations, parallel splitting, and hybrid methods to obtain strong convergence.Source: §1 · p. 4

2 Preliminaries

The preliminaries establish properties of nonexpansive mappings and projections, then state the bifunction assumptions and solution-set facts used in the convergence analysis.

2 Preliminaries

  • For a nonexpansive mapping with a fixed point, F(T) is closed and convex, and I−T is demiclosed.Demiclosedness means weak convergence of xn and strong convergence of (I−T)xn to y imply (I−T)x=y.Source: §2 · p. 5
  • The metric projection maps each point in H to its unique nearest point in C and is firmly nonexpansive.The preliminaries identify firm nonexpansiveness with 1-inverse strong monotonicity.Source: §2 · p. 5
  • A bifunction is monotone when f(x,y)+f(y,x)≤0, and monotonicity implies pseudomonotonicity but not conversely.The preliminaries also require weak continuity, convexity and subdifferentiability in the second argument, and Lipschitz-type continuity with constants c1 and c2; under A1–A4, EP(f) is weakly closed and convex.Source: §2 · p. 5

3 Main results

The section develops three parallel hybrid extragradient algorithms for common solutions of finite pseudomonotone equilibrium families and fixed-point sets of nonexpansive mappings in a real Hilbert space. It gives assumptions and steps for the first algorithm.

3 Main results

  • The algorithms target common solutions of finite pseudomonotone equilibrium families and finite nonexpansive-map families in a real Hilbert space.The stated solution set is assumed nonempty, and the bifunctions satisfy conditions A1–A4.Source: §3 · p. 6
  • Algorithm 1 solves two batches of N strongly convex programs in parallel at each iteration.Its initialization also specifies a stepsize bound and an iteration-weight condition.Source: §3 · pp. 6–7
  • It selects the farthest equilibrium candidate from xn, forms mapping-based intermediate approximations, then selects the farthest of those.The intermediate approximations combine xn with Sj applied to the selected equilibrium candidate.Source: §3 · p. 7

Step 6. Construct two closed convex subsets of C

The section describes constructing two closed convex subsets of C and projecting each Algorithm 1 iterate from x0 onto their intersection, which contains the common solution set. The visible algorithm fragment also outlines parallel strongly convex programs, selection of a farthest candidate, and parallel application of mappings.

Step 6. Construct two closed convex subsets of C

  • At each reached iteration, F ⊂ Cn ∩ Qn, so the sets are closed and convex and the projection defining xn+1 is well-defined.If Algorithm 1 terminates at a finite iteration, that iterate is a common equilibrium solution and fixed point.Source: Step 6. Construct two closed convex… · pp. 7–8
  • Under A1–A4, a nonempty solution set, and finitely many nonexpansive mappings, Algorithm 1 converges strongly to x† = PF x0.Its proof establishes that weak limit points lie in F and that the sequence converges strongly to the projection.Source: Step 6. Construct two closed convex… · p. 11
  • For finitely many pseudomonotone, L-Lipschitz mappings with a nonempty common variational inequality solution set, the specialized method converges strongly to x† = PF x0.The corollary follows by setting fi(x, y) = ⟨Ai(x), y − x⟩ and taking each Sj = I.Source: Step 6. Construct two closed convex… · pp. 12–13
  • Replacing the Mann step with Halpern iteration yields Algorithm 2, which converges strongly to x† = PF x0 when αn → 0 and F is nonempty.A finite-iteration fixed-point claim is not generally valid for Algorithm 2, so the paper advises a practical stopping rule such as n > nmax.Source: Step 6. Construct two closed convex… · pp. 13–14
  • Algorithm 3 replaces the Mann iteration and parallel splitting-up step with a convex combination of the identity and the mappings Sj.The supplied passage introduces this variant and its coefficient conditions but does not state a convergence theorem here.Source: Step 6. Construct two closed convex… · p. 15
  • The method solves N strongly convex programs in parallel.The supplied fragment labels this as Step 2.Source: Step 6. Construct two closed convex… · p. 15
  • It selects the candidate farthest from x_n among z_i^n, for i = 1, . . . , N.The fragments identify the farthest-element selection as Step 3.Source: Step 6. Construct two closed convex… · p. 15
  • It computes u_j^n := S_j z̄_n for j = 1, . . . , M, in parallel.The fragments label this as Step 4.Source: Step 6. Construct two closed convex… · p. 15

Step 5. Construct two closed convex subsets of C

The construction supports a projection update, and the convergence analysis establishes strong convergence to the projection of the initial point onto the common solution set.

Step 5. Construct two closed convex subsets of C

4 Numerical experiment

The numerical experiment tests the parallel hybrid Mann-extragradient method against its sequential mode on a cluster; in the most favorable cases, it reports speedup near two and efficiency near one.

4 Numerical experiment

  • The test uses fi(x, y) := Bi(x)(y − x), with monotone, 4-Lipschitz Bi-based bifunctions and Lipschitz-type constants c1 = c2 = 2.Each equilibrium set is [0, ξi].Source: §4 · p. 17
  • The mappings S_j, j = 1, . . . , M, are nonexpansive; F(S_1) = [0, 1], while F(S_j) = {0} for j = 2, . . . , M.Source: §4 · p. 17
  • The illustrated run initializes x0 = 1, ρ = 1/5, αn = 1/n, and ε = 10^-5, with N = 2 × 10^6 and M = 3 × 10^6.Table 1 is captioned as the experiment with αn = 1/n.Source: §4 · p. 18, Table 1 · p. 19
  • The experiment compares execution times at given tolerances on a Linux cluster with eight computing nodes; parallel timing uses two CPUs.The reported notations include tolerance, iterate error, parallel time Tp, and sequential time Ts.Source: §4 · p. 19
  • In the most favorable cases, PHMEM achieves speedup Sp ≈ 2 and efficiency Ep ≈ 1.The experiment compares parallel and sequential execution.Source: §4 · p. 19

Concluding remarks

The paper proposes three parallel hybrid extragradient methods for common solutions of pseudomonotone equilibrium problems and fixed-point problems. A simple cluster experiment illustrates the algorithms.

Concluding remarks

  • The paper proposes three parallel hybrid extragradient methods for common solutions of finite families of pseudomonotone equilibrium problems and nonexpansive mappings in Hilbert spaces.The variants are parallel hybrid Mann-extragradient, Halpern-extragradient, and iteration-extragradient methods.Source: Concluding remarks · p. 19
  • A simple numerical experiment on computing clusters verifies the efficiency of the proposed parallel algorithms.Source: Concluding remarks · p. 19
Loading 1512.07296v1…