Source-linked AI summary
An inertial forward-backward-forward primal-dual splitting algorithm for solving monotone inclusion problems
Radu Ioan Bot, Ernö Robert Csetnek
TL;DR
The paper addresses monotone inclusion problems involving a maximally monotone operator, a monotone Lipschitzian operator, and more complex linearly composed or parallel-sum structures. It develops an inertial forward-backward-forward method and a product-space primal-dual extension, then applies them to convex optimization problems with matching primal-dual optimality conditions. Under a stated regularity condition, those optimality conditions are also necessary, and strong convexity yields a unique primal solution.
Problem
The paper targets monotone inclusions with mixtures of linearly composed and parallel-sum operators, including settings where forward-backward methods cannot apply because monotone Lipschitzian operators may not be cocoercive.
Method
The paper introduces an inertial forward-backward-forward splitting method, extends it through a product-space primal-dual construction, and applies the resulting schemes to convex optimization pairs.
Results
The proposed schemes provide convergence results for the inclusion problems and yield primal-dual optimality conditions whose optimal objective values coincide for the convex optimization pair.
Takeaways & Limitations
The framework separately accesses operators through forward or backward evaluations while covering complex primal-dual inclusion and convex optimization structures.
Takeaways & Limitations
For convex optimization, necessity of the optimality conditions requires a regularity condition, with sufficient examples involving full domains or relative-interior assumptions.
Abstract
from arXiv · showhide
We introduce and investigate the convergence properties of an inertial forward-backward-forward splitting algorithm for approaching the set of zeros of the sum of a maximally monotone operator and a single-valued monotone and Lipschitzian operator. By making use of the product space approach, we expand it to the solving of inclusion problems involving mixtures of linearly composed and parallel-sum type monotone operators. We obtain in this way an inertial forward-backward-forward primal-dual splitting algorithm having as main characteristic the fact that in the iterative scheme all operators are accessed separately either via forward or via backward evaluations. We present also the variational case when one is interested in the solving of a primal-dual pair of convex optimization problems with intricate objective functions.
1 Introduction and preliminaries
The paper motivates inertial splitting methods for monotone inclusions and introduces forward-backward-forward and primal-dual directions that separately evaluate operators. It also establishes the operator-theoretic and convergence foundations used later.
- Monotone inclusion problems involving mixtures of monotone operators remain broadly relevant because of their applicability across applied mathematics.
- Inertial proximal methods use the last two iterates and generalize the classical proximal-point algorithm.
- Inertial forward-backward methods evaluate a set-valued operator through its resolvent and a single-valued cocoercive operator through a forward step.
- The paper’s first major aim is an inertial forward-backward-forward algorithm for zeros of a maximally monotone operator plus a monotone Lipschitzian operator.
- Primal-dual splitting extends this approach to mixtures of linearly composed and parallel-sum operators while evaluating each operator separately by forward or backward steps.
- The paper develops operator preliminaries, recalls convergence results, and applies the proposed schemes to primal-dual convex optimization problems.
2 An inertial forward-backward-forward splitting algorithm
This section formulates an inertial forward-backward-forward scheme for a maximally monotone operator and a monotone Lipschitzian operator, then proves weak convergence under stated parameter and regularity conditions. The analysis also identifies special cases that recover or extend established algorithms.
- Algorithm and convergence: Theorem 4 considers a maximally monotone A, a monotone β-Lipschitzian B, and a nonempty zero set zer(A + B).
- Convergence analysis: Under the stated bounds on α1, α2, σ, and λn, the constructed Lyapunov-type sequence is nonincreasing and successive differences are summable.
- Algorithm and convergence: The inertial scheme uses two nondecreasing parameter sequences α1,n and α2,n, initialized at zero and bounded by α1 and α2.
- Convergence analysis: The iterates converge weakly to a point in zer(A + B), while stronger convergence follows under demiregularity or uniform monotonicity conditions.
- Remarks and special cases: The theorem permits alternative initialization and parameter conditions, including x0 = x1 instead of α1,1 = α2,1 = 0.
- Remarks and special cases: Setting α1 = 0 recovers the classical error-free Tseng forward-backward-forward scheme, while B = 0 yields a proximal-point extension.
3 Solving monotone inclusion problems involving mixtures of linearly composed and parallel-sum type operators
The section reformulates complex primal-dual monotone inclusion problems in a product space and applies the inertial forward-backward-forward algorithm to solve them concomitantly. Under stated parameter and monotonicity conditions, zeros of the product-space operator correspond to primal-dual solutions, with additional convergence conclusions under uniform monotonicity.
- Problem setting: The framework targets primal inclusions combining linearly composed and parallel-sum type monotone operators with a corresponding Attouch-Théra-type dual problem.The setting includes a maximally monotone operator, a monotone Lipschitzian operator, and multiple auxiliary Hilbert spaces and operators.
- Algorithm and conditions: The resulting inertial iteration uses separate forward and backward evaluations for the component operators, with inertial parameters and step sizes constrained by explicit bounds.The theorem assumes nondecreasing inertial sequences beginning at zero and a bound involving α1, α2, σ, and λ.
- Convergence consequences: Uniform monotonicity of A + C or of selected dual operator combinations yields stronger convergence conclusions for the corresponding iterates or residuals.The section derives these conclusions through the theorem’s uniform-monotonicity alternatives and associated inequalities.
- Product-space reformulation: The product-space construction applies the inertial forward-backward-forward algorithm to the combined operators M and Q.The proof establishes that M is maximally monotone and Q is monotone and Lipschitzian, matching the hypotheses of the base theorem.
- Primal-dual correspondence: A zero of M + Q is equivalent to a primal-dual solution of the structured inclusion problem.This equivalence links the product-space algorithmic fixed-point formulation to the original primal-dual problem.
4 Convex optimization problems
This section applies the inertial forward-backward-forward primal-dual algorithm to a primal-dual pair of convex optimization problems with composite and infimal-convolution terms. Under regularity and parameter conditions, the resulting optimality system characterizes primal-dual solutions and supports convergence guarantees.
- Problem formulation: The optimization model includes infimal convolutions and linear compositions, allowing objective functions with intricate composite structure.Infimal convolution is defined through an auxiliary minimization over decompositions of its argument.
- Problem formulation: The paper formulates primal and Fenchel-type dual problems using proper convex lower-semicontinuous functions, a smooth convex term, strongly convex conjugate-related terms, and linear operators.The associated monotone inclusion and dual inclusion are expressed through subdifferentials and gradients.
- Operator formulation: The paper maps the optimization model to monotone operators by setting A = ∂f, C = ∇h, B_i = ∂g_i, and D_i = ∂l_i.This operator representation connects the primal-dual optimization problems to the splitting framework.
- Optimality conditions: A primal-dual zero of the associated monotone inclusion is equivalent to a primal-dual solution of the optimization problem.The optimality conditions identify primal optimality, dual optimality, and coincidence of the two optimal objective values.
- Optimality conditions: The equivalence between optimality conditions and primal-dual solutions requires a regularity condition for necessity, with sufficient qualification conditions given through domains and relative interiors.The paper discusses strong quasi-relative interior conditions and finite-dimensional relative-interior alternatives.
- Algorithm and convergence: The inertial primal-dual iteration is guaranteed under bounded nondecreasing inertial parameters and step sizes satisfying the stated constraint, while additional uniform convexity can strengthen convergence.The paper also gives a coercivity-based condition ensuring existence of primal solutions when the problem is feasible.