Source-linked AI summary
Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum monotone operators
Patrick L. Combettes, Jean-Christophe Pesquet
TL;DR
The paper addresses monotone inclusions whose existing approaches require generally intractable resolvent computations. It proposes a fully split, highly parallel algorithm that processes operators separately and establishes convergence-related guarantees, with applications to convex minimization.
Problem
Existing primal-dual methods may require resolvents of combined operators that are usually intractable, limiting direct numerical reduction of the problem.
Method
The paper proposes a fully split primal-dual algorithm that processes single-valued operators explicitly, set-valued operators through resolvents, and most steps in parallel.
Results
The main result provides summability guarantees for the algorithm's iterates under stated monotonicity and Lipschitzian assumptions.
Takeaways & Limitations
The method extends splitting algorithms to a broader class of problems and has potential applications including convex minimization, partial differential equations, mechanics, and variational inequalities.
Takeaways & Limitations
The motivating existing algorithm requires resolvents of A + C and combined inverse operators, which are usually intractable in practice.
Abstract
from arXiv · showhide
We propose a primal-dual splitting algorithm for solving monotone inclusions involving a mixture of sums, linear compositions, and parallel sums of set-valued and Lipschitzian operators. An important feature of the algorithm is that the Lipschitzian operators present in the formulation can be processed individually via explicit steps, while the set-valued operators are processed individually via their resolvents. In addition, the algorithm is highly parallel in that most of its steps can be executed simultaneously. This work brings together and notably extends various types of structured monotone inclusion problems and their solution methods. The application to convex minimization problems is given special attention.
1 Introduction
The paper formulates a broad structured monotone-inclusion problem and proposes a fully split, highly parallel primal-dual algorithm that separately processes its component operators. The framework encompasses several existing duality and minimization formulations while addressing resolvent computations that are usually intractable.
- Problem formulation: Problem 1.1 combines maximally monotone, Lipschitzian, linear-composition, and parallel-sum operators in primal and dual inclusions.The formulation uses Hilbert spaces, a maximally monotone A, a monotone Lipschitzian C, and operator pairs linked through bounded linear maps.
- Scope and connections: Problem 1.1 captures and extends various existing problem formulations, including several duality and convex minimization settings.The examples recover previously studied frameworks through special choices of the operators and spaces.
- Motivation: The prior primal-dual alternative requires resolvents of A + C and related operators, which are usually intractable.Even the simple zero-finding case motivates splitting methods that avoid directly computing the resolvent of A + C.
- Algorithmic contribution: The proposed method activates A, the linear maps, the inverse Lipschitzian operators, the parallel-sum components, and C separately.This fully split design avoids treating the entire structured operator as a single resolvent-bearing object.
- Algorithmic contribution: The algorithm uses explicit steps for single-valued operators, resolvent-based implicit steps for set-valued operators, and simultaneous activation of many operations.The paper emphasizes that explicit steps are typically easier to implement than implicit steps.
2 Notation and background
This section establishes Hilbert-space notation and foundational concepts from monotone operator theory and convex analysis. It defines operator properties, resolvents, parallel sums, convex conjugates, subdifferentials, proximal mappings, and related convexity and interior notions.
- Hilbert-space notation: The paper uses real Hilbert spaces with scalar products, norms, weak and strong convergence notation, and direct sums of the spaces G_i.The direct sum is equipped with the product-space norm.
- Monotone operators: It introduces set-valued operators through their graphs, ranges, inverses, resolvents, monotonicity, and maximal monotonicity.Monotonicity is expressed by a nonnegative scalar-product condition on pairs of graph points.
- Convex analysis: The background defines parallel sums, lower semicontinuous convex functions, conjugates, subdifferentials, proximal mappings, infimal convolutions, and strong or relative interiors.It also states uniform monotonicity and uniform convexity through scalar-product and function inequalities.
3 Main result
The main theorem presents a fully split, error-tolerant forward-backward-forward algorithm for the structured monotone inclusion framework and characterizes its convergence. The method separately processes the problem’s operators, permits parallel elementary updates, and yields weak or conditionally strong convergence results.
- Algorithm and convergence: Theorem 3.1 establishes the new splitting algorithm and describes its asymptotic behavior under the stated assumptions.The formulation uses absolutely summable error sequences and step sizes bounded in terms of the Lipschitz constant β.
- Convergence guarantees: The theorem provides weak convergence in general, while strong convergence is obtained under uniform monotonicity assumptions on selected operators.Uniform monotonicity of A, C, or a suitable B_i-related inverse operator supports strong convergence of the corresponding components.
- Operator decomposition: The proof rewrites the primal-dual inclusion as finding a zero of M + Q, with M maximally monotone and Q monotone and β-Lipschitzian.This decomposition enables application of the forward-backward-forward splitting framework.
- Algorithm and convergence: The iteration applies forward evaluations of the monotone-Lipschitz component Q, a resolvent step for M, and an error-tolerant update.Its displayed form is y_n = x_n − γ_n(Qx_n + a_n), p_n = J_γnM y_n + b_n, q_n = p_n − γ_n(Qp_n + c_n), and x_n+1 = x_n − y_n + q_n.
- Convergence guarantees: The generated iterates satisfy summability and asymptotic regularity properties, including ∑_n∥x_n − p_n∥^2 < +∞ and vanishing component discrepancies.For every i, y2,i,n − e y2,i,n → 0 and p2,i,n − e p2,i,n → 0.
- Algorithm structure: The algorithm fully splits the operators, uses explicit steps for single-valued terms and resolvents for set-valued terms, and allows most elementary steps to run in parallel.Summable error sequences relax the requirement of exact operator evaluations during the iterations.
4 Minimization problems
The paper specializes its monotone-inclusion framework to convex minimization, covering composite objectives with smooth terms, linear operators, and strongly convex regularizers. The resulting algorithm yields primal-dual solutions and convergence properties under stated assumptions, with stronger convergence under uniform convexity conditions.
- Problem 4.1 models convex minimization with f and gi in Γ0, a convex differentiable h with µ-Lipschitzian gradient, strongly convex ℓi, and bounded linear Li.
- Theorem 4.2 is presented as an offspring of Theorem 3.1 and establishes existence and convergence results for the minimization formulation.
- The algorithm uses proximal evaluation for f, including p1,n = proxγnf(y1,n + γnz) + b1,n, and its residuals satisfy a finite summed-square condition.
- Uniform convexity of f or h, or of a suitable gi, yields the corresponding strong-convergence claims through uniform monotonicity of the associated subdifferentials.
- The specialization identifies A = ∂f, C = ∇h, Bi = ∂gi, and Di = ∂ℓi, transferring the general splitting theorem to the minimization setting.
- Several constraint qualifications ensure the primal-dual relationship, including relative-interior conditions, real-valuedness, or finite-dimensional relative-interior assumptions.
- Even when each ℓi is the indicator of {0}, the resulting algorithm remains new, including the further special case h = 0.