2020/01/23 by Fedor Stonyakin, Alexander Tyurin, Stonyakin, Fedor +17 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Applied mathematics #Convexity #FOS: Mathematics #Mathematical analysis #Mathematical optimization #Mathematics #Obstacle problem #Operator (biology) #Optimization and Control (math.OC) #Optimization and Variational Analysis #Optimization problem #Saddle point #Smoothness #Sparse and Compressive Sensing Techniques #Variational inequality #math.OC
paper · pdf · doi:10.48550/arxiv.2001.09013
published in arXiv (Cornell University) (Cornell University) · arXiv admin note: text overlap with arXiv:1902.00990. To appear in Optimization Methods and Software, https://doi.org/10.1080/10556788.2021.1924714
openalex publication_date 2020/01/23 · arxiv created 2021/12/19 · arxiv updated 2021/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
In this paper, we propose a general algorithmic framework for first-order\nmethods in optimization in a broad sense, including minimization problems,\nsaddle-point problems, and variational inequalities. This framework allows\nobtaining many known methods as a special case, the list including accelerated\ngradient method, composite optimization methods, level-set methods, Bregman\nproximal methods. The idea of the framework is based on constructing an inexact\nmodel of the main problem component, i.e. objective function in optimization or\noperator in variational inequalities. Besides reproducing known results, our\nframework allows constructing new methods, which we illustrate by constructing\na universal conditional gradient method and a universal method for variational\ninequalities with a composite structure. This method works for smooth and\nnon-smooth problems with optimal complexity without a priori knowledge of the\nproblem's smoothness. As a particular case of our general framework, we\nintroduce relative smoothness for operators and propose an algorithm for\nvariational inequalities (VIs) with such operators. We also generalize our\nframework for relatively strongly convex objectives and strongly monotone\nvariational inequalities.\n This paper is an extended and updated version of [arXiv:1902.00990]. In\nparticular, we add an extension of relative strong convexity for optimization\nand variational inequalities.\n