Geodesic
Efficient numerical methods for entropy-linear programming problems
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 4, pp. 523-534 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{ZVMMF_2016_56_4_a1,
     author = {A. V. Gasnikov and E. V. Gasnikova and Yu. E. Nesterov and A. V. Chernov},
     title = {Efficient numerical methods for entropy-linear programming problems},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {523--534},
     year = {2016},
     volume = {56},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_4_a1/}
}
TY  - JOUR
AU  - A. V. Gasnikov
AU  - E. V. Gasnikova
AU  - Yu. E. Nesterov
AU  - A. V. Chernov
TI  - Efficient numerical methods for entropy-linear programming problems
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2016
SP  - 523
EP  - 534
VL  - 56
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_4_a1/
LA  - ru
ID  - ZVMMF_2016_56_4_a1
ER  - 
%0 Journal Article
%A A. V. Gasnikov
%A E. V. Gasnikova
%A Yu. E. Nesterov
%A A. V. Chernov
%T Efficient numerical methods for entropy-linear programming problems
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2016
%P 523-534
%V 56
%N 4
%U http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_4_a1/
%G ru
%F ZVMMF_2016_56_4_a1
A. V. Gasnikov; E. V. Gasnikova; Yu. E. Nesterov; A. V. Chernov. Efficient numerical methods for entropy-linear programming problems. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 56 (2016) no. 4, pp. 523-534. http://geodesic.mathdoc.fr/item/ZVMMF_2016_56_4_a1/

[1] Fang S.-C., Rajasekera J. R., Tsao H.-S. J., Entropy optimization and mathematical programming, Kluwer's International Series, 1997 | MR

[2] Popkov Yu. S., Teoriya makrosistem: Ravnovesnye modeli, URSS, M., 2013

[3] Vilson A. Dzh., Entropiinye metody modelirovaniya slozhnykh sistem, Nauka, M., 1978

[4] International workshops on Bayesian inference and maximum entropy methods in science and engineering, AIP Conf. Proceedings (holds every year from 1980)

[5] Kapur J. N., Maximum - entropy models in science and engineering, John Wiley Sons, Inc., 1989 | MR | Zbl

[6] Golan A., Judge G., Miller D., Maximum entropy econometrics: Robust estimation with limited data, Wiley, Chichester, 1996 | Zbl

[7] Jaynes E. T., Probability theory. The logic of science, Cambridge University Press, Cambridge, 2003 | MR | Zbl

[8] Gasnikov A. V., Markovskie modeli makrosistem, 2014, arXiv: 1412.2720

[9] Gasnikov A. V., Klenov S. L., Nurminskii E. A., Kholodov Ya. A., Shamrai N. B., Vvedenie v matematicheskoe modelirovanie transportnykh potokov, s prilozheniyami M. L. Blanka, K. V. Vorontsova i Yu. V. Chekhovicha, E. V. Gasnikovoi, A. A. Zamyatina i V. A. Malysheva, A. V. Kolesnikova, Yu. E. Nesterova i S. V. Shpirko, A. M. Raigorodskogo, s predisloviem rukovoditelya departamenta transporta g. Moskvy M. S. Liksutova, ed. A. V. Gasnikov, MTsNMO, M., 2013 http://www.mou.mipt.ru/gasnikov1129.pdf

[10] Gasnikova E. V., “Dvoistvennye multiplikativnye algoritmy dlya zadach entropiino-lineinogo programmirovaniya”, Zh. vychisl. matem. i matem. fiz., 49:3 (2009), 453–464 | MR | Zbl

[11] Nemirovskii A. S., Yudin D. B., Slozhnost zadach i effektivnost metodov optimizatsii, Nauka, M., 1979 http://www2.isye.gatech.edu/ñemirovs/Lect_EMCO.pdf | MR

[12] Kelbert M. Ya., Sukhov Yu. M., Markovskie tsepi kak otpravnaya tochka teorii sluchainykh protsessov i ikh prilozhenii. Veroyatnost i statistika v primerakh i zadachakh, v. 2, MTsNMO, M., 2010

[13] Kats M., Veroyatnost i smezhnye voprosy v fizike, Mir, M., 1965

[14] Malyshev V. A., Pirogov S. A., “Obratimost i neobratimost v stokhasticheskoi khimicheskoi kinetike”, Uspekhi matem. nauk, 63:1(379) (2008), 4–36 | Zbl

[15] Gasnikov A. V., Gasnikova E. V., “Ob entropiino-podobnykh funktsionalakh, voznikayuschikh v stokhasticheskoi khimicheskoi kinetike pri kontsentratsii invariantnoi mery ivk achestve funktsii Lyapunova dinamiki kvazisrednikh”, Matem. zametki, 94:6 (2013), 819–827, arXiv: 1410.3126 | DOI | MR | Zbl

[16] Vedenyapin V. V., Adzhiev S. Z., “Entropiya po Boltsmanu i Puankare”, Uspekhi matem. nauk, 69:6(420) (2014), 45–80 | DOI | MR | Zbl

[17] Gasnikov A. V., Gasnikova E. V., Mendel M. A., Chepurchenko K. V., “Evolyutsionnye vyvody entropiinoi modeli rascheta matritsy korrespondentsii”, Matem. modelirovanie, 28 (2016), arXiv: 1508.01077

[18] Nesterov Y., “Smooth minimization of non-smooth function”, Math. Program. Ser. A, 103:1 (2005), 127–152 | DOI | MR | Zbl

[19] Nesterov Yu. E., Vvedenie v vypukluyu optimizatsiyu, MTsNMO, M., 2010

[20] Gasnikova E. V., Modelirovanie dinamiki makrosistem na osnove kontseptsii ravnovesiya, Diss. na soisk. stepeni kand. fiz.-mat. nauk, spets. 05.13.18, 2012

[21] Devolder O., Glineur F., Nesterov Y., “Double smoothing technique for large-scale linearly constrained convex optimization”, SIAM J. Optimizat., 22:2 (2012), 702–727 | DOI | MR | Zbl

[22] Gasnikov A. V., Dorn Yu. V., Nesterov Yu. E., Shpirko S. V., “O trekhstadiinoi versii modeli statsionarnoi dinamiki transportnykh potokov”, Matem. modelirovanie, 26:6 (2014), 34–70, arXiv: 1405.7630 | Zbl

[23] Gasnikov A. V., Dvurechenskii P. E., Nesterov Yu. E., “Stokhasticheskie gradientnye metody s netochnym orakulom”, Trudy MFTI, 8 (2016), arXiv: 1411.4218

[24] Juditsky A., Nemirovski A., “First order methods for nonsmooth convex large-scale optimization. II: Utilizing problem's structure”, Optimization for Machine Learning, eds. S. Sra, S. Nowozin, S. Wright, MIT Press, 2012 http://www2.isye.gatech.edu/ñemirovs/MLOptChapterII.pdf

[25] Bubeck S., Theory of convex optimization for machine learning, 2014, arXiv: 1405.4980

[26] Nazin A. V., Tremba A. A., “Igrovoi algoritm zerkalnogo spuska v zadache robastnogo PageRank”, Avtomatika i telemekhanika, 2015

[27] Boyd S., et al., Open Software, http://www.cvxpy.org/en/latest/examples/index.html

[28] Cuturi M., Personal page, http://www.iip.ist.i.kyoto-u.ac.jp/member/cuturi/

[29] Pele O., Werman M., “Fast and robust earth mover's distances”, ICCV'09 (2009) http://www.cs.huji.ac.il/w̃erman/Papers/ICCV2009.pdf

[30] Franklin J., Lorenz J., “On the scaling of multidimensional matrices”, Linear Algebra and its applications, 114 (1989), 717–735 | DOI | MR | Zbl