Proximal methods for minimizing the sum of a convex function and a composite function

Quoc Tran Dinh, Moritz Diehl

Published 2011-05-02Version 1

This paper extends the algorithm schemes proposed in \cite{Nesterov2007a} and \cite{Nesterov2007b} to the minimization of the sum of a composite objective function and a convex function. Two proximal point-type schemes are provided and their global convergence is investigated. The worst case complexity bound is also estimated under certain Lipschitz conditions and nondegeneratedness. The algorithm is then accelerated to get a faster convergence rate for the strongly convex case.