Geodesic
Adaptive mirror descent algorithms in convex programming problems with Lipschitz constraints
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 2, pp. 266-279 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The paper is devoted to new modifications of recently proposed adaptive Mirror Descent methods for convex minimization problems in the case of several convex functional constraints. Methods for problems of two types are considered. In problems of the first type, the objective functional is Lipschitz (generally, nonsmooth). In problems of the second type, the gradient of the objective functional is Lipschitz. We also consider the case of a nonsmooth objective functional equal to the maximum of smooth functionals with Lipschitz gradient. In all the cases, the functional constraints are assumed to be Lipschitz and, generally, nonsmooth. The proposed modifications make it possible to reduce the running time of the algorithm due to skipping some of the functional constraints at nonproductive steps. We derive bounds for the convergence rate, which show that the methods under consideration are optimal from the viewpoint of lower oracle estimates. The results of numerical experiments illustrating the advantages of the proposed procedure for some examples are presented.
Keywords: adaptive Mirror Descent, Lipschitz functional, Lipschitz gradient, productive step, nonproductive step. 
@article{TIMM_2018_24_2_a24,
     author = {F. S. Stonyakin and M. S. Alkousa and A. N. Stepanov and M. A. Barinov},
     title = {Adaptive mirror descent algorithms in convex programming problems with {Lipschitz} constraints},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {266--279},
     year = {2018},
     volume = {24},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2018_24_2_a24/}
}
TY  - JOUR
AU  - F. S. Stonyakin
AU  - M. S. Alkousa
AU  - A. N. Stepanov
AU  - M. A. Barinov
TI  - Adaptive mirror descent algorithms in convex programming problems with Lipschitz constraints
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2018
SP  - 266
EP  - 279
VL  - 24
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2018_24_2_a24/
LA  - ru
ID  - TIMM_2018_24_2_a24
ER  - 
%0 Journal Article
%A F. S. Stonyakin
%A M. S. Alkousa
%A A. N. Stepanov
%A M. A. Barinov
%T Adaptive mirror descent algorithms in convex programming problems with Lipschitz constraints
%J Trudy Instituta matematiki i mehaniki
%D 2018
%P 266-279
%V 24
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2018_24_2_a24/
%G ru
%F TIMM_2018_24_2_a24
F. S. Stonyakin; M. S. Alkousa; A. N. Stepanov; M. A. Barinov. Adaptive mirror descent algorithms in convex programming problems with Lipschitz constraints. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 2, pp. 266-279. http://geodesic.mathdoc.fr/item/TIMM_2018_24_2_a24/

[1] Ben-Tal A. and Nemirovski A., “Robust truss topology design via semidefinite programming”, SIAM J. Optim., 7:4 (1997), 991–1016 | DOI | MR | Zbl

[2] Shpirko S., Nesterov Yu., “Primal-dual subgradient methods for huge-scale linear conic problem”, SIAM J. Optim., 24:3 (2014), 1444–1457 | DOI | MR | Zbl

[3] Beck A., Teboulle M., “Mirror descent and nonlinear projected subgradient methods for convex optimization”, Operations Research Letters, 31:3 (2003), 167–175 | DOI | MR | Zbl

[4] Nemirovsky A., Yudin D., Problem complexity and method efficiency, Wiley Sons, N Y, 1983, 404 pp. | MR | Zbl

[5] Polyak B. T., “Odin obschii metod resheniya ekstremalnykh zadach”, Dokl. AN SSSR, 8:3 (1967), 593–597 | Zbl

[6] Shor N. 3., “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 matematicheskie metody, 1979, no. 2, 135–152

[8] A. Beck, A. Ben-Tal, N. Guttmann-Beck, L. Tetruashvili, “The comirror algorithm for solving nonsmooth constrained convex problems”, Operations Research Letters, 38:6 (2010), 493–498 | DOI | MR | Zbl

[9] Ben-Tal A., Nemirovski A., Lectures on modern convex optimization, Society for Industrial and Appl. Math., Philadelphia, 2001, 590 pp. | MR | Zbl

[10] A. Bayandina, P. Dvurechensky, A. Gasnikov, F. Stonyakin, A. Titov, Mirror descent and convex optimization problems with non-smooth inequality constraints, [e-resource], 2018, 30 pp., arXiv: https://arxiv.org/abs/1710.06612

[11] Nesterov Y., Introductory lectures on convex optimization, a basic course, Kluwer Acad. Publ., Boston, 2004, 236 pp. | DOI | MR | Zbl

[12] Nesterov Y., Subgradient methods for convex functions with nonstandard growth properties, e-resource, slides, Online; accessed 30-March-2018 URL: http://www.mathnet.ru:8080/PresentFiles/16179/growthbm_nesterov.pdf

[13] CPython [site] URL: https://www.python.org/