A multilevel proximal gradient algorithm for a class of composite optimization problems

Abstract

Composite optimization models consist of the minimization of the sum of a smooth (not necessarily convex) function and a non-smooth convex function. Such models arise in many applications where, in addition to the composite nature of the objective function, a hierarchy of models is readily available. It is common to take advantage of this hierarchy of models by first solving a low fidelity model and then using the solution as a starting point to a high fidelity model. We adopt an optimization point of view and show how to take advantage of the availability of a hierarchy of models in a consistent manner. We do not use the low fidelity model just for the computation of promising starting points but also for the computa- tion of search directions. We establish the convergence and convergence rate of the proposed algorithm. Our numerical experiments on large scale image restora- tion problems and the transition path problem suggest that, for certain classes of problems, the proposed algorithm is significantly faster than the state of the art.