|
This article is cited in 31 scientific papers (total in 31 papers)
Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints
A. S. Anikina, A. V. Gasnikovbc, P. E. Dvurechenskydc, A. I. Tyurine, A. V. Chernovb a Institute of System Dynamics and Control Theory, Siberian Branch, Russian Academy of Sciences, Irkutsk, Russia
b Moscow Institute of Physics and Technology, Dolgoprudnyi, Moscow oblast, Russia
c Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow, Russia
d Weierstrass Institute of Applied Analysis and Stochastics, Berlin, Germany
e National Research University Higher School of Economics, Moscow, Russia
Abstract:
A strongly convex function of simple structure (for example, separable) is minimized under affine constraints. A dual problem is constructed and solved by applying a fast gradient method. The necessary properties of this method are established relying on which, under rather general conditions, the solution of the primal problem can be recovered with the same accuracy as the dual solution from the sequence generated by this method in the dual space of the problem. Although this approach seems natural, some previously unpublished rather subtle results necessary for its rigorous and complete theoretical substantiation in the required generality are presented.
Key words:
minimization of strongly convex functionals, primal-dual methods, fast gradient method, dual problem, regularization of dual problems, restart technique, strong convexity, PageRank problem.
Received: 03.02.2016 Revised: 12.05.2016
Citation:
A. S. Anikin, A. V. Gasnikov, P. E. Dvurechensky, A. I. Tyurin, A. V. Chernov, “Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints”, Zh. Vychisl. Mat. Mat. Fiz., 57:8 (2017), 1270–1284; Comput. Math. Math. Phys., 57:8 (2017), 1262–1276
Linking options:
https://www.mathnet.ru/eng/zvmmf10598 https://www.mathnet.ru/eng/zvmmf/v57/i8/p1270
|
Statistics & downloads: |
Abstract page: | 294 | Full-text PDF : | 58 | References: | 44 | First page: | 7 |
|