Proximal envelopes: Smooth optimization algorithms for nonsmooth problems

Nonsmooth optimization problems arise in an ever-growing number of applications in science and engineering. Proximal (or splitting) algorithms are a general approach to a variety of nonsmooth problems, but as with all first order methods their convergence properties are severely affected by ill conditioning of the problem. In this thesis, an interpretation to proximal algorithms as unconstrained gradient methods over an associated function function is provided. Such functions are called proximal envelopes, in analogy with the well-known Moreau envelope. Proximal envelopes provide a link between nonsmooth and smooth optimization, and allow for the application of more efficient and robust smooth optimization algorithms to the solution of nonsmooth, possibly constrained problems. We consider the case of the forward-backward and Douglas-Rachford splitting methods. In the first case, based on generalized differentiability properties on the original problem terms, we devise superlinearly convergent line-search algorithms based on quasi-Newton directions, that use the same oracle as the forward-backward splitting; furthermore, the analysis is extended to the case where the dual problem is concerned. In the second case a global convergence rate for the Douglas-Rachford splitting is obtained, while an optimal stepsize selection strategy and an accelerated variant of the method is proposed.