Inexact model: a framework for optimization and variational inequalities. (2nd November 2021)

• Record Type: Journal Article
• Authors: Stonyakin, Fedor; Tyurin, Alexander; Gasnikov, Alexander; Dvurechensky, Pavel; Agafonov, Artem; Dvinskikh, Darina; Alkousa, Mohammad; Pasechnyuk, Dmitry; Artamonov, Sergei; Piskunova, Victorya
• Is Part Of: Optimization methods and software. Volume 36:Number 6(2021)
• Page Start: 1155
• Page End: 1201
• Publication Date: 2021-11-02
• Subjects: Convex optimization -- composite optimization -- proximal method -- level-set method -- variational inequality -- universal method -- Mirror–Prox -- acceleration -- relative smoothness -- saddle-point problem; 65K05 -- 65K15 -- 90C06; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2021.1924714
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : In this paper, we propose a general algorithmic framework for the first-order methods in optimization in a broad sense, including minimization problems, saddle-point problems and variational inequalities (VIs). This framework allows obtaining many known methods as a special case, the list including accelerated gradient method, composite optimization methods, level-set methods, Bregman proximal methods. The idea of the framework is based on constructing an inexact model of the main problem component, i.e. objective function in optimization or operator in VIs. Besides reproducing known results, our framework allows constructing new methods, which we illustrate by constructing a universal conditional gradient method and a universal method for VIs with a composite structure. This method works for smooth and non-smooth problems with optimal complexity without a priori knowledge of the problem's smoothness. As a particular case of our general framework, we introduce relative smoothness for operators and propose an algorithm for VIs with such operators. We also generalize our framework for relatively strongly convex objectives and strongly monotone VIs.