Inducing strong convergence of trajectories in dynamical systems associated to monotone inclusions with composite structure.

Radu Ioan Bot, Sorin-Mihai Grad, Dennis Meier, Mathias StaudiglAdvances 2019 · DOI · OpenReview

TL;DR

This paper introduces novel dynamical systems that guarantee strong convergence of their trajectories to the minimum norm solution of complex optimization problems involving sums of monotone operators. By employing Tikhonov regularization, these systems overcome limitations of existing methods that only achieve weak convergence, offering a more robust approach to solving challenging inclusion and equilibrium problems.

What Problem Does This Paper Address?

Many real-world problems in optimization, control, and signal processing can be formulated as finding solutions to monotone inclusion problems. These problems often involve the sum of multiple "monotone operators," which are mathematical functions with specific properties that ensure well-behaved solutions. A key challenge is that traditional dynamical systems designed to solve these problems often only guarantee "weak convergence" of their trajectories. This means the trajectories get close to a solution, but not necessarily to a specific, desirable one, and the convergence can be slow or indirect. Furthermore, finding the "minimum norm solution" (the solution closest to the origin) is often a crucial requirement, which weak convergence alone doesn't guarantee. This paper addresses this by developing new dynamical systems that achieve "strong convergence" (trajectories get arbitrarily close to a solution) and specifically target the minimum norm solution.

Methods

The core innovation lies in the use of Tikhonov regularization. This technique involves adding a small, carefully chosen perturbation to the original problem or its associated dynamical system. The authors explore two main strategies:

  1. Outer Tikhonov Regularization: Perturbing the entire dynamical system's vector field.
  2. Inner Tikhonov Regularization: Perturbing specific components of the dynamical system, such as individual operators.

They apply these regularization techniques to several classes of dynamical systems:

  • Krasnoselskii-Mann type systems: Used for finding fixed points of nonexpansive mappings.
  • Forward-Backward (FB) systems: Designed for problems involving sums of monotone and cocoercive operators.
  • Forward-Backward-Forward (FBF) systems: A more general framework for composite monotone inclusion problems.

The theoretical backbone of their analysis relies on established results in dynamical systems theory, particularly concerning the existence and uniqueness of solutions and their asymptotic behavior. They leverage tools like the resolvent of monotone operators and properties of averaged mappings.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical illustrations rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Tikhonov regularization as a bridge to strong convergence: The most significant insight is demonstrating how a seemingly small perturbation (Tikhonov regularization) can dramatically improve the convergence properties of dynamical systems, transforming weak convergence into strong convergence.
  • Targeting the minimum norm solution: The regularization is not just about achieving strong convergence, but specifically guiding trajectories towards the minimum norm solution, which is often the most desirable solution in practical applications.
  • Complementary regularization strategies: The paper highlights that both "outer" and "inner" regularization approaches can be effective, but they can lead to different dynamics and convergence behaviors, offering flexibility in problem-solving.
  • Unified framework for diverse systems: The techniques are shown to be applicable to a range of dynamical systems (Krasnoselskii-Mann, FB, FBF), suggesting a generalizable approach to improving convergence in monotone inclusion problems.

Key Results

The paper establishes theoretical guarantees for the strong convergence of trajectories for several classes of Tikhonov-regularized dynamical systems. Specifically:

  • Krasnoselskii-Mann systems: Trajectories converge strongly to the minimum norm fixed point of a nonexpansive operator.
  • Forward-Backward systems: Trajectories converge strongly to the minimum norm solution of a monotone inclusion problem involving the sum of a maximally monotone operator and a cocoercive operator.
  • Forward-Backward-Forward systems: Trajectories converge strongly to the minimum norm solution of a monotone inclusion problem involving the sum of a maximally monotone operator and a Lipschitz continuous operator.

Numerical experiments are presented that visually confirm these theoretical results, demonstrating how regularization smooths out oscillations and accelerates convergence compared to unregularized systems. The figures illustrate that regularized systems converge to the minimum norm solution (often the origin), while unregularized systems may converge to other solutions or exhibit slower convergence.

Limitations and Future Work

  • Assumptions on operators: The theoretical results often rely on specific properties of the involved operators (e.g., maximally monotone, cocoercive, Lipschitz continuous). Extending these results to more general classes of operators would be valuable.
  • Parameter tuning: While Tikhonov regularization is shown to be effective, the choice of regularization parameters (e.g., $\epsilon(t)$, $\lambda(t)$, $\gamma(t)$) can influence the convergence speed and behavior. The paper provides some guidance but further research into optimal parameter selection could be beneficial.
  • Generalization to other system types: The paper focuses on specific types of dynamical systems. Exploring the application of Tikhonov regularization to other dynamical systems used in optimization and control could be a fruitful direction.
  • Computational efficiency: While strong convergence is achieved, the computational cost of implementing these regularized systems might be higher than their unregularized counterparts. Investigating efficient numerical schemes for these systems is a potential area for future work.

Summary updated

Abstract

In this work we investigate dynamical systems designed to approach the solution sets of inclusion problems involving the sum of two maximally monotone operators. Our aim is to design methods which guarantee strong convergence of trajectories towards the minimum norm solution of the underlying monotone inclusion problem. To that end, we investigate in detail the asymptotic behavior of dynamical systems perturbed by a Tikhonov regularization where either the maximally monotone operators themselves, or the vector field of the dynamical system is regularized. In both cases we prove strong convergence of the trajectories towards minimum norm solutions to an underlying monotone inclusion problem, and we illustrate numerically qualitative differences between these two complementary regularization strategies. The so-constructed dynamical systems are either of Krasnoselskii-Mann, of forward-backward type or of forward-backward-forward type, and with the help of injected regularization we demonstrate seminal results on the strong convergence of Hilbert space valued evolutions designed to solve monotone inclusion and equilibrium problems.
BibTeX
@inproceedings{bot2019inducing,
  author = {Radu Ioan Bot and Sorin-Mihai Grad and Dennis Meier and Mathias Staudigl},
  title = {{Inducing strong convergence of trajectories in dynamical systems associated to monotone inclusions with composite structure.}},
  booktitle = {Advances},
  year = {2019},
  doi = {10.1515/anona-2020-0143},
}
Figure