Excessive gap technique in non-smooth convex minimization

Yurii Nesterov

No 2003035, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: In this paper we introduce a new primal-dual technique for convergence analysis of gradient schemes for non-smooth convex optimization. As an example of its application, we derive a primal-dual gradient method for a special class of structured non-smooth optimization problems, which ensures a rate of convergence of the order O(1/k), where k is the iteration count. Another example is a gradient scheme which minimizes a non-smooth strongly convex function with known structure with the rate of convergence O(1/k exp2). In both cases the effciency of the methods is higher than the corresponding black-box lower complexity bounds by an order of magnitude.

Keywords: convex optimization; non-smooth optimization; complexity theory; black-box oracle; optimal methods; structural optimization. (search for similar items in EconPapers)
Date: 2003-05
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2003.html (text/html)

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:cor:louvco:2003035

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().