Solving nonsmooth convex optimization with complexity (\eps^{-1/2})\$

This paper describes an algorithm for solving structured nonsmooth convex optimization problems using OSGA, a first-order method with the complexity \$O(\eps^{-2})\$ for Lipschitz continuous nonsmooth problems and \$O(\eps^{-1/2})\$ for smooth problems with Lipschitz continuous gradient. If the nonsmoothness of the problem is manifested in a structured way, we reformulate the problem in a form that can be solved efficiently by OSGA with the complexity \$O(\eps^{-1/2})\$. To solve the reformulated problem, we equip OSGA by an appropriate prox-function for which the OSGA subproblem can be solved either in a closed form or by a simple iterative scheme, which decreases the computational cost of applying the algorithm, especially for large-scale problems. We show that applying the new scheme is feasible for many problems arising in applications.

Citation

Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz 1, 1090 Vienna, Austria May 2015