A new splitting method for solving composite monotone inclusions involving parallel-sum operators

Quoc Tran-Dinh, Bằng Công VũarXiv 2015 · DOI · arXiv

TL;DR

This paper introduces a novel "fully splitting" primal-dual algorithm for a complex class of mathematical optimization problems called composite monotone inclusions. This new method is more efficient and general than existing approaches because it can handle operators that are "parallel sums" and only requires individual, rather than combined, operator computations at each step, leading to a guaranteed convergence to a solution.

What Problem Does This Paper Address?

The paper tackles a challenging problem in convex analysis and optimization: solving composite monotone inclusions. These are mathematical equations that arise in various fields like variational inequalities, convex optimization, and signal processing. The specific form of the inclusion studied is $0 \in Ax + L^*(B \Box D)(Lx) + C(x)$, where $A, B, D$ are maximally monotone operators, $C$ is a monotone Lipschitzian operator, $L$ is a linear operator, and $B \Box D$ represents the "parallel sum" of operators $B$ and $D$. Existing methods often struggle with the parallel sum operator, requiring its computation, which can be intractable. Furthermore, many methods require computing operators in combination, limiting their applicability and efficiency. This paper aims to develop a method that avoids these limitations by treating each operator individually.

Methods

The core contribution is a new primal-dual splitting algorithm. The approach is "fully splitting" in the sense that it uses the resolvent of individual monotone operators ($A$ and $B$) and the values of the single-valued operators ($C$ and $D^{-1}$) separately. This is a significant departure from prior work that often required computing the resolvent of combined operators (like $A+C$ or $B \Box D$).

The algorithm is built upon the concept of a "Kuhn-Tucker set," which links the primal and dual versions of the inclusion problem. The method iteratively generates a sequence of points that approximate a feasible point within this set. The algorithm's update steps involve computing individual resolvents and operator values, followed by a projected update. The paper provides a detailed algorithmic description (Algorithm 2) and proves its weak convergence under specific conditions on the step sizes.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • "Fully Splitting" is Key: The most significant insight is the development of a "fully splitting" algorithm. This means that at each iteration, the algorithm only needs to compute the resolvent of individual monotone operators ($A$ and $B$) and evaluate the Lipschitzian operators ($C$ and $D^{-1}$) separately. This avoids the computational burden of dealing with combined operators like $A+C$ or the parallel sum $B \Box D$.
  • Primal-Dual Approach: By considering both the primal and dual formulations of the inclusion problem simultaneously, the algorithm can leverage the structure of the problem more effectively and achieve convergence.
  • Kuhn-Tucker Set as a Target: The algorithm's convergence is analyzed with respect to the Kuhn-Tucker set, which represents the set of primal-dual solutions. This provides a clear target for the iterative process.
  • Generalization: The proposed method extends existing frameworks to a more general class of monotone inclusions, particularly those involving parallel-sum operators, which were previously difficult to handle.
  • Independence from Linear Operator Norm: A crucial practical advantage is that the step-size parameters do not depend on the norm of the linear operator $L$. This is important because $L$ can be large in many applications, and its norm can be difficult to estimate or bound.

Key Results

The paper presents a new primal-dual splitting algorithm (Algorithm 2) for solving composite monotone inclusions. The main theoretical result is the proof of the weak convergence of this algorithm to a primal-dual solution of the inclusion problem under certain conditions on the step sizes and the problem's parameters.

As a byproduct, the algorithm can be specialized to solve composite convex minimization problems. In this context, it utilizes the proximal operator of each objective component independently, allowing for parallel computation and exploiting the separable structure of such problems. The paper also provides a concrete example of this specialization in Algorithm 3 for a class of structured convex optimization problems.

Limitations and Future Work

  • Weak Convergence: The primary convergence guarantee is weak convergence. While this is a standard result for many iterative algorithms in this field, strong convergence would be a desirable future direction.
  • Parameter Selection: The convergence of the algorithm depends on the choice of certain parameters (e.g., $\epsilon$, $\gamma_n$, $\mu_n$, $\lambda_n$). While the paper provides conditions for these parameters, finding optimal or adaptive strategies for their selection could be an area for future research.
  • Extension to Systems: The authors mention that extending the framework to systems of monotone inclusions (as studied in [12]) is straightforward. This suggests future work could explore these extensions more deeply.
  • New Variants: The paper notes that new variants of Algorithm 2 can be derived for problems in [4, Problem 1.2] and [14, Problem 1.1] as a direct application, indicating potential for further algorithmic development.

Summary updated

Abstract

We propose a new primal-dual splitting method for solving composite inclusions involving Lipschitzian, and parallel-sum-type monotone operators. Our approach extends the framework in \cite{Siopt4} to a more general class of monotone inclusions in a nontrivial fashion. The main idea is to represent the solution set of both the primal and dual problems using their associated Kuhn-Tucker set, and then develop a projected method to successively approximate a feasible point of the Kuhn-Tucker set. We propose a splitting algorithm based on the resolvent of each maximally monotone operator to construct a primal-dual sequence that weakly converges to a solution of the original problem. The key feature of our method is that it only employes the resolvent of each monotone operator separately, which is different from existing methods in the literature. As a byproduct, our algorithm can be specialized to solve composite convex minimization problems that uses the proximal-operator of each objective component independently, and is equipped with a weakly convergence guarantee.
BibTeX
@misc{trandinh2015new,
  author = {Quoc Tran-Dinh and Bằng Công Vũ},
  title = {{A new splitting method for solving composite monotone inclusions involving parallel-sum operators}},
  year = {2015},
  eprint = {1505.07946},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1505.07946},
}
Figure