Geodesic
On some algorithms for constrained optimization problems with relative accuracy with respect to the objective functional
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 26 (2020) no. 3, pp. 198-210 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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.
Keywords: relative accuracy, convex homogeneous functional, weakly $\alpha$-quasiconvex functional, mirror descent, Lipschitz-continuous functional, unimodal functional. 
@article{TIMM_2020_26_3_a16,
     author = {F. S. Stonyakin and I. V. Baran},
     title = {On some algorithms for constrained optimization problems with relative accuracy with respect to the objective functional},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {198--210},
     year = {2020},
     volume = {26},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2020_26_3_a16/}
}
TY  - JOUR
AU  - F. S. Stonyakin
AU  - I. V. Baran
TI  - On some algorithms for constrained optimization problems with relative accuracy with respect to the objective functional
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2020
SP  - 198
EP  - 210
VL  - 26
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2020_26_3_a16/
LA  - ru
ID  - TIMM_2020_26_3_a16
ER  - 
%0 Journal Article
%A F. S. Stonyakin
%A I. V. Baran
%T On some algorithms for constrained optimization problems with relative accuracy with respect to the objective functional
%J Trudy Instituta matematiki i mehaniki
%D 2020
%P 198-210
%V 26
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2020_26_3_a16/
%G ru
%F TIMM_2020_26_3_a16
F. S. Stonyakin; I. V. Baran. On some algorithms for constrained optimization problems with relative accuracy with respect to the objective functional. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 26 (2020) no. 3, pp. 198-210. http://geodesic.mathdoc.fr/item/TIMM_2020_26_3_a16/

[1] Nesterov Yu., “Rounding of convex sets and efficient gradient methods for linear programming problems”, Optimization Methods and Software, 23:1 (2008), 109–128 | MR | Zbl

[2] Nesterov Yu., “Unconstrained convex minimization in relative scale”, Math. Oper. Res., 34:1 (2009), 180–193 | DOI | MR | Zbl

[3] Nesterov Yu. E., Algoritmicheskaya vypuklaya optimizatsiya, dis. ...d-ra fiz.-mat. nauk, Mosk. fiz.-tekhn. in-t, 2013, 367 pp.

[4] Nemirovskii A. S., Yudin D. B., Slozhnost zadach i effektivnost metodov optimizatsii, Nauka, Moskva, 1979, 384 pp.

[5] Polyak B. T., “Odin obschii metod resheniya ekstremalnykh zadach”, Dokl. AN SSSR, 174:1 (1967), 33–36 | Zbl

[6] Shor N. Z., “Primenenie obobschennogo gradientnogo spuska v blochnom programmirovanii”, Kibernetika, 1967, no. 3, 53–55 | Zbl

[7] Nemirovskii A. S., Yudin D. B., “Effektivnye metody resheniya zadach vypuklogo programmirovaniya bolshoi razmernosti”, Ekonomika i mat. metody, 1979, no. 2, 135–152

[8] Bayandina A., Dvurechensky P., Gasnikov A., Stonyakin F., Titov A., “Mirror descentand convex optimization problems with non-smooth inequality constraints”, Large-Scale and Distributed Optimization, Lect. Notes Math., 2227, eds. Pontus Giselsson, Anders Rantzer, Springer, Cham, 2018, 181–213 | DOI | MR | Zbl

[9] Stonyakin F., Stepanov A., Gasnikov A., Titov A., “Mirror descent for constrained optimization problems with large subgradient values of functional constraints”, Kompyuternye issledovaniya i modelirovanie, 12:2 (2020), 301–317 | DOI | MR

[10] Stonyakin F. S., Alkusa M. S., Stepanov A. N., Titov A. A., “Adaptivnye algoritmy zerkalnogo spuska dlya zadach vypukloi i silno vypukloi optimizatsii s funktsionalnymi ogranicheniyami”, Diskretnyi analiz i issled. operatsii, 26:3 (2019), 88–114 | DOI | MR | Zbl

[11] Gasnikov A. V., Sovremennye chislennye metody optimizatsii. Metod universalnogo gradientnogo spuska, Izd-vo MFTI, Moskva, 2018, 286 pp.

[12] Guminov S. V., Nesterov Yu. E., Dvurechenskii P. E., Gasnikov A. V., “Pryamo-dvoistvennyi uskorennyi gradientnyi metod s odnomernym poiskom dlya vypuklykh, nevypuklykh i negladkikh zadach optimizatsii”, Dokl. RAN, 485:1 (2019), 15–18 | DOI | Zbl

[13] Hinder O., Sidford A., Sohoni N. S., Near-optimal methods for minimizing star-convex functions and beyond, [e-resource], 2019, 37 pp., arXiv: 1906.11985

[14] Ben-Tal A., Nemirovski A., Lectures on modern convex optimization analysis, algorithms, and engineering applications, SIAM, Philadelphia, 2019, 647 pp. | MR

[15] Nesterov Yu. E., Effektivnye metody nelineinogo programmirovaniya, Radio i svyaz, Moskva, 1989, 301 pp.