Primal–Dual Mirror Descent Method for Constraint Stochastic Optimization Problems
- 作者: Bayandina A.S.1, Gasnikov A.V.2,3,4, Gasnikova E.V.5, Matsievskii S.V.6
-
隶属关系:
- Department of Control and Applied Mathematics, Moscow Institute of Physics and Technology
- Chair of Mathematical Foundations of Control, Moscow Institute of Physics and Technology
- Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences
- Adygeya State University
- Laboratory of Structural Analysis Methods in Predictive Simulation, Moscow Institute of Physics and Technology
- Kant Baltic Federal University
- 期: 卷 58, 编号 11 (2018)
- 页面: 1728-1736
- 栏目: Article
- URL: https://journal-vniispk.ru/0965-5425/article/view/179912
- DOI: https://doi.org/10.1134/S0965542518110039
- ID: 179912
如何引用文章
详细
Extension of the mirror descent method developed for convex stochastic optimization problems to constrained convex stochastic optimization problems (subject to functional inequality constraints) is studied. A method that performs an ordinary mirror descent step if the constraints are insignificantly violated and performs a mirror descent step with respect to the violated constraint if this constraint is significantly violated is proposed. If the method parameters are chosen appropriately, a bound on the convergence rate (that is optimal for the given class of problems) is obtained and sharp bounds on the probability of large deviations are proved. For the deterministic case, the primal–dual property of the proposed method is proved. In other words, it is proved that, given the sequence of points (vectors) generated by the method, the solution of the dual method can be reconstructed up to the same accuracy with which the primal problem is solved. The efficiency of the method as applied for problems subject to a huge number of constraints is discussed. Note that the bound on the duality gap obtained in this paper does not include the unknown size of the solution to the dual problem.
作者简介
A. Bayandina
Department of Control and Applied Mathematics, Moscow Institute of Physics and Technology
编辑信件的主要联系方式.
Email: anast.bayandina@gmail.com
俄罗斯联邦, Dolgoprudnyi, Moscow oblast, 141700
A. Gasnikov
Chair of Mathematical Foundations of Control, Moscow Institute of Physics and Technology; Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences; Adygeya State University
编辑信件的主要联系方式.
Email: gasnikov@yandex.ru
俄罗斯联邦, Dolgoprudnyi, Moscow oblast, 141700; Moscow, 127051; Maykop, 352700
E. Gasnikova
Laboratory of Structural Analysis Methods in Predictive Simulation, Moscow Institute of Physics and Technology
编辑信件的主要联系方式.
Email: egasnikova@yandex.ru
俄罗斯联邦, Dolgoprudnyi, Moscow oblast, 141700
S. Matsievskii
Kant Baltic Federal University
编辑信件的主要联系方式.
Email: matsievsky@newmail.ru
俄罗斯联邦, Kaliningrad, 236016
补充文件
