First order inertial optimization algorithms with threshold effects associated with dry friction

In a Hilbert space setting, we consider a new first order optimization algorithm which is obtained by temporal discretization of a damped inertial dynamic involving dry friction. The function f to be minimized is assumed to be differentiable (not necessarily convex). The dry friction potential function φ, which has a sharp minimum at the origin, enters the algorithm via its proximal mapping, which acts as a soft thresholding operator on the sum of the velocity and the gradient terms. After a finite number of steps, the structure of the algorithm changes, losing its inertial character to become the steepest descent method. The geometric damping driven by the Hessian of f makes it possible to control and attenuate the oscillations. The algorithm generates convergent sequences when f is convex, and in the nonconvex case when f satisfies the Kurdyka-Lojasiewicz property. As a remarkable property, the convergence results tolerate the presence of errors, under the sole assumption of their asymptotic convergence towards zero. The study is then extended to the case of a nonsmooth convex function f , in which case the algorithm involves the proximal operators of f and φ separately. Then, applications are given to the Lasso problem and nonsmooth d.c. programming.