Optimization Online


An optimal subgradient algorithm for large-scale convex optimization in simple domains

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

Abstract: This paper shows that the optimal subgradient algorithm, OSGA, proposed in \cite{NeuO} can be used for solving structured large-scale convex constrained optimization problems. Only first-order information is required, and the optimal complexity bounds for both smooth and nonsmooth problems are attained. More specifically, we consider two classes of problems: (i) a convex objective with a simple closed convex domain, where the orthogonal projection on this feasible domain is efficiently available; (ii) a convex objective with a simple convex functional constraint. If we equip OSGA with an appropriate prox-function, the OSGA subproblem can be solved either in a closed form or by a simple iterative scheme, which is especially important for large-scale problems. We report numerical results for some applications to show the efficiency of the proposed scheme. A software package implementing OSGA for above domains is available.

Keywords: structured convex optimization, sparse optimization, nonsmooth optimization, projection 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, 2015

Download: [PDF]

Entry Submitted: 01/06/2015
Entry Accepted: 01/06/2015
Entry Last Modified: 01/06/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