PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithms for the Split Variational Inequality Problem

Yair Censor, Aviv Gibali, Simeon Reich

arXiv:1009.3780v2math.OCmath.FA

TL;DR

The paper introduces SVIP, which links VIP solutions across two spaces through a bounded linear transformation. It develops iterative algorithms, including product-space and direct approaches, and reports convergence under stated conditions while extending the framework to multiple-set problems and special cases.

  • Problem

    The paper addresses how to find a solution of one inverse problem whose bounded-linear image solves another inverse problem, specifically two linked VIPs.

  • Method

    It reformulates SVIP as an equivalent constrained VIP in a product space and also develops an approach that avoids product-space translation.

  • Results

    The proposed algorithms generate sequences that converge weakly to SVIP solution points under the stated conditions.

  • Takeaways & Limitations

    The framework covers special cases including split feasibility, split minimization, and newly introduced common variational inequality point and split zeros problems.

  • Takeaways & Limitations

    For the multiple-set SVIP, the paper does not yet provide a solution approach that avoids product-space formalism.

Abstract

from arXiv · show

We propose a prototypical Split Inverse Problem (SIP) and a new variational problem, called the Split Variational Inequality Problem (SVIP), which is a SIP. It entails finding a solution of one inverse problem (e.g., a Variational Inequality Problem (VIP)), the image of which under a given bounded linear transformation is a solution of another inverse problem such as a VIP. We construct iterative algorithms that solve such problems, under reasonable conditions, in Hilbert space and then discuss special cases, some of which are new even in Euclidean space.

1 Introduction

The paper introduces the Split Variational Inequality Problem, coupling VIP solutions in two Hilbert spaces through a bounded linear operator. It develops product-space and direct iterative approaches, situating SVIP among split minimization and feasibility problems.

  • Problem formulation: The problem is posed in two real Hilbert spaces with operators f and g and nonempty, closed, convex sets C and Q.
  • Problem formulation: SVIP seeks x∗ in C solving one VIP while y∗ = Ax∗ in Q solves another VIP.The two variational inequalities are linked by the bounded linear operator A.
  • Scope and applications: SVIP generalizes split minimization and includes the Split Feasibility Problem as a special case.The paper notes prior practical use of SFP in intensity-modulated radiation therapy treatment planning.
  • Solution approaches: One approach converts SVIP into an equivalent constrained VIP in the product space H1 × H2 and applies an extragradient-inspired iterative algorithm.
  • Solution approaches: A second approach solves SVIP without translating it into a product-space formulation, with convergence established under stated conditions.

3 An algorithm for solving the constrained variational inequality problem

This section develops an extragradient-inspired algorithm for a constrained VIP. Under monotonicity, Lipschitz continuity, and parameter conditions, its generated sequences converge to a feasible VIP solution.

  • Problem and assumptions: The constrained VIP seeks a point in the intersection of a closed convex constraint set Ω and SOL(C, f).
  • Algorithm: The algorithm modifies Korpelevich’s extragradient method and computes an intermediate point before constructing a supporting half-space Tk.
  • Problem and assumptions: The convergence analysis assumes that f is monotone on C and Lipschitz continuous on H with constant κ > 0.
  • Convergence: The generated sequences converge to a point z in Ω∩SOL(C, f) under the theorem’s conditions.
  • Relation to prior work: Compared with a related method, the algorithm projects onto a half-space rather than directly onto the convex set C.

4 The split variational inequality problem as a constrained variational inequality problem in a product space

The paper reformulates SVIP as an equivalent constrained VIP in the product space H1 × H2. This equivalence permits reuse of the constrained-VIP algorithm and yields convergence under monotonicity, Lipschitz, and parameter assumptions.

  • Product-space formulation: The product-space construction uses H1 × H2, the product set D = C × Q, and an associated constrained VIP.
  • Equivalence: A decomposition argument establishes equivalence between the original SVIP and the product-space constrained VIP.
  • Assumptions: The product-space algorithm requires f and g to be monotone on C and Q and Lipschitz continuous with constants κ1 and κ2.
  • Convergence: The generated sequences converge to a point in V ∩ SOL(D, h) under the stated parameter conditions.
  • Implementation: Translating the product-space algorithm back to H1 and H2 depends especially on computing the projection onto V.Product-set projections separate into projections onto C and Q, while finite-dimensional subspace projections can use an orthogonal basis.

5 Solving the split variational inequality problem without a product space

The paper characterizes the SVIP solution set directly and proposes an algorithm using projected operators and the adjoint of A, without product-space translation. Under inverse strong monotonicity, step-size, and nonemptiness assumptions, the generated sequence converges weakly to a solution.

  • Direct formulation: The SVIP solution set is Γ := {z ∈ SOL(C, f) | Az ∈ SOL(Q, g)}.This formulation requires the source point and its image under A to solve their respective variational inequalities.
  • Convergence: The convergence proof relies on Fejér-monotonicity of the generated sequence with respect to Γ.The associated lemma establishes this monotonicity before the weak-convergence theorem is applied.
  • Convergence: Under nonempty Γ, inverse strong monotonicity, and λ ∈ [0, 2α], Algorithm 5.1 generates a sequence converging weakly to a point in Γ.The convergence theorem assumes γ ∈ (0, 1/L) and bounded linearity of A.
  • Relation to prior work: The direct SVIP results are related to split common fixed-point methods, with differences in operator assumptions and convergence scope.Here U is firmly quasi-nonexpansive while T is only nonexpansive; prior work also considered demicontractive operators.
  • Multiple-set extension: The framework extends to the Multiple Set Split Variational Inequality Problem through a product-space construction and a parallel algorithm.For MSSVIP, the paper states that no solution approach avoiding product-space formalism is yet available.

6 Applications

The applications section identifies several feasibility, minimization, common-inequality, and zero-finding problems as SVIP special cases. It also derives equivalences and shows how the framework yields a minimum-norm feasibility solution under a particular operator choice.

  • Split and convex feasibility: The Split Feasibility Problem and Convex Feasibility Problem are special cases of the SVIP.The SFP is obtained by setting f ≡ g ≡ 0, while the CFP is a special case of the SFP with A = I.
  • Split and convex feasibility: Viewing the SFP through the SVIP enables computation of its minimum-norm solution.The paper obtains this by solving the SVIP with f = I and g ≡ 0.
  • Common variational inequality points: The Common Variational Inequality Point Problem is newly introduced and is equivalent to a constrained VIP in an appropriate product space.Its product-space formulation can be solved using Algorithm 3.4.
  • Split minimization: When f and g are gradients of convex functions, the SVIP becomes a Split Minimization Problem.The source and image points minimize the respective functions over C and Q.
  • Split zeros: The Split Zeros Problem is newly introduced as finding x* with B1(x*) = 0 and B2(Ax*) = 0.For surjective A, it is a special case of the SVIP.
  • Split zeros: Under the lemma’s assumptions, solving the stated variational problem is equivalent to membership in Γ, the split VIP solution set.The equivalence applies for x* ∈ C with Ax* ∈ Q and nonempty zero intersections.

arXiv:1009.3780v2 [math.OC] 10 Aug 2011

The paper introduces the Split Inverse Problem and its variational-inequality instance, then develops Hilbert-space algorithms and discusses special cases, including new Euclidean-space problems.

  • Contribution: The paper proposes a prototypical Split Inverse Problem and introduces the Split Variational Inequality Problem as one of its instances.The SVIP links solutions across two spaces through a bounded linear transformation.
  • Contribution: It constructs iterative algorithms for these problems under reasonable conditions in Hilbert space.The paper’s keywords include iterative methods, metric projections, monotone operators, and product spaces.
  • Applications: The paper discusses special cases of the framework, some of which are new even in Euclidean space.These include applications and specialized split problems derived from the SVIP.

1 Introduction

The paper introduces the Split Variational Inequality Problem (SVIP), coupling VIPs in two Hilbert spaces through a bounded linear operator. It develops product-space and direct iterative approaches, relates SVIP to prior methods, and identifies applications and unifying extensions.

  • Problem formulation: SVIP requires a solution x* of one VIP whose image Ax* solves a second VIP in another Hilbert space.The image must also lie in the second problem’s feasible set Q.
  • Applications and relations: SVIP includes split minimization and the Split Feasibility Problem, previously used in intensity-modulated radiation therapy planning.The paper also presents CVIP as unifying and improving several existing constrained VIP problems and methods.
  • Solution approaches: The paper considers a product-space reformulation into an equivalent Constrained VIP (CVIP).This equivalence allows an iterative CVIP algorithm to solve the original SVIP.
  • Solution approaches: A second method solves SVIP without translating it into a product-space formulation.The paper presents this method and proves convergence later in the development.
  • Solution approaches: The CVIP algorithm is inspired by an extension of Korpelevich’s extragradient method.The approach is part of the paper’s iterative treatment of both CVIP and SVIP.

2 The split variational inequality problem as a methodology for inverse problems

The paper places SVIP within a general Split Inverse Problem framework, where linked inverse problems are posed in two spaces. It extends this methodology from convex feasibility problems to variational inequalities.

  • Split inverse problems: A prototypical SIP links inverse problems in spaces X and Y through a bounded linear operator A.The required point x* solves IP1, while Ax* solves IP2.
  • Split inverse problems: Different choices of IP1 and IP2 allow many inverse-problem models to fit the SIP framework.The Split Convex Feasibility Problem is identified as an earlier SIP instance.
  • Applications: Convex feasibility problems have been used to model inverse problems across areas including radiation therapy, imaging, denoising, and antenna design.The passage lists applications across mathematics, physical sciences, and engineering.
  • SVIP as an extension: SVIP extends SIP methodology by using Variational Inequality Problems in both spaces.The paper notes that convex feasibility and constrained optimization are special cases of VIP, so SVIP covers the earlier SCFP.

3 Preliminaries

The preliminaries establish Hilbert-space notation, convergence concepts, operator properties, projection geometry, and monotone-operator tools used in the algorithms and convergence analysis.

  • Hilbert-space foundations: The section fixes real Hilbert spaces, inner products, norms, closed convex sets, and notation for weak and strong sequence convergence.Weak convergence is denoted by xk ⇀ x, while strong convergence is denoted by xk → x.
  • Projection operators: Metric projection onto a nonempty closed convex set is unique and nonexpansive.Its characterization includes an inner-product inequality and a squared-distance inequality.
  • Operator properties: The preliminaries define demiclosedness, nonexpansiveness, Opial’s condition, inverse strong monotonicity, Lipschitz continuity, and maximal monotonicity.These properties provide the operator-theoretic vocabulary for subsequent convergence arguments.
  • Monotone operators: The normal cone of a closed convex set is defined through an inner-product inequality against every point in the set.The normal-cone construction is connected to maximal monotone operators and VIP solution sets.
  • Algorithmic tools: For an inverse strongly monotone operator h, the mapping PD(I − λh) is nonexpansive when λ ∈ [0, 2α].This property is collected for later use in the algorithmic analysis.

4 An algorithm for solving the constrained variational inequality problem

The paper presents an iterative algorithm for a constrained VIP under monotonicity and Lipschitz assumptions, proves convergence, and highlights a projection advantage over related methods.

  • Problem and assumptions: The constrained VIP seeks a point in the intersection of a feasible set and the solution set SOL(C, f).It is formulated for a real Hilbert space with nonempty, closed, convex sets C and Ω.
  • Problem and assumptions: The convergence analysis assumes that f is monotone on C and Lipschitz continuous with constant κ > 0.These are stated as Conditions 4.1 and 4.2.
  • Convergence result: Under the stated conditions, the algorithm generates two sequences converging to a point z ∈ Ω ∩ SOL(C, f).The convergence theorem identifies the limiting point within the constrained VIP solution set.
  • Algorithm: Each iteration constructs a half-space Tk supporting C at yk and uses projections involving Tk and Ω to calculate the next iterate.The algorithm description separates half-space construction from the subsequent iterate calculation.
  • Relation to prior work: Compared with a related nonexpansive-operator method, Algorithm 4.4 projects onto a half-space rather than directly onto the convex set C.The paper presents this as an advantage when projections onto C lack closed-form expressions.

5 The split variational inequality problem as a constrained variational inequality problem in a product space

The SVIP is transformed into an equivalent constrained VIP in the product space H1 × H2. This equivalence supports an extragradient-inspired iterative algorithm whose sequences converge weakly under monotonicity, Lipschitz, and parameter conditions.

  • Product-space formulation: The product-space formulation introduces D := C × Q and transforms the SVIP into an equivalent constrained VIP.The equivalence is established by showing that a solution pair of the product-space problem solves the two original VIPs, and conversely.
  • Algorithm: The constrained VIP is solved with an iterative algorithm inspired by an extension of Korpelevich’s extragradient method.The approach applies the product-space algorithm to the original SVIP through the established equivalence.
  • Conditions: Monotonicity of f and g and Lipschitz continuity with constants κ1 and κ2 are required for the convergence analysis.The stated conditions require f and g to be monotone and Lipschitz continuous on their respective spaces.
  • Convergence: The generated sequences converge to a point z ∈ V ∩ SOL(D, h) under the algorithm’s parameter conditions.The relaxation sequence is constrained to [c,d] ⊂ (0,1), while another sequence lies in [a,b] ⊂ (0,1/κ), with κ = min{κ1,κ2}.
  • Implementation: Translating the product-space method back to H1 and H2 is straightforward for projections onto D but may require computing the projection onto V.In finite dimensions, projection onto the subspace V can be computed using an orthogonal basis.

6 Solving the split variational inequality problem without a product space

The paper also solves the SVIP directly in the original spaces, avoiding product-space reformulation. Under inverse strongly monotone operator assumptions and step-size restrictions, the resulting algorithm converges weakly to a split solution and extends to multiple sets.

  • Direct formulation: The SVIP solution set is Γ := {z ∈ SOL(C,f) | Az ∈ SOL(Q,g)}, and the direct method operates on this set without product-space formulation.The algorithm uses T := P_Q(I − λg) and U := P_C(I − λf).
  • Convergence analysis: Fejér-monotonicity of the generated sequence with respect to Γ is the key intermediate property in the direct convergence proof.The Fejér-monotonicity lemma is used as the basis for the convergence theorem.
  • Convergence result: The direct algorithm converges weakly to a solution x* ∈ Γ when f and g are inverse strongly monotone, Γ is nonempty, and γ ∈ (0,1/L).Here L is the spectral radius of A*A, and λ lies in [0,2α] with α := min{α1,α2}.
  • Multiple-set extension: The same product-space strategy extends the framework to the Multiple Set Split Variational Inequality Problem with simultaneous algorithms.The MSSVIP requires product-space formalism for the presented solution approach.
  • Multiple-set convergence: For the MSSVIP, the generated sequence converges weakly to a solution under the stated inverse-strong-monotonicity, parameter, and nonemptiness assumptions.The convergence theorem applies the two-operator SVIP result in a product-space setting.

7 Applications

The SVIP framework encompasses feasibility, common-solution, split-minimization, and split-zeros problems. It also identifies new split problems and connects their solution conditions to variational inequalities.

  • Feasibility problems: The Split Feasibility Problem and Convex Feasibility Problem appear as special cases of the SVIP.The SFP is obtained by setting f ≡ g ≡ 0, while the CFP is a special case of the SFP.
  • New split problems: The paper introduces the Common Solutions to Variational Inequalities Problem and the Split Zeros Problem as new split problems.The CSVIP uses a family of variational inequalities, while the SZP requires B1(x*) = 0 and B2(Ax*) = 0.
  • Feasibility problems: Viewing the SFP through the SVIP enables finding its minimum-norm solution by choosing f = I and g ≡ 0.This construction is stated to be easily verified within the SVIP formulation.
  • Common solutions: The CSVIP can be transformed into a constrained VIP in a product space using a diagonal set that enforces a common point across components.The diagonal set is Δ := {x ∈ R^{mn} | x = (a,a,…,a), a ∈ R^n}.
  • Split minimization: When f and g are gradients of convex functions, the SVIP becomes a Split Minimization Problem requiring both x* and Ax* to minimize their respective functions.The functions are continuously differentiable and convex on closed and convex sets.
  • Split zeros: The Split Zeros Problem is a special case of the SVIP when A is surjective, and under the stated equivalence conditions SVIP solutions satisfy B1(x*) = 0 and B2(Ax*) = 0.The paper also gives conditions under which the only solution of an SVIP is a solution of an SZP.
Loading 1009.3780v2…