Mirror descent for constrained optimization problems with large subgradient values of functional constraints

Stonyakin F.S., Stepanov A.N., Gasnikov A.V., Titov A.A.
 pdf (185K)

The paper is devoted to the problem of minimization of the non-smooth functional $f$ with a non-positive non-smooth Lipschitz-continuous functional constraint. We consider the formulation of the problem in the case of quasi-convex functionals. We propose new strategies of step-sizes and adaptive stopping rules in Mirror Descent for the considered class of problems. It is shown that the methods are applicable to the objective functionals of various levels of smoothness. Applying a special restart technique to the considered version of Mirror Descent there was proposed an optimal method for optimization problems with strongly convex objective functionals. Estimates of the rate of convergence for the considered methods are obtained depending on the level of smoothness of the objective functional. These estimates indicate the optimality of the considered methods from the point of view of the theory of lower oracle bounds. In particular, the optimality of our approach for Höldercontinuous quasi-convex (sub)differentiable objective functionals is proved. In addition, the case of a quasiconvex objective functional and functional constraint was considered. In this paper, we consider the problem of minimizing a non-smooth functional $f$ in the presence of a Lipschitz-continuous non-positive non-smooth functional constraint $g$, and the problem statement in the cases of quasi-convex and strongly (quasi-)convex functionals is considered separately. The paper presents numerical experiments demonstrating the advantages of using the considered methods.

Keywords: non-smooth constrained optimization, quasi-convex functional, adaptive mirror descent, level of smoothness, Hölder-continuous objective functional, optimal method
Citation in English: Stonyakin F.S., Stepanov A.N., Gasnikov A.V., Titov A.A. Mirror descent for constrained optimization problems with large subgradient values of functional constraints // Computer Research and Modeling, 2020, vol. 12, no. 2, pp. 301-317
Citation in English: Stonyakin F.S., Stepanov A.N., Gasnikov A.V., Titov A.A. Mirror descent for constrained optimization problems with large subgradient values of functional constraints // Computer Research and Modeling, 2020, vol. 12, no. 2, pp. 301-317
DOI: 10.20537/2076-7633-2020-12-2-301-317
URL: http://crm-en.ics.org.ru/journal/article/2910/
Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Copyright © 2009–2024 Institute of Computer Science