Text

Finite Convergence of Proximal-Gradient Inertial Algorithms Combining Dry Friction with Hessian-Driven Damping

In a Hilbert space ${\mathcal H}$, we introduce a new class of proximal-gradient algorithms with finite convergence properties. These algorithms naturally occur as discrete temporal versions of an inertial differential inclusion which is stabilized under the joint action of three dampings: dry friction, viscous friction, and a geometric damping driven by the Hessian. The function $f:{\mathcal H} \to {\mathbb R}$ to be minimized is supposed to be differentiable (not necessarily convex) and enters the algorithm via its gradient. The dry friction damping function $\phi:{\mathcal H} \to {\mathbb R}_+$ is convex with a sharp minimum at the origin (typically $\phi(x) = r \|x\|$ with $r>0$). It enters the algorithm via its proximal mapping, which acts as a soft threshold operator on the velocities. It is the source of stabilization in a finite number of steps. The geometric damping driven by the Hessian intervenes in the dynamics in the form $\nabla^2 f (x(t)) \dot{x} (t)$. By treating this term as the time derivative of $ \nabla f (x (t)) $, this gives, in discretized form, first-order algorithms. The Hessian-driven damping allows one to control and to attenuate the oscillations. The convergence results tolerate the presence of errors, under the sole assumption of their asymptotic convergence to zero. Replacing the potential function $f$ by its Moreau envelope, we extend the results to the case of a nonsmooth convex function $f$. In this case, the algorithm involves the proximal operators of $f$ and $\phi$ separately. Several variants of this algorithm are considered, including the case of the Nesterov accelerated gradient method. We then consider the extension to the case of additive composite optimization, thus leading to splitting methods. Numerical experiments are given for lasso-type problems. The performance profiles, as a comparison tool, highlight the effectiveness of a variant of the Nesterov accelerated method with dry friction and Hessian-driven damping.

Ketersediaan

Informasi Detail

Judul Seri

SIAM JOURNAL ON OPTIMIZATION; Vol.30 No.3 July-September 2020

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 2134 - 2162

Bahasa

English

ISBN/ISSN

-

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

FINITE CONVERGENCE
INERTIAL METHODS
DIFFERENTIAL INCLUSION
PROXIMAL-GRADIENT ALGORITHMS
DRY FRICTION
HESSIAN-DRIVEN DAMPING
LASSO PROBLEM

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Samir Adly, Hedy Attouch

Versi lain/terkait

Lampiran Berkas

Komentar