Adaptive gradient-type methods for optimization problems with relative error and sharp minimum

F. S. Stonyakin ; S. S. Ablaev ; I. V. Baran

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 27 (2021) no. 4, pp. 175-188

Résumé

A universal method of gradient type for convex minimization problems with relative error is studied, and new results on the linear convergence rate of specific versions of the subgradient method for problems with a sharp minimum and some generalizations of convexity are obtained. A new approach to the choice of parameters and the stopping rule of an adaptive version of the method of similar triangles on a class of minimization problems for convex positively homogeneous functionals is proposed. As a consequence, an analog of the universal gradient method for problems with relative error is obtained and an optimal estimate of its convergence rate on a chosen class of problems is proved. An example of the results of numerical experiments illustrating the possibility of improving the quality of the approximate solution produced by the method as compared to a theoretical estimate due to the introduced adaptive stopping rule is given. A version of the subgradient method for minimization problems with weakly $\beta$-quasiconvex Lipschitz-continuous functionals in the case of a sharp minimum is considered, and a linear convergence rate is proved. Finally, a version of the subgradient method is proposed that converges at a linear rate on a class of problems of minimizing quasiconvex Holder-continuous functionals with a sharp minimum. The applicability of this result for functionals with a weak sharp minimum (Holderian growth) is shown and a corollary of this result is formulated for problems with relative error.

Détail

Keywords: relative error, convex positively homogeneous functional, weak $\beta$-quasiconvex functional, subgradient method, Lipschitz-continuous functional
Mots-clés : quasiconvex functional.