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

Computer Research and Modeling. 2020. Vol. 12. No. 2. P. 301–317.

Stonyakin F. S., Stepanov A. N., Gasnikov A., Titov A.

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 ¨oldercontinuous 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: Optimal Methods, non-smooth constrained optimization, quasi-convex functional, adaptive mirror descent, level of smoothness, негладкая условная оптимизация, квазивыпуклый функционал, адаптивный зеркальный спуск, уровень гладкости, гёльдеров целевой функционал, оптимальный метод