Fast optimization via inertial dynamics with closed-loop damping

closed-loop damping convergence rates damped inertial gradient systems Hessian damping Kurdyka-Łojasiewicz inequality maximally monotone operators quasi-gradient systems

Mathematics Subject Classification ID

Dynamical systems in optimization and economics (37N40) Applications of functional analysis in optimization, convex analysis, mathematical programming, economics (46N10) Newton-type methods (49M15) Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Convex programming (90C25)

Abstract: In a Hilbert space

H

, in order to develop fast optimization methods, we analyze the asymptotic behavior, as time

t

tends to infinity, of inertial continuous dynamics where the damping acts as a closed-loop control. The function

f : H o R

to be minimized (not necessarily convex) enters the dynamic through it gradient, which is assumed to be Lipschitz continuous on the bounded subsets of

H

. This gives autonomous dynamical systems with nonlinear damping and nonlinear driving force. We first consider the case where the damping term

p a r t i a l p h i (d o t x (t))

acts as a closed-loop control of the velocity. The damping potential

p h i : H o [0, + i n f t y)

is a convex continuous function which achieves its minimum at the origin. We show the existence and uniqueness of a global solution to the associated Cauchy problem. Then, we analyze the asymptotic convergence properties of the generated trajectories generated. We use techniques from optimization, control theory, and PDE's: Lyapunov analysis based on the decreasing property of an energy-like function, quasi-gradient and Kurdyka-Lojasiewicz theory, monotone operator theory for wave-like equations. Convergence rates are obtained based on the geometric properties of the data

f

and

p h i

. When

f

is strongly convex, we give general conditions which provide exponential convergence rates. Then, we extend the results to the case where an additional Hessian-driven damping enters the dynamic, which reduces the oscillations. Finally, we consider an inertial system involving jointly the velocity

d o t x (t)

and the gradient

a b l a f (x (t))

. In addition to its original results, this work surveys the numerous works devoted in recent years to the interaction between continuous damped inertial dynamics and numerical algorithms for optimization, with the emphasis on autonomous systems, closed-loop adaptive procedures, and convergence rates.

Review text

Summary: In a real Hilbert space \(\mathcal{H}\), in order to develop fast optimization methods, we analyze the asymptotic behavior, as time \(t\) tends to infinity, of a large class of autonomous dissipative inertial continuous dynamics. The function \(f : \mathcal{H} \to \mathbb{R}\) to be minimized (not necessarily convex) enters the dynamic via its gradient, which is assumed to be Lipschitz continuous on bounded subsets of \(\mathcal{H}\). This results in autonomous dynamical systems with nonlinear damping and nonlinear driving force. We first consider the case where the damping term \(\partial \phi ( \dot{x} ( t ) )\) acts as closed-loop control of the velocity. The damping potential \(\phi : \mathcal{H} \to \mathbb{R}_+ \) is a convex continuous function which reaches its minimum at the origin. We show the existence and uniqueness of a global solution to the associated Cauchy problem. We analyze the asymptotic convergence and the convergence rates of the trajectories generated by this system. To do this, we use techniques from optimization, control theory, and PDEs: Lyapunov analysis based on the decreasing property of an energy-like function, quasi-gradient and Kurdyka-Łojasiewicz theory, and monotone operator theory for wave-like equations. Convergence rates are obtained based on the geometric properties of the data \(f\) and \(\phi \). We put forward minimal hypotheses on the damping potential \(\phi\) guaranteeing the convergence of trajectories, thus showing the dividing line between strong and weak damping. When \(f\) is strongly convex, we give general conditions on the damping potential \(\phi\) which provide exponential convergence rates. Then, we extend the results to the case where additional Hessian-driven damping enters the dynamic, which reduces the oscillations. Finally, we consider a new inertial system where damping jointly involves the velocity \(\dot{x} ( t )\) and the gradient \(\nabla f ( x ( t ) )\). This study naturally leads to similar results for proximal-gradient algorithms obtained by temporal discretization; some of them are studied in the article. In addition to its original results, this work surveys numerous works devoted to the interaction between damped inertial continuous dynamics and numerical optimization algorithms, with an emphasis on autonomous systems, adaptive procedures, and convergence rates.

Recommendations

Cites work

Cited in

(39)

This page was built for publication: Fast optimization via inertial dynamics with closed-loop damping

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6172672)