A multi-step inertial extragradient algorithm for nonsmooth and nonconvex composite optimization problems

We are concerned with minimizing a composite objective function, which can be decomposed into a differentiable but not necessarily convex part and a convex but possibly nonsmooth function. To efficiently exploit the decomposable structure, in this paper, we propose a Multi-step inertial ExtraGradient Algorithm (MEGA), which consists of two inertial steps involving the combination of finite historical iterates and two proximal gradient steps evaluating the proximal operators of a convex function at some points. With the help of Kurdyka-Łojasiewicz property, we theoretically prove that the sequence generated by our MEGA is globally convergent to a stationary point of the problem under consideration. A series of numerical experiments on Lasso and nonconvex quadratic optimization problems show that the proposed MEGA works well in practice. Particularly exciting is the illustration by some computational results that our MEGA can escape local minima points (at least with high probability) to reach a global solution. This strongly supports the idea that utilizing more historical information in extragradient methods is beneficial for solving nonconvex optimization problems.