Source-linked AI summary
A Monotone+Skew Splitting Model for Composite Monotone Inclusions in Duality
L. Briceno-Arias, P. L. Combettes
TL;DR
The paper tackles simultaneous solution of composite monotone inclusions and their duals, a setting where existing splitting methods face restrictive operator and resolvent requirements. It reformulates the problems as zeros of a maximally monotone operator plus a linear skew-adjoint operator, derives fully decomposed primal-dual algorithms, and establishes convergence results. The framework also supports applications to composite variational problems, though one implementation may require two operator inversions per iteration.
Problem
Composite monotone inclusion problems often involve an operator composed with a linear map and its adjoint, while existing splitting methods have stringent requirements for primal-dual solution.
Method
The paper reformulates the primal-dual problem as finding a zero of a maximally monotone operator plus a bounded linear skew-adjoint operator, then applies forward-backward-forward splitting with separate operator activations.
Results
The framework yields primal-dual splitting algorithms with established convergence results and applies to composite variational problems and sums of composite functions.
Takeaways & Limitations
The approach provides a fully decomposed way to solve the primal and dual inclusions simultaneously using A, B, and L separately at each iteration.
Takeaways & Limitations
The monotone-plus-skew resolvent implementation may require inversion of two operators at each iteration, which can be numerically demanding.
Abstract
from arXiv · showhide
The principle underlying this paper is the basic observation that the problem of simultaneously solving a large class of composite monotone inclusions and their duals can be reduced to that of finding a zero of the sum of a maximally monotone operator and a linear skew-adjoint operator. An algorithmic framework is developed for solving this generic problem in a Hilbert space setting. New primal-dual splitting algorithms are derived from this framework for inclusions involving composite monotone operators, and convergence results are established. These algorithms draw their simplicity and efficacy from the fact that they operate in a fully decomposed fashion in the sense that the monotone operators and the linear transformations involved are activated separately at each iteration. Comparisons with existing methods are made and applications to composite variational problems are demonstrated.
1 Introduction
The paper addresses composite monotone inclusions together with their duals by reformulating them as a monotone-plus-skew zero problem. It develops fully decomposed primal-dual splitting algorithms and applies them to variational problems.
- Many problems in optimization, variational inequalities, and related fields reduce to inclusions involving monotone set-valued operators in Hilbert spaces.
- The central setting uses maximally monotone operators A and B, a bounded linear map L, and primal and dual inclusions solved together.
- The framework covers Fenchel-Rockafellar duality and yields proximal splitting schemes for primal-dual variational problems and sums of composite functions.
- Existing splitting methods are restricted because composite operators may not be maximally monotone and their resolvents generally lack a convenient expression through L and B.
- The proposed reformulation places the problem in a product Hilbert space using a maximally monotone operator M and a bounded linear skew-adjoint transformation S.
- The resulting forward-backward-forward framework performs explicit steps on S, an implicit step on M, and separately activates A, B, and the linear transformations.
2 Preliminary results
The preliminary results establish convergence properties for an inexact forward-backward-forward method and verify the monotone-plus-skew model's operator structure and primal-dual equivalence.
- The inexact algorithm uses forward evaluations, a resolvent step, and implementation-error sequences that are assumed absolutely summable.
- Under maximal monotonicity, monotonicity, Lipschitz continuity, and nonempty-zero assumptions, the method has weak convergence guarantees.
- Strong convergence follows under additional conditions such as demiregularity or uniform monotonicity of A, B, or their sum.
- The monotone+skew model: The product-space operator M is maximally monotone, while S is bounded, skew-adjoint, and satisfies ∥S∥ = ∥L∥.
- The monotone+skew model: Consequently, M + S is maximally monotone, allowing the convergence theorem to apply to the monotone-plus-skew formulation.
- The monotone+skew model: The resolvent implementation can require inversion of two operators at every iteration, which may be numerically demanding.
- Primal-dual equivalence: The primal, dual, and product-space zero problems are equivalent in solvability, and zeros of M + S form a closed convex subset of P × D.
3 Main results
The paper applies a monotone-plus-skew splitting framework to derive primal-dual algorithms for composite inclusions. The resulting methods separately activate the operators and linear transformations, support parallel operator evaluations, and provide convergence under stated monotonicity conditions.
- Framework: The main algorithm obtains primal and dual solutions by applying a splitting theorem to a maximally monotone operator plus a skew linear transformation.The construction yields solutions to the composite primal-dual problem through the reformulated inclusion.
- Algorithmic structure: The algorithm uses A, B, and L separately, with A and B activatable in parallel and all L-related steps explicit.This decomposition is the central implementation property of the main result.
- Algorithmic structure: The primal-dual iteration updates the primal and dual variables through resolvent evaluations of A and B^-1 and explicit applications of L and L^*.The displayed iteration includes errors represented by absolutely summable perturbation sequences.
- Convergence: Under the theorem’s assumptions, the iterates converge weakly to primal and dual solutions, with stronger convergence for components covered by uniform or strong monotonicity assumptions.The reported convergence statements include weak convergence of dual variables and strong convergence in the corresponding monotone cases.
- Special cases: For the two-operator specialization, the method uses resolvents of both maximally monotone operators and provides an alternative to Douglas-Rachford splitting.The comparison is stated for finding a zero of the sum of two maximally monotone operators.
- Multiple operators: For multiple composite operators, the resulting algorithm activates the operators B_i in parallel and independently from the transformations L_i.The construction uses a product-space Hilbert-space formulation with weighted inner products.
4 Variational problems
The paper applies its splitting framework to Fenchel–Rockafellar problems and composite minimization, yielding decomposed primal-dual algorithms with convergence guarantees under stated assumptions.
- Fenchel–Rockafellar framework: The variational section applies earlier monotone-inclusion results to minimization problems involving lower semicontinuous convex functions.The framework uses subdifferentials and proximal operators to connect inclusions with primal and dual minimization problems.
- Fenchel–Rockafellar framework: The primal inclusion corresponds to minimizing f − ⟨· | z⟩ + g ◦ (L · − r), while the dual inclusion corresponds to minimizing f* ◦ (z − L* ·) + g* + ⟨r | ·⟩.The inclusion-to-minimization relations are stated separately for the primal and dual formulations.
- Primal-dual algorithm: A new primal-dual splitting method separately activates the proximity operators of f and g* and the linear operator L, while allowing implementation errors represented by absolutely summable sequences.The iteration uses forward steps involving L and L*, proximal steps for f and g*, and error terms in the updates.
- Primal-dual algorithm: Under the stated qualification and existence conditions, the resulting iterates converge to solutions of the primal-dual problem.The propositions state convergence to a primal solution and corresponding dual solution, with stronger convergence under uniform convexity assumptions.
- Composite functions: The framework extends to sums of m composite functions by introducing separate Hilbert spaces, weights, operators L_i, and dual variables v_i.The composite algorithm uses β = max_i ∥L_i∥, weighted primal updates, and separate operator evaluations for each component.
- Composite functions: For the composite-function scheme, the primal and dual sequences converge weakly, with strong convergence of each dual sequence under the stated strong-convexity condition.The proposition reports weak convergence of x_i,n and v_i,n and strong convergence of v_i,n when the relevant conjugate functions are strongly convex.