A universal modification of the linear coupling method

In the late sixties, N. Shor and B. Polyak independently proposed optimal first-order methods for non-smooth convex optimization problems. In 1982 A. Nemirovski proposed optimal first-order methods for smooth convex optimization problems, which utilized auxiliary line search. In 1985 A. Nemirovski a...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2018-04
Main Authors: Guminov, Sergey, Gasnikov, Alexander, Anikin, Anton, Gornov, Alexander
Format: Article
Language:English
Subjects:
Convex analysis
Convexity
Methods
Optimization
Performance enhancement
Searching
Smoothness
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In the late sixties, N. Shor and B. Polyak independently proposed optimal first-order methods for non-smooth convex optimization problems. In 1982 A. Nemirovski proposed optimal first-order methods for smooth convex optimization problems, which utilized auxiliary line search. In 1985 A. Nemirovski and Yu. Nesterov proposed a parametric family of optimal first-order methods for convex optimization problems with intermediate smoothness. In 2013 Yu. Nesterov proposed a universal gradient method which combined all the good properties of the previous methods, except the possibility of using auxiliary line search. One can typically observe that in practice auxiliary line search improves performance for many tasks. In this paper, we propose the apparently first such method of non-smooth convex optimization allowing for the use of the line search procedure. Moreover, it is based on the universal gradient method, which does not require any a priori information about the actual degree of smoothness of the problem. Numerical experiments demonstrate that the proposed method is, in some cases, considerably faster than Nesterov's universal gradient method.
ISSN:2331-8422