OSGA: A fast subgradient algorithm with optimal complexity

Arnold Neumaier

Veröffentlichungen: Beitrag in FachzeitschriftArtikelPeer Reviewed

Abstract

This paper presents an algorithm for approximately minimizing a convex function in simple, not necessarily bounded convex, finite-dimensional domains, assuming only that function values and subgradients are available. No global information about the objective function is needed apart from a strong convexity parameter (which can be put to zero if only convexity is known). The worst case number of iterations needed to achieve a given accuracy is independent of the dimension and—apart from a constant factor—best possible under a variety of smoothness assumptions on the objective function.
OriginalspracheEnglisch
Seiten (von - bis)1- 21
Seitenumfang21
FachzeitschriftMathematical Programming
Jahrgang158
Ausgabenummer1-2
Frühes Online-Datum16 Mai 2015
DOIs
PublikationsstatusVeröffentlicht - Juli 2016

ÖFOS 2012

  • 101016 Optimierung

Zitationsweisen