Geodesic
Solving strongly convex-concave composite saddle-point problems with low dimension of one group of variable
Sbornik. Mathematics, Tome 214 (2023) no. 3, pp. 285-333

Voir la notice de l'article provenant de la source Math-Net.Ru

Algorithmic methods are developed that guarantee efficient complexity estimates for strongly convex-concave saddle-point problems in the case when one group of variables has a high dimension, while another has a rather low dimension (up to 100). These methods are based on reducing problems of this type to the minimization (maximization) problem for a convex (concave) functional with respect to one of the variables such that an approximate value of the gradient at an arbitrary point can be obtained with the required accuracy using an auxiliary optimization subproblem with respect to the other variable. It is proposed to use the ellipsoid method and Vaidya's method for low-dimensional problems and accelerated gradient methods with inexact information about the gradient or subgradient for high-dimensional problems. In the case when one group of variables, ranging over a hypercube, has a very low dimension (up to five), another proposed approach to strongly convex-concave saddle-point problems is rather efficient. This approach is based on a new version of a multidimensional analogue of Nesterov's method on a square (the multidimensional dichotomy method) with the possibility to use inexact values of the gradient of the objective functional. Bibliography: 28 titles.
Keywords: saddle-point problem, ellipsoid method, Vaidya's method, inexact subgradient, multidimensional dichotomy.
Mots-clés : hypercube 
@article{SM_2023_214_3_a0,
     author = {M. S. Alkousa and A. V. Gasnikov and E. L. Gladin and I. A. Kuruzov and D. A. Pasechnyuk and F. S. Stonyakin},
     title = {Solving strongly convex-concave composite saddle-point problems with low dimension of one group of variable},
     journal = {Sbornik. Mathematics},
     pages = {285--333},
     publisher = {mathdoc},
     volume = {214},
     number = {3},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2023_214_3_a0/}
}
TY  - JOUR
AU  - M. S. Alkousa
AU  - A. V. Gasnikov
AU  - E. L. Gladin
AU  - I. A. Kuruzov
AU  - D. A. Pasechnyuk
AU  - F. S. Stonyakin
TI  - Solving strongly convex-concave composite saddle-point problems with low dimension of one group of variable
JO  - Sbornik. Mathematics
PY  - 2023
SP  - 285
EP  - 333
VL  - 214
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SM_2023_214_3_a0/
LA  - en
ID  - SM_2023_214_3_a0
ER  - 
%0 Journal Article
%A M. S. Alkousa
%A A. V. Gasnikov
%A E. L. Gladin
%A I. A. Kuruzov
%A D. A. Pasechnyuk
%A F. S. Stonyakin
%T Solving strongly convex-concave composite saddle-point problems with low dimension of one group of variable
%J Sbornik. Mathematics
%D 2023
%P 285-333
%V 214
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SM_2023_214_3_a0/
%G en
%F SM_2023_214_3_a0
M. S. Alkousa; A. V. Gasnikov; E. L. Gladin; I. A. Kuruzov; D. A. Pasechnyuk; F. S. Stonyakin. Solving strongly convex-concave composite saddle-point problems with low dimension of one group of variable. Sbornik. Mathematics, Tome 214 (2023) no. 3, pp. 285-333. http://geodesic.mathdoc.fr/item/SM_2023_214_3_a0/