Solving structured nonsmooth convex optimization with complexity $$\mathcal {O}(\varepsilon ^{-1/2})$$ O ( ε - 1 / 2 )

Masoud Ahookhosh () and Arnold Neumaier ()
Additional contact information
Masoud Ahookhosh: University of Vienna
Arnold Neumaier: University of Vienna

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 2018, vol. 26, issue 1, No 8, 110-145

Abstract: Abstract 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 $$\mathcal {O}(\varepsilon ^{-2})$$ O ( ε - 2 ) for Lipschitz continuous nonsmooth problems and $$\mathcal {O}(\varepsilon ^{-1/2})$$ 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 $$\mathcal {O}(\varepsilon ^{-1/2})$$ 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.

Keywords: Structured nonsmooth convex optimization; Subgradient methods; Proximity operator; Optimal complexity; First-order black-box information; 90C25; 90C60; 49M37; 65K05; 68Q25 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11750-017-0462-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:topjnl:v:26:y:2018:i:1:d:10.1007_s11750-017-0462-3

Ordering information: This journal article can be ordered from
http://link.springer.de/orders.htm

DOI: 10.1007/s11750-017-0462-3

Access Statistics for this article

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research is currently edited by Juan José Salazar González and Gustavo Bergantiños

More articles in TOP: An Official Journal of the Spanish Society of Statistics and Operations Research from Springer, Sociedad de Estadística e Investigación Operativa
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().