Optimization Online


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

Masoud Ahookhosh (masoud.ahookhosh***at***univie.ac.at)
Arnold Neumaier (Arnold.Neumaier***at***univie.ac.at)

Abstract: 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.

Keywords: Structured nonsmooth convex optimization; Subgradient methods; Proximity operator; Optimal complexity; First-order black-box information; High-dimensional data

Category 1: Convex and Nonsmooth Optimization

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

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

Download: [PDF]

Entry Submitted: 05/08/2015
Entry Accepted: 05/08/2015
Entry Last Modified: 06/16/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society