Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone line-search algorithms

Abstract

We consider the problem of minimizing the sum of two nonconvex functions, one of which is smooth and the other prox-bounded and possibly nonsmooth. Such weak requirements on the functions significantly widen the range of applications compared to traditional splitting methods which typically rely on convexity. Our approach is based on the forward-backward envelope (FBE), namely a strictly continuous function whose stationary points are a subset of those of the original cost function. We analyze first- and second-order properties of the FBE under assumptions of prox-regularity of the nonsmooth term in the cost. Although the FBE in the present setting is nonsmooth we propose a globally convergent derivative-free nonmonotone line-search algorithm which relies on exactly the same oracle as the forward-backward splitting method (FBS). Moreover, when the line-search directions satisfy a Dennis-Mor\'e condition, the proposed method converges superlinearly under generalized second-order sufficiency conditions. Our theoretical results are backed up by promising numerical simulations. On large-scale problems, computing line-search directions using limited-memory quasi-Newton updates our algorithm greatly outperforms FBS and, in the convex case, its accelerated variant (FISTA).