Solving structured nonsmooth convex optimization with complexity \mathcal {O}(\varepsilon ^{-1/2})
-
Masoud Ahookhosh [1] ; Arnold Neumaier [1]
-
[1] University of Vienna
University of Vienna
Innere Stadt, Austria
-
- Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 26, Nº. 1, 2018, págs. 110-145
- Idioma: inglés
- Enlaces
-
Resumen
This paper describes an algorithm for solving structured nonsmooth convex optimization problems using the optimal subgradient algorithm (OSGA), which is a first-order method with the complexity O(ε−2) for Lipschitz continuous nonsmooth problems and O(ε−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 so that it can be solved efficiently by a new setup of OSGA (called OSGA-V) with the complexity O(ε−1/2) . Further, to solve the reformulated problem, we equip OSGA-O with an appropriate prox-function for which the OSGA-O subproblem can be solved either in a closed form or by a simple iterative scheme, which decreases the computational cost of applying the algorithm for large-scale problems. We show that applying the new scheme is feasible for many problems arising in applications. Some numerical results are reported confirming the theoretical foundations.
