On some algorithms for constrained optimization problems with relative accuracy with respect to the objective functional

F. S. Stonyakin ; I. V. Baran

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 26 (2020) no. 3, pp. 198-210

Résumé

Convergence rate estimates are derived for some subgradient methods for the problem of minimization of a nonsmooth convex Lipschitz homogeneous functional with relative accuracy with respect to the objective functional under functional constraints. It is proposed to apply analogs of known switching subgradient schemes to such problems, which allows us to consider some classes of nonconvex problems as well. A convergence rate estimate is obtained for the adaptive mirror descent with switchings on the class of weakly $\alpha$-quasiconvex objective functionals and constraint functionals. A convergence rate estimate of a proposed subgradient method with switchings with relative accuracy with respect to the objective functional is proved for problems of minimization of a convex homogeneous objective functional with a weakly $\alpha$-quasiconvex constraint functional. We also consider a method for problems of minimization of a convex homogeneous Lipschitz functional with unimodal Lipschitz constraint functional and derive an estimate for its convergence rate. All convergence rate estimates proved in the paper show the optimality of the proposed algorithmic procedures from the viewpoint of the theory of lower oracle bounds.

Détail

Keywords: relative accuracy, convex homogeneous functional, weakly $\alpha$-quasiconvex functional, mirror descent, Lipschitz-continuous functional, unimodal functional.