PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast convex optimization via inertial dynamics with Hessian driven damping

Hedy Attouch, Juan Peypouquet, Patrick Redont

arXiv:1601.07113v1math.OC

TL;DR

The paper asks how inertial dynamics with vanishing and Hessian-driven damping can accelerate convex minimization. It analyzes the dynamics through Lyapunov and first-order reformulations, obtaining fast objective convergence, trajectory convergence, and extensions to nonsmooth convex functions.

  • Problem

    The paper studies fast minimization and convergence of inertial trajectories for convex objectives, including smooth and nonsmooth settings.

  • Method

    It combines vanishing isotropic and Hessian-driven damping, analyzes Lyapunov functions, and reformulates the dynamics as a first-order system for nonsmooth extension.

  • Results

    For α ≥ 3, objective values converge at O(t^-2) with rapidly vanishing gradients; for α > 3, trajectories converge weakly to minimizers and strongly in several cases.

  • Takeaways & Limitations

    The dynamics provides a continuous-time framework connecting accelerated convex optimization with Newton-type damping and supporting nonsmooth convex objectives.

  • Takeaways & Limitations

    Time discretization and applications to unilateral mechanics and nonlinear oscillators are identified but left outside the paper’s scope.

Abstract

from arXiv · show

We first study the fast minimization properties of the trajectories of the second-order evolution equation $$\ddot{x}(t) + \fracα{t} \dot{x}(t) + β\nabla^2 Φ(x(t))\dot{x} (t) + \nabla Φ(x(t)) = 0,$$ where $Φ:\mathcal H\to\mathbb R$ is a smooth convex function acting on a real Hilbert space $\mathcal H$, and $α$, $β$ are positive parameters. This inertial system combines an isotropic viscous damping which vanishes asymptotically, and a geometrical Hessian driven damping, which makes it naturally related to Newton's and Levenberg-Marquardt methods. For $α\geq 3$, $β>0$, along any trajectory, fast convergence of the values $$Φ(x(t))- \min_{\mathcal H}Φ=\mathcal O\left(t^{-2}\right)$$ is obtained, together with rapid convergence of the gradients $\nablaΦ(x(t))$ to zero. For $α>3$, just assuming that $Φ$ has minimizers, we show that any trajectory converges weakly to a minimizer of $Φ$, and $ Φ(x(t))-\min_{\mathcal H}Φ= o(t^{-2})$. Strong convergence is established in various practical situations. For the strongly convex case, convergence can be arbitrarily fast depending on the choice of $α$. More precisely, we have $Φ(x(t))- \min_{\mathcal H}Φ= \mathcal O(t^{-\frac{2}{3}α})$. We extend the results to the case of a general proper lower-semicontinuous convex function $Φ: \mathcal H \rightarrow \mathbb R \cup \{+\infty \}$. This is based on the fact that the inertial dynamic with Hessian driven damping can be written as a first-order system in time and space. By explicit-implicit time discretization, this opens a gate to new $-$ possibly more rapid $-$ inertial algorithms, expanding the field of FISTA methods for convex structured optimization problems.

Introduction

The paper studies inertial dynamics combining vanishing isotropic damping with Hessian-driven geometric damping, establishing fast optimization and convergence properties while extending the framework toward nonsmooth convex problems.

  • Introduction: The system combines asymptotically vanishing isotropic damping with Hessian-driven geometric damping linked to Newton’s method.The Hessian term gives the dynamics a geometric component beyond homogeneous damping.
  • Introduction: For α ≥ 3 and β > 0, trajectories achieve fast convergence of objective values and gradients converge rapidly to zero.
  • Introduction: For α > 3, trajectories converge weakly to minimizers, with objective error o(t^-2), and strong convergence holds in various practical situations.
  • Introduction: The results extend naturally to nonsmooth convex functions because the dynamics can be reformulated as a first-order system involving only the gradient.
  • Introduction: Time discretization suggests new fast inertial algorithms for structured convex minimization, but algorithm design is left for future research.

1. Smooth potential

This section formulates the smooth-potential problem, establishes global well-posedness, and identifies the main minimizing and convergence properties to be proved.

  • 1. Smooth potential: The analysis assumes α > 0, β > 0, a twice continuously differentiable convex potential, and positive initial time with prescribed position and velocity.
  • 1. Smooth potential: The section studies existence, minimization, fast objective convergence, weak trajectory convergence, and selected cases of strong convergence.
  • 1. Smooth potential: For any Cauchy data, the dynamics admits a unique twice continuously differentiable global solution.
  • 1. Smooth potential: The Lyapunov-function analysis uses a family of Lyapunov functions, whose multiplicity is crucial for proving that the gradient vanishes asymptotically.

1.2. Lyapunov analysis and minimizing properties of the solutions for α > 0.

For α > 0, Lyapunov functions control the dynamics and establish limiting objective behavior, minimizer cluster-point properties, and asymptotic decay of gradients and motion.

  • 1.2. Lyapunov analysis and minimizing properties: For each θ ∈ [0, β], Wθ is identified as a strict Lyapunov function for the dynamics.The construction includes kinetic, objective, and gradient-related terms.
  • 1.2. Lyapunov analysis and minimizing properties: The objective value converges to inf Φ, while W0 and Wβ converge to the same limit.
  • 1.2. Lyapunov analysis and minimizing properties: Every sequential weak cluster point belongs to argmin Φ; if the trajectory remains bounded, minimizers must exist.
  • 1.2. Lyapunov analysis and minimizing properties: When Φ is bounded below, the gradient converges to zero and the velocity vanishes asymptotically.
  • 1.2. Lyapunov analysis and minimizing properties: The analysis can be developed using differentiability of the combined quantity u̇θ rather than separately differentiating ẋ and ∇Φ(x).

1.3. Fast convergence of the values for α ≥3.

For α ≥ 3, Lyapunov estimates yield fast objective convergence and bounded trajectories; for α > 3, the analysis supports faster rates and weak convergence to minimizers.

  • 1.3. Fast convergence of the values for α ≥3: α = 3 is the smallest value for which the paper proves fast convergence results.
  • 1.3. Fast convergence of the values for α ≥3: For α ≥ 3, the Lyapunov function Eλ is nonincreasing for λ ∈ [2, α − 1], and its limit exists.
  • 1.3. Fast convergence of the values for α ≥3: For α ≥ 3 with a minimizer, trajectories are bounded and the objective error has an O(t^-2) estimate.
  • 1.3. Fast convergence of the values for α ≥3: The Lyapunov estimates also give ∥ẋ(t) + β∇Φ(x(t))∥ = O(t^-1).
  • 1.3. Fast convergence of the values for α ≥3: For α > 3, the trajectories converge weakly to points in argmin Φ.

1.4. Weak convergence of the trajectories and faster convergence of the values for α > 3.

For α > 3, trajectories converge weakly to minimizers, while objective values converge faster than t^-2.

  • The analysis derives auxiliary limits and integrability properties that support both weak trajectory convergence and the faster value estimate.
  • The proof uses Opial’s lemma after establishing limits for distances to minimizers and identifying weak cluster points.
  • For α > 3, every trajectory converges weakly in H to a point in argminΦ.
  • Φ(x(t)) − min Φ = o(t^-2) for α > 3 when argminΦ is nonempty.

1.5. Some remarks concerning the Hessian-driven damping term.

The Hessian-driven damping yields gradient and acceleration decay, supports reformulation without explicit Hessians, and extends the framework toward nonsmooth and discretized optimization.

  • The transition from β > 0 to β = 0 is abrupt because gradient estimates degenerate as β approaches zero.
  • lim_t→∞ ||∇Φ(x(t))|| = 0 for α > 0 and inf Φ > −∞, a property not known for AVD.
  • For α ≥ 3, bounded-set Lipschitz continuity of ∇Φ implies that the acceleration tends to zero.
  • The system can be reformulated as a first-order system involving only the gradient, enabling extension to proper lower-semicontinuous convex potentials.
  • Explicit-implicit discretization may yield new inertial forward-backward algorithms for structured convex minimization, but preserving the continuous asymptotics remains future work.

2. Strong convergence results

Strong convergence to minimizers is established under several structural assumptions, including evenness, an interior minimizer set, bounded inf-compactness, or uniform monotonicity.

  • Even objective function: For α > 3 and even twice-differentiable convex Φ, trajectories converge strongly to a minimizer.
  • Interior minimizers: For α > 3, an objective with int(argminΦ) nonempty also yields strong convergence to a minimizer.
  • Interior minimizers: The interior-minimizer assumption upgrades an L2 estimate for t||∇Φ(x(t))|| to an L1 estimate.
  • Boundedly inf-compact objectives: For α ≥ 3 and boundedly inf-compact Φ with argminΦ nonempty, every trajectory converges strongly to a minimizer.
  • Uniform monotonicity: For α > 3 and ∇Φ uniformly monotone on bounded sets, argminΦ is a singleton and trajectories converge strongly to it.

3. Further results in the strongly convex case

In the strongly convex case, the minimizer is unique and a tailored Lyapunov analysis provides faster objective convergence than the general theory.

  • Strong convexity yields a convergence rate for Φ(x(t)) that is better and more precise than the general rate.
  • For α ≥ 3 and strongly convex Φ, argminΦ is a singleton.
  • The proof constructs a surrogate Lyapunov function using weighted objective gaps, distances to the minimizer, and velocity-gradient cross terms.
  • The parameter choices cancel selected velocity terms and produce a differential inequality controlling the objective gap.
  • Strong convexity converts the resulting Lyapunov bound into a bound on Φ(x(t)) − Φ*.

4. (DIN-AVD) as a first-order system. Extension to non-smooth potentials

The Hessian-damped inertial dynamics is equivalent to a first-order formulation that avoids Hessian evaluations, enabling extension from smooth convex potentials to nonsmooth convex functions. Under α>3, the resulting systems retain weak convergence, with strong convergence under additional structural assumptions.

  • First-order reformulation: The dynamics can be reformulated as a first-order system involving only the gradient, eliminating explicit Hessian dependence.This formulation also supports replacing the gradient by the subdifferential for proper lower-semicontinuous convex potentials.
  • First-order reformulation: The smooth second-order equation and its first-order system are equivalent for matching initial conditions.The equivalence is established through auxiliary variables and transformed initial data.
  • Nonsmooth extension: For nonsmooth convex potentials, the generalized system is governed by a maximal monotone subdifferential plus a time-dependent linear operator.This structure yields global strong-solution existence and uniqueness for admissible Cauchy data.
  • Asymptotic convergence: For α>0, the generalized energy is nonincreasing and converges with the objective value to inf φ; weak cluster points lie in argminφ.Additional estimates include boundedness and decay properties for the trajectory and subgradient-related terms.
  • Scope of the extension: The generalized nonsmooth analysis weakens some properties available in the smooth case, including acceleration convergence when Hessian regularity is unavailable.The paper specifically notes that convergence of the acceleration depends on Lipschitz continuity of the Hessian.
  • Asymptotic convergence: For α>3 with minimizers, trajectories converge weakly to minimizers, while strong convergence holds under evenness, nonempty minimizer interior, bounded inf-compactness, or strong convexity.These conditions correspond to separate strong-convergence results in the generalized setting.

5. Asymptotic behavior of the trajectory under perturbations

The perturbed dynamics is analyzed through energy functions that remain controllable under integrable forcing. The paper obtains convergence of values, gradients, and trajectories under progressively stronger assumptions on damping and perturbations.

  • Energy method: Energy derivatives are unaffected by the perturbation terms because the terms containing g cancel in the relevant energy computations.This cancellation supports monotonicity estimates for the perturbed energy functions.
  • Minimizing behavior: Integrable perturbations preserve the limiting objective behavior: W0,g(t), Wβ,g(t), and Φ(x(t)) converge to inf Φ.The result assumes α>0 and that Φ is bounded below.
  • Minimizing behavior: The velocity and gradient both converge to zero under the perturbed dynamics.The argument uses decay of the combined quantities ˙x(t)+θ∇Φ(x(t)) for θ=0 and θ=β.
  • Trajectory convergence: For α≥3 with a nonempty minimizer set, the perturbed trajectory converges weakly to a minimizer.The proof transfers the main estimates to perturbed energy functions using integrability assumptions on the forcing.

6. Inertial forward-backward algorithms

Time discretization of the generalized dynamics yields inertial forward-backward algorithms for structured convex minimization. The scheme treats the smooth and nonsmooth potentials asymmetrically through explicit and implicit steps.

  • Algorithmic extension: Time discretization of the generalized dynamics enlarges the class of inertial forward-backward algorithms related to FISTA methods.The paper presents this as a new algorithmic direction rather than a completed convergence analysis.
  • Structured minimization: The structured objective is φ+Ψ, where Ψ is smooth and φ is proper, lower-semicontinuous, and convex.The two potentials are assigned different regularity roles in the discretization.
  • Structured minimization: The discretization is explicit in the smooth potential Ψ and implicit in the nonsmooth potential φ.The resulting update uses ∇Ψ in a forward step and the proximity operator of φ in a backward step.
  • Scope and cost: The inertial and damping additions have essentially no computational cost compared with classical forward-backward methods.However, whether the discretized method inherits the continuous-time convergence properties remains future work.

7. Conclusions

DIN-AVD combines vanishing isotropic viscosity with Hessian-driven geometric damping, yielding broad convergence properties and a natural nonsmooth extension. The conclusions also identify unresolved questions about parameter selection and the criticality of α = 3.

  • System and mechanism: DIN-AVD combines an asymptotically vanishing isotropic viscosity term with geometrical Hessian-driven damping.The Hessian-driven term links the system to Newton’s and Levenberg–Marquardt methods.
  • Convergence properties: Its trajectories minimize Φ, with o(k^-2) value convergence, weak convergence to minimizers, and strong convergence in several important cases.The gradient vanishes at order O(k^-1), while velocity and, under local Lipschitz continuity of ∇Φ, acceleration vanish asymptotically.
  • Nonsmooth extension: The system extends naturally to nonsmooth potentials through an equivalent first-order formulation in space and time.Most smooth-potential properties extend, except acceleration convergence, which depends on Lipschitz continuity of ∇Φ.
  • Open questions: The parameter roles remain incompletely understood, including whether α = 3 is critical and how to choose α, β, and initial conditions optimally.The paper leaves open whether lower α can preserve fast convergence or permit nonconvergent trajectories.

Appendix

The appendix develops auxiliary lemmas for establishing asymptotic convergence in Hilbert spaces. These tools combine distance-limit arguments, asymptotic differential relations, and integration-by-parts estimates for bounded-below functions.

  • Weak convergence tools: Opial’s lemma converts existence of distance limits and minimizer-valued weak cluster points into weak convergence to a point in the target set.The target set is a nonempty subset S of the Hilbert space.
  • Asymptotic differential relations: An asymptotic relation of the form u(t) + α u̇(t) → L implies u(t) → L when α > 0.The proof applies a shifted variable v = u − L and bounds its asymptotic norm.
  • Integral estimates: A twice continuously differentiable function bounded from below can be normalized to a nonnegative function before applying integration-by-parts estimates.The appendix uses this normalization as the starting point for subsequent integral deductions.
  • Weighted asymptotics: A nonnegative continuous integrable function combined with a nondecreasing unbounded weight supports an asymptotic conclusion in the auxiliary estimates.The lemma assumes ψ(t) tends to +∞ and f belongs to L1(δ, +∞).
Loading 1601.07113v1…