Adaptive Mirror Descent Algorithms for Convex and Strongly Convex Optimization Problems with Functional Constraints
- Authors: Stonyakin F.S.1,2, Alkousa M.2, Stepanov A.N.1, Titov A.A.2
-
Affiliations:
- Vernadsky Crimean Federal University
- Moscow Institute of Physics and Technologies
- Issue: Vol 13, No 3 (2019)
- Pages: 557-574
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213247
- DOI: https://doi.org/10.1134/S1990478919030165
- ID: 213247
Cite item
Abstract
Under consideration are some adaptive mirror descent algorithms for the problems of minimization of a convex objective functional with several convex Lipschitz (generally, nonsmooth) functional constraints. It is demonstrated that the methods are applicable to the objective functionals of various levels of smoothness: The Lipschitz condition holds either for the objective functional itself or for its gradient or Hessian (while the functional itself can fail to satisfy the Lipschitz condition). The main idea is the adaptive adjustment of the method with respect to the Lipschitz constant of the objective functional (its gradient or Hessian), as well as the Lipschitz constant of the constraint. The two types of methods are considered: adaptive (not requiring the knowledge of the Lipschitz constants neither for the objective functional nor for constraints, and partially adaptive (requiring the knowledge of the Lipschitz constant for constraints). Using the restart technique, some methods are proposed for strongly convex minimization problems. Some estimates of the rate of convergence are obtained for all algorithms under consideration in dependence on the level of smoothness of the objective functional. Numerical experiments are presented to illustrate the advantages of the proposed methods for some examples.
About the authors
F. S. Stonyakin
Vernadsky Crimean Federal University; Moscow Institute of Physics and Technologies
Author for correspondence.
Email: fedyor@mail.ru
Russian Federation, pr. Akad. Vernadskogo 4, Simferopol, 295007; Institutskii per. 9, Dolgoprudnyi, 141701
M. Alkousa
Moscow Institute of Physics and Technologies
Author for correspondence.
Email: mohammad.alkousa@phystech.edu
Russian Federation, Institutskii per. 9, Dolgoprudnyi, 141701
A. N. Stepanov
Vernadsky Crimean Federal University
Author for correspondence.
Email: stepanov.student@gmail.com
Russian Federation, pr. Akad. Vernadskogo 4, Simferopol, 295007
A. A. Titov
Moscow Institute of Physics and Technologies
Author for correspondence.
Email: a.a.titov@phystech.edu
Russian Federation, Institutskii per. 9, Dolgoprudnyi, 141701