Skip to main content
SpringerLink
Log in

Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints

  • Published:
Computational Mathematics and Mathematical Physics Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A. V. Gasnikov, E. V. Gasnikova, Yu. E. Nesterov, and A. V. Chernov, “Efficient numerical methods for entropy-linear programming problems,” Comput. Math. Math. Phys. 56 (4), 514–524 (2016).

    Article  MathSciNet  MATH  Google Scholar 

  2. Y. Nesterov, “Primal-dual subgradient methods for convex problems,” Math. Program. Ser. B 120 (1), 261–283 (2009).

    Article  MathSciNet  MATH  Google Scholar 

  3. A. Nemirovski, S. Onn, and U. G. Rothblum, “Accuracy certificates for computational problems with convex structure,” Math. Operations Res. 35 (1), 52–78 (2010).

    Article  MathSciNet  MATH  Google Scholar 

  4. O. Devolder, PhD Thesis (CORE UCL, 2013).

    Google Scholar 

  5. Yu. E. Nesterov, Doctoral Dissertation in Mathematics and Physics (Moscow Inst. of Physics and Technology, Dolgoprudnyi, 2013). www.mathnet.ru/php/seminars.phtml?option_lang=rus&presentid=8313.

    Google Scholar 

  6. Yu. Nesterov, “New primal-dual subgradient methods for convex optimization problems with functional constraints,” International Workshop on Optimization and Statistical Learning, January 11–16, 2015 (France, Les Houches, 2015). http://lear.inrialpes.fr/workshop/osl2015/program.html.

    Google Scholar 

  7. Yu. Nesterov, “Complexity bounds for primal-dual methods minimizing the model of objective function,” CORE Discussion Papers, 2015/03 (2015).

    Google Scholar 

  8. A. Anikin, P. Dvurechensky, A. Gasnikov, A. Golov, A. Gornov, Yu. Maximov, M. Mendel, and V. Spokoiny, “Modern efficient numerical approaches to regularized regression problems in application to traffic demands matrix calculation from link loads,” Proceedings of International Conference ITAS-2015, Sochi, Russia, September 2015 (2015). arXiv:1508.00858.

    Google Scholar 

  9. A. V. Gasnikov, E. V. Gasnikova, E. I. Ershov, P. E. Dvurechensky, and A. A. Lagunovskaya, “Search for stochastic equilibria in equilibrium traffic flow models,” Tr. Mosk. Fiz.-Tekh. Inst. 7 (4), 114–128 (2015). arXiv:1505.07492.

    Google Scholar 

  10. A. V. Gasnikov, P. E. Dvurechensky, Yu. V. Dorn, and Yu. V. Maksimov, “Numerical methods of searching for equilibrium flow distributions in Beckmann’s and stable dynamic models,” Mat. Model. 28 (10), 40–64 (2016). arXiv:1506.00293.

    MathSciNet  MATH  Google Scholar 

  11. A. V. Gasnikov, P. E. Dvurechensky, D. I. Kamzolov, Yu. E. Nesterov, V. G. Spokoinyi, P. I. Stetsyuk, A. L. Suvorikova, and A. V. Chernov, “Search for equilibria in multistage traffic flow models,” Tr. Mosk. Fiz.-Tekh. Inst. 7 (4), 143–155 (2015). https://mipt.ru/upload/medialibrary/ffe/143-155.pdf.

    Google Scholar 

  12. A. V. Gasnikov, P. E. Dvurechensky, Yu. E. Nesterov, V. G. Spokoinyi, and A. L. Suvorikova, “Superposition of the balancing and universal gradient methods for searching for an entropy-smoothed Wasserstein barycenter and equilibria in multistage traffic flow models,” Tr. Mosk. Fiz.-Tekh. Inst. 8 (3), 5–24 (2016). arXiv:1506.00292.

    Google Scholar 

  13. A. V. Gasnikov, P. E. Dvurechensky, and I. N. Usmanova, “On the nontriviality of fast (accelerated) randomized methods,” Tr. Mosk. Fiz.-Tekh. Inst. 8 (2), 67–100 (2016). arXiv:1508.02182.

    Google Scholar 

  14. Z. Allen-Zhu and L. Orecchia, Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent, e-print (2014). arXiv:1407.1537.

    Google Scholar 

  15. A. S. Nemirovski and D. B. Yudin, Complexity of Problems and Efficiency of Optimization Methods (Nauka, Moscow, 1979) [in Russian]. http://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf.

    Google Scholar 

  16. V. A. Zorich, Mathematical Analysis of Problems in Natural Sciences (MTsNMO, Moscow, 2008) [in Russian].

    Google Scholar 

  17. B. T. Polyak, Introduction to Optimization (Nauka, Moscow, 1983; Optimization Software, New York, 1987).

    MATH  Google Scholar 

  18. A. Chernov, P. Dvurechensky, and A. Gasnikov, “Fast primal-dual gradient method for strongly convex minimization problems with linear constraints,” International Conference on Discrete Optimization and Operations Research, Vladivostok, Russian Iceland, September 19–23, 2016 (Springer, Berlin, 2016), pp. 584–595. arXiv:1605.02970.

    Google Scholar 

  19. A. Nemirovski, Lectures on Modern Convex Optimization Analysis, Algorithms, and Engineering Applications (SIAM, Philadelphia, 2013). http://www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf.

    MATH  Google Scholar 

  20. Yu. Nesterov, “Gradient methods for minimizing composite functions,” Math. Prog. 140 (1), 125–161 (2013).

    Article  MathSciNet  MATH  Google Scholar 

  21. Yu. Nesterov, “Universal gradient methods for convex optimization problems,” CORE Discussion Paper, 2013/63 (2013).

    Google Scholar 

  22. A. V. Gasnikov and P. E. Dvurechensky, “Stochastic intermediate gradient method for convex optimization problems,” Dokl. Math. 93 (2), 148–151 (2016).

    Article  MathSciNet  MATH  Google Scholar 

  23. P. Dvurechensky and A. Gasnikov, “Stochastic intermediate gradient method for convex problems with inexact stochastic oracle,” J. Optim. Theory Appl., 1–25 (2016). arXiv:1411.2876.

  24. A. V. Gasnikov, P. E. Dvurechensky, and Yu. E. Nesterov, “Stochastic gradient methods with an inexact oracle,” Tr. Mosk. Fiz.-Tekh. Inst. 8 (1), 41–91 (2016). arxiv:1411.4218

    MATH  Google Scholar 

  25. A. V. Gasnikov, D. I. Kamzolov, and M. A. Mendel’, “Basic constructions over convex optimization algorithms and their applications to deriving new estimates for strongly convex problems,” Tr. Mosk. Fiz.-Tekh. Inst. 8 (3), 25–42 (2016). arXiv:1603.07701.

    Google Scholar 

  26. A. Pătraşcu, PhD Thesis (University Politehnica of Bucharest, Bucharest, 2015). http://acse.pub.ro/person/ion-necoara/.

    Google Scholar 

  27. B. Cox, A. Juditsky, and A. Nemirovski, Decomposition Techniques for Bilinear Saddle Point Problems and Variational Inequalities with Affine Monotone Operators on Domains Given by Linear Minimization Oracles, e-print (2015). arXiv:1506.02444.

    Google Scholar 

  28. A. V. Gasnikov and D. Yu. Dmitriev, “On efficient randomized algorithms for finding the PageRank vector,” Comput. Math. Math. Phys. 55 (3), 349–365 (2015). arXiv:1410.3120.

    Article  MathSciNet  MATH  Google Scholar 

  29. H. Nikaido, Convex Structures and Economic Theory (Academic, New York, 1968; Mir, Moscow, 1972).

    MATH  Google Scholar 

  30. A. V. Gasnikov and Yu. E. Nesterov, “Universal method for stochastic composite optimization problems,” arXiv:1604.05275.

  31. B. O’Donoghue and E. Candes, “Adaptive restart for accelerated gradient schemes,” Foundations Comput. Math. 15, 715–732 (2015).

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of System Dynamics and Control Theory, Siberian Branch, Russian Academy of Sciences, Irkutsk, 664033, Russia

    A. S. Anikin

  2. Moscow Institute of Physics and Technology, Dolgoprudnyi, Moscow oblast, 141700, Russia

    A. V. Gasnikov

  3. Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow, 127051, Russia

    A. V. Gasnikov & P. E. Dvurechensky

  4. Weierstrass Institute of Applied Analysis and Stochastics, Berlin, 10117, Germany

    P. E. Dvurechensky & A. V. Chernov

  5. National Research University Higher School of Economics, Moscow, 101000, Russia

    A. I. Tyurin

Authors
  1. A. S. Anikin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. V. Gasnikov
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. P. E. Dvurechensky
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. A. I. Tyurin
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. A. V. Chernov
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to A. V. Gasnikov.

Additional information

Original Russian Text © A.S. Anikin, A.V. Gasnikov, P.E. Dvurechensky, A.I. Tyurin, A.V. Chernov, 2017, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2017, Vol. 57, No. 8, pp. 1270–1284.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Anikin, A.S., Gasnikov, A.V., Dvurechensky, P.E. et al. Dual approaches to the minimization of strongly convex functionals with a simple structure under affine constraints. Comput. Math. and Math. Phys. 57, 1262–1276 (2017). https://doi.org/10.1134/S0965542517080048

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S0965542517080048

Keywords

Search

Navigation