Source-linked AI summary
Second order forward-backward dynamical systems for monotone inclusion problems
Radu Ioan Bot, Ernö Robert Csetnek
TL;DR
The paper studies convergence for second-order dynamical systems with time-dependent damping and relaxation, motivated by heavy-ball optimization. It extends the approach to forward-backward dynamics for monotone inclusions and establishes trajectory and ergodic function-value convergence results.
Problem
The paper examines how second-order optimization dynamics can be analyzed for convergence, including systems with time-dependent damping and relaxation and monotone inclusion problems.
Source: §1 · pp. 1–2, §4 · p. 9Method
Results
Takeaways & Limitations
The framework covers minimization of a nonsmooth convex function plus a smooth convex function, and its explicit discretization gives a relaxed forward-backward algorithm with inertial effects.
Source: §1 · p. 2Under assumption (A6), the result gives convergence of the function value along the ergodic trajectory; weak convergence of the trajectory to a minimizer additionally requires (A1).
Source: §4 · p. 18
Abstract
from arXiv · showhide
We begin by considering second order dynamical systems of the from $\ddot x(t) + \gamma(t)\dot x(t) + \lambda(t)B(x(t))=0$, where $B: {\cal H}\rightarrow{\cal H}$ is a cocoercive operator defined on a real Hilbert space ${\cal H}$, $\lambda:[0,+\infty)\rightarrow [0,+\infty)$ is a relaxation function and $\gamma:[0,+\infty)\rightarrow [0,+\infty)$ a damping function, both depending on time. For the generated trajectories, we show existence and uniqueness of the generated trajectories as well as their weak asymptotic convergence to a zero of the operator $B$. The framework allows to address from similar perspectives second order dynamical systems associated with the problem of finding zeros of the sum of a maximally monotone operator and a cocoercive one. This captures as particular case the minimization of the sum of a nonsmooth convex function with a smooth convex one. Furthermore, we prove that when $B$ is the gradient of a smooth convex function the value of the latter converges along the ergodic trajectory to its minimal value with a rate of ${\cal O}(1/t)$.
1 Introduction and preliminaries
The paper develops second-order optimization dynamics from the heavy-ball model, then extends the framework to time-dependent systems and forward-backward dynamics for monotone inclusions. It states existence, uniqueness, and convergence results, and connects the continuous systems to inertial algorithms.
1 Introduction and preliminaries
- The heavy-ball system models a damped nonlinear oscillator moving over a convex potential, while related work studies trajectory and function-value convergence and inertial discretizations.The introduction also situates the work alongside constrained gradient-projection systems and a nonexpansive-operator system.Source: §1 · pp. 1–2
- For a cocoercive operator, the paper studies a second-order system with time-dependent relaxation and damping and proves existence, uniqueness, and weak convergence to a zero under mild assumptions.The weak convergence result requires the zero set of the operator to be nonempty.Source: §1 · p. 2
- The framework also treats zeros of a maximally monotone operator plus a cocoercive operator through a resolvent-based second-order forward-backward system.This includes minimizing the sum of a nonsmooth convex function and a smooth convex function.Source: §1 · p. 2
- When the cocoercive operator is a smooth convex function's gradient, its value along the ergodic trajectory converges to its minimum at O(1/t).Source: §1 · p. 2
- Explicit discretization of the second-order forward-backward system yields a relaxed forward-backward algorithm with inertial effects.The authors expect the continuous perspective to inform choices of relaxation and damping parameters in iterative schemes.Source: §1 · p. 2
2 Existence and uniqueness of strong global solutions
This section establishes global existence and uniqueness for the second-order system with a Lipschitz operator and locally integrable time-dependent coefficients. The proof reduces it to a first-order system and applies the Cauchy-Lipschitz-Picard theorem.
2 Existence and uniqueness of strong global solutions
- For an absolutely continuous trajectory, composing with the Lipschitz operator B preserves absolute continuity, with the derivative bounded by L times the trajectory's derivative almost everywhere.Absolute continuity here is characterized by an integrable derivative and the corresponding integration formula.Source: §2 · p. 3
- A strong global solution has locally absolutely continuous position and velocity, satisfies the equation almost everywhere, and takes the prescribed initial position and velocity.Source: §2 · p. 3
- The proof rewrites the second-order dynamics as a first-order system in the product space H × H and applies the Cauchy-Lipschitz-Picard theorem.The locally integrable coefficients make the first-order vector field satisfy the theorem's conditions.Source: §2 · pp. 3–4
- For an L-Lipschitz operator and nonnegative measurable λ and γ locally integrable on every finite interval, each initial position and velocity yield a unique strong global solution.Source: §2 · p. 3
3 Convergence of the trajectories
Under the stated assumptions, trajectories for a cocoercive operator with a zero converge weakly to a zero. The section extends this convergence result to nonexpansive and averaged operators.
Convergence proof
- The proof invokes the continuous Opial lemma: distance limits and weak cluster points in the solution set yield weak convergence.The lemma requires distances to every point in the set to have limits and every weak sequential cluster point to belong to that set.Source: §3 · p. 5
Existence and uniqueness
- For initial data u0, v0, (A1) ensures a unique global C2 trajectory for the dynamical system.The convergence analysis also assumes B is β-cocoercive and has a nonempty zero set.Source: §3 · p. 5
Theorem 6
- Theorem 6 gives bounded trajectories with square-integrable velocity, acceleration, and Bx; these quantities tend to zero, and x converges weakly to a zero of B.The result assumes B is β-cocoercive with a nonempty zero set and λ, γ fulfill (A1).Source: §3 · p. 5
Nonexpansive operators
- For nonexpansive T with a nonempty fixed-point set, Corollary 7 gives the same boundedness, vanishing residual and derivatives, and weak convergence to Fix T.This result holds for λ, γ fulfilling (A2).Source: §3 · p. 8
Relation to prior work
- Unlike the constant-parameter setting of [9, Theorem 3.2], Corollary 7 allows time-dependent damping and relaxation.The cited earlier result assumes γ² > 2.Source: §3 · p. 8
Averaged operators
- Corollary 9 extends the trajectory conclusions to α-averaged R with a nonempty fixed-point set, under (A3).The proof reduces this case to Corollary 7 by representing R as (1−α)Id+αT for nonexpansive T.Source: §3 · p. 9
4 Forward-backward second order dynamical systems
This section studies second-order forward-backward dynamics for monotone inclusions and convex minimization, establishing convergence properties and analyzing allowable step sizes and ergodic objective-value rates. It distinguishes objective convergence along the ergodic trajectory under (A6) from weak trajectory convergence under the additional assumption (A1), and identifies relaxation and damping choices that guarantee both.
Theorem 10
- Under A4, for η ∈ (0, 2β), trajectories x(t) converge weakly to a point in Zer(A + B); for every zero x*, B(x(t)) → Bx* and B is constant on Zer(A + B).For every zero x*, B(x(·)) − Bx* is square-integrable.Source: §4 · p. 10
Theorem 10 and Remark 11
- If A or B is uniformly monotone, the trajectory converges strongly to the unique zero of A + B.The theorem’s convergence conclusions also hold at η = 2β.Source: §4 · pp. 10, 12
Corollary 12
- For the solution x(t) of (31), with λ and γ fulfilling (A4), x(t) converges weakly to a minimizer of f + g; if f or g is uniformly convex, it converges strongly to the unique minimizer.For any minimizer x* of f + g, ∇g(x(·)) − ∇g(x*) is square-integrable, and ∇g(x(t)) converges to ∇g(x*).Source: §4 · pp. 12–13
Corollary 14
- Under A5, the minimization conclusions hold for any η > 0, including weak convergence and strong convergence when f or g is uniformly convex.The proof uses a modified energy functional instead of the squared distance to a minimizer.Source: §4 · pp. 13–14
Remark 15
- With constant damping γ and λ = 1, A5 permits γ² > η/β + 1, relaxing the parameter conditions γ² > 2 and 0 < η ≤ 2β considered in.Source: §4 · p. 16
Remark 16
- When γ(t) = γ and λ(t) = 1, discretizing the minimization dynamics yields a relaxed forward-backward algorithm with inertial effects.Source: §4 · p. 16
Ergodic objective-value rate
- The section introduces a convergence-rate result for the objective value of a smooth convex function along the dynamics’ ergodic trajectory.Source: §4 · p. 16
4 Forward-backward second order dynamical systems
- Under (A6), the objective along the ergodic trajectory converges to its global minimum value; this theorem does not establish trajectory convergence.The theorem gives only the ergodic objective convergence result.Source: §4 · pp. 17–18
- Weak convergence of the trajectory to a minimizer follows from Theorem 6 when the relaxation and damping functions also fulfill (A1).The ergodic trajectory then converges weakly to the same minimizer.Source: §4 · p. 18
- For the specified relaxation and damping choices satisfying the stated parameter inequalities, both ergodic objective convergence and weak trajectory convergence to a minimizer are guaranteed.The parameter bounds are given in the passage, but their expressions are not fully legible.Source: §4 · p. 18