A. V. Gasnikov, E. V. Gasnikova, Yu. E. Nesterov, A. V. Chernov, “Efficient numerical methods for entropy-linear programming problems”, Zh. Vychisl. Mat. Mat. Fiz., 56:4 (2016), 523–534; Comput. Math. Math. Phys., 56:4 (2016), 514

Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki

RUS ENG

JOURNALS PEOPLE ORGANISATIONS CONFERENCES SEMINARS VIDEO LIBRARY PACKAGE AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	General information
	Latest issue
	Archive
	Impact factor

	Search papers
	Search references

	RSS
	Latest issue
	Current issues
	Archive issues
	What is RSS

Zh. Vychisl. Mat. Mat. Fiz.:
Year:
Volume:
Issue:
Page:
	Find

Personal entry:
Login:
Password:
	Save password
	Enter
	Forgotten password?
	Register

Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, 2016, Volume 56, Number 4, Pages 523–534
DOI: https://doi.org/10.7868/S0044466916040098 (Mi zvmmf10368)

This article is cited in 25 scientific papers (total in 25 papers)

Efficient numerical methods for entropy-linear programming problems

A. V. Gasnikov^ab, E. V. Gasnikova^c, Yu. E. Nesterov^d, A. V. Chernov^c

^a Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), Moscow
^b National Research University "Higher School of Economics" (HSE), Moscow
^c Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region
^d Center for Operat. Research and Econometrics Universite Catholigue de Louvain, Belgium

Full-text PDF (369 kB) Citations (25)

References:

PDF

HTML

DOI: https://doi.org/10.7868/S0044466916040098

Abstract: Entropy-linear programming (ELP) problems arise in various applications. They are usually written as the maximization of entropy (minimization of minus entropy) under affine constraints. In this work, new numerical methods for solving ELP problems are proposed. Sharp estimates for the convergence rates of the proposed methods are established. The approach described applies to a broader class of minimization problems for strongly convex functionals with affine constraints.

Key words: entropy-linear programming, fast gradient method, regularization, dual problem.

Funding agency	Grant number
Russian Foundation for Basic Research	15-31-70001_мол_а_мос 14-01-00722_а 15-31-20571_мол_а_вед
Russian Science Foundation	14-50-00150
Gasnikova, Nesterov, and Chernov acknowledge the support of the Russian Foundation for Basic Research, project nos. 15-31-70001 mol_a_mos, 14-01-00722-a, and 15-31-20571-mol_a_ved. Theorem 2 was proved at the Institute for Information Transmission Problems of the Russian Academy of Sciences by Gasnikov, who acknowledges the support of the Russian Science Foundation, project no. 14-50-00150.

Received: 04.03.2015
Revised: 28.05.2015

English version:
Computational Mathematics and Mathematical Physics, 2016, Volume 56, Issue 4, Pages 514–524
DOI: https://doi.org/10.1134/S0965542516040084

Bibliographic databases:

Document Type: Article

UDC: 519.658

Language: Russian

Citation: A. V. Gasnikov, E. V. Gasnikova, Yu. E. Nesterov, A. V. Chernov, “Efficient numerical methods for entropy-linear programming problems”, Zh. Vychisl. Mat. Mat. Fiz., 56:4 (2016), 523–534; Comput. Math. Math. Phys., 56:4 (2016), 514–524

Citation in format AMSBIB

\Bibitem{GasGasNes16}

\by A.~V.~Gasnikov, E.~V.~Gasnikova, Yu.~E.~Nesterov, A.~V.~Chernov

\paper Efficient numerical methods for entropy-linear programming problems

\jour Zh. Vychisl. Mat. Mat. Fiz.

\yr 2016

\vol 56

\issue 4

\pages 523--534

\mathnet{http://mi.mathnet.ru/zvmmf10368}

\crossref{https://doi.org/10.7868/S0044466916040098}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3540556}

\elib{https://elibrary.ru/item.asp?id=25772311}

\transl

\jour Comput. Math. Math. Phys.

\yr 2016

\vol 56

\issue 4

\pages 514--524

\crossref{https://doi.org/10.1134/S0965542516040084}

\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000376415600002}

\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84971247449}

Linking options:

https://www.mathnet.ru/eng/zvmmf10368

https://www.mathnet.ru/eng/zvmmf/v56/i4/p523

This publication is cited in the following 25 articles:

Egor Gladin, Alexander Gasnikov, Pavel Dvurechensky, “Accuracy Certificates for Convex Minimization with Inexact Oracle”, J Optim Theory Appl, 204:1 (2025)
Peiyun Xue, Zhenan Dong, Yan Qiang, Wen Zheng, Jing Bai, Xiang Gao, “RankMatch: Environmental sound semi-supervised learning with audio classification propensity”, Applied Acoustics, 231 (2025), 110515
Pavel Dvurechensky, Petr Ostroukhov, Alexander Gasnikov, César A. Uribe, Anastasiya Ivanova, “Near-optimal tensor methods for minimizing the gradient norm of convex functions and accelerated primal–dual tensor methods”, Optimization Methods and Software, 2024, 1
Meruza Kubentayeva, Demyan Yarmoshik, Mikhail Persiianov, Alexey Kroshnin, Ekaterina Kotliarova, Nazarii Tupitsa, Dmitry Pasechnyuk, Alexander Gasnikov, Vladimir Shvetsov, Leonid Baryshev, Alexey Shurupov, “Primal-dual gradient methods for searching network equilibria in combined models with nested choice structure and capacity constraints”, Comput Manag Sci, 21:1 (2024)
Olga Yufereva, Michael Persiianov, Pavel Dvurechensky, Alexander Gasnikov, Dmitry Kovalev, “Decentralized convex optimization on time-varying networks with application to Wasserstein barycenters”, Comput Manag Sci, 21:1 (2024)
Yue Xie, Zhongjian Wang, Zhiwen Zhang, “Randomized Methods for Computing Optimal Transport Without Regularization and Their Convergence Analysis”, J Sci Comput, 100:2 (2024)
Artem Vasin, Alexander Gasnikov, Pavel Dvurechensky, Vladimir Spokoiny, “Accelerated gradient methods with absolute and relative noise in the gradient”, Optimization Methods and Software, 38:6 (2023), 1180
Nazarii Tupitsa, Pavel Dvurechensky, Darina Dvinskikh, Alexander Gasnikov, Encyclopedia of Optimization, 2023, 1
A. S. Anikin, V. V. Matyukhin, D. A. Pasechnyuk, “Accelerated proximal envelopes: application to componentwise methods”, Comput. Math. Math. Phys., 62:2 (2022), 336–345
Runhua Wang, Yaohua Liu, Qing Ling, “Byzantine-Resilient Resource Allocation Over Decentralized Networks”, IEEE Trans. Signal Process., 70 (2022), 4711
E. V. Kotlyarova, A. V. Gasnikov, E. V. Gasnikova, D. V. Yarmoshik, “Poisk ravnovesii v dvukhstadiinykh modelyakh raspredeleniya transportnykh potokov po seti”, Kompyuternye issledovaniya i modelirovanie, 13:2 (2021), 365–379
C. A. Uribe, S. Lee, A. Gasnikov, A. Nedic, “A dual approach for optimal algorithms in distributed optimization over networks”, Optim. Method Softw., 36:1 (2021), 171–210
E. A. Vorontsova, A. V. Gasnikov, P. E. Dvurechenskii, A. S. Ivanova, D. A. Pasechnyuk, “Numerical methods for the resource allocation problem in a computer network”, Comput. Math. Math. Phys., 61:2 (2021), 297–328
Dmitry Pasechnyuk, Vladislav Matyukhin, Lecture Notes in Computer Science, 12755, Mathematical Optimization Theory and Operations Research, 2021, 176
C. A. Uribe, S. Lee, A. Gasnikov, A. Nedic, “A dual approach for optimal algorithms in distributed optimization over networks”, 2020 Information Theory and Applications Workshop (ITA), IEEE, 2020
Cesar A. Uribe, Soomin Lee, Alexander Gasnikov, Angelia Nedic, 2020 Information Theory and Applications Workshop (ITA), 2020, 1
Pavel Dvurechensky, Alexander Gasnikov, Sergey Omelchenko, Alexander Tiurin, Lecture Notes in Computer Science, 12095, Mathematical Optimization Theory and Operations Research, 2020, 406
D. R. Baymurzina, A. V. Gasnikov, E. V. Gasnikova, P. E. Dvurechenskii, E. I. Ershov, M. B. Kubentayeva, A. A. Lagunovskaya, “Universal method of searching for equilibria and stochastic equilibria in transportation networks”, Comput. Math. Math. Phys., 59:1 (2019), 19–33
A. V. Gasnikov, Yu. E. Nesterov, “Universal method for stochastic composite optimization problems”, Comput. Math. Math. Phys., 58:1 (2018), 48–64
P. Dvurechensky, D. Dvinskikh, A. Gasnikov, C. A. Uribe, A. Nedic, “Decentralize and randomize: faster algorithm for Wasserstein barycenters”, 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Advances in Neural Information Processing Systems, eds. S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. CesaBianchi, R. Garnett, 2018, 10760–10770

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles

Журнал вычислительной математики и математической физики

Computational Mathematics and Mathematical Physics

Statistics & downloads:
Abstract page:	630
Full-text PDF :	172
References:	117
First page:	21

Registration to the website

Logotypes