Суперпозиция метода балансировки и универсального градиентного метода для поиска энтропийно-регуляризованного барицентра Вассерштейна и равновесий в многостадийных моделях транспортных потоков

Суперпозиция метода балансировки и универсального градиентного метода для поиска энтропийно-регуляризованного барицентра Вассерштейна и равновесий в многостадийных моделях транспортных потоков

Автор: Гасников А.В., Двуреченский П.Е., Спокойный В.Г., Стецюк П.И., Суворикова А.Л.

Журнал: Труды Московского физико-технического института @trudy-mipt

Рубрика: Информатика, вычислительная техника и упровление

Статья в выпуске: 3 (31) т.8, 2016 года.

Бесплатный доступ

Представлен обзор современных численных методов поиска барицентра Вассерштейна конечного семейства вероятностных мер с одинаковым конечным носителем. Такие задачи в последнее время стали очень популярны в связи с всевозможными приложениями к сравнительному анализу изображений, в частности, к обнаружению разладок в ряде изображений. Например, подобные задачи возникают при изучении деятельности головного мозга. В основном мы исходили из цикла работ M. Cuturi с соавторами. Общая идея этих работ - найти барицентр вероятностных мер согласно энтропийно-регуляризованному расстоянию Вассерштейна. Такое (регуляризованное) расстояние можно заметно эффективнее посчитать, чем исходное расстояние Вассерштейна. В одной из работ отмеченного цикла [8] содержалась идея сочетания метода Синхорна (балансировки) для решения внутренней задачи (расчета соответствующих регуляризованных расстояний и их субградиентов) и быстрого градиентного метода для решения внешней задачи (поиск барицентра). К сожалению, в описанном авторами виде метод оказался не пригодным для использования на практике (не было также никаких теоретических гарантий его сходимости). В [1] показано, как можно доработать данный метод (в частности, доказана сходимость предложенной модификации). Однако мы были сконцентрированы на другом приложении (к поиску равновесий в многостадийных транспортных моделях). В данной работе мы рассматриваем оба отмеченных приложения. Главным результатом работы является разработка в общем случае (не только для этих двух приложений) концепции суперпозиции методов, когда мы можем выделить в исходной задаче часть переменных, по которым задача эффективно решается внутреннем методом (но допускается, что лишь приближенно) при замороженных остальных переменных. А по оставшейся группе переменных запускается внешний метод, на каждой итерации которого требуется запускать внутренний метод. В статье получен частичный ответ на довольно общий вопрос: как оптимально сочетать эти методы (внутренней и внешний), т.е. насколько точно надо решать на каждой итерации внешнего метода внутреннюю задачу, чтобы минимизировать общее время работы метода при заданной точности решения, которую хотим получить?

Еще

Седловая задача, энтропия, метод балансировки, метод синхорна, универсальный метод, неточный оракул, задача монжа-канторовича, расстояние вассерштейна, барицентр вассерштейна

Короткий адрес: https://sciup.org/142186147

IDR: 142186147

Список литературы Суперпозиция метода балансировки и универсального градиентного метода для поиска энтропийно-регуляризованного барицентра Вассерштейна и равновесий в многостадийных моделях транспортных потоков

  • Гасников А.В., Двуреченский П.Е., Камзолов Д.И., Нестеров Ю.Е., Спокойный В.Г., Стецюк П.И., Суворикова А.Л., Чернов А.В. Поиск равновесий в многостадийных транспортных моделях//Труды МФТИ. 2015. Т. 7, № 4. С. 143-155
  • Гасников А.В., Дорн Ю.В., Нестеров Ю.Е, Шпирко С.В. О трехстадийной версии модели стационарной динамики транспортных потоков//Математическое моделирование. 2014. Т. 26:6. C. 34-70. arXiv:1405.7630
  • Гасников А.В. Об эффективной вычислимости конкурентных равновесий в транспортно-экономических моделях//Математическое моделирование. 2015. Т. 27, № 12. С. 121-136. arXiv:1410.3123
  • Бабичева Т.С., Гасников А.В., Лагуновская А.А., Мендель М.А. Двухстадийная модель равновесного распределения транспортных потоков//Труды МФТИ 2015. Т. 7, № 3. С. 31-41. https://mipt.ru/upload/medialibrary/971/31-41.pdf
  • Гасников А.В., Гасникова Е.В., Мациевский С.В., Усик И.В. О связи моделей дискретного выбора с разномасштабными по времени популяционными играми загрузок//Труды МФТИ. 2015. Т. 7, № 4. С. 129-142. arXiv:1511.02390
  • Гасников А.В., Гасникова Е.В., Нестеров Ю.Е., Чернов А.В. Об эффективных численных методах решения задач энтропийно-линейного программирования//ЖВМ и МФ. 2016. Т. 56, № 4. С. 523-534. arXiv:1410.7719
  • Agueh M., Carlier G. Barycenters in the Wasserstein space//SIAM J. Math. Anal. 2011. V. 43, N 2. P. 904-924
  • Cuturi M., Doucet A. Fast Computation of Wasserstein Barycenters//ICML. 2014. http://www.iip.ist.i.kyoto-u.ac.jp/member/cuturi/
  • Benamou J.D., Carlier G., Cuturi M., Nenna L., Peyr´e G. Iterative Bregman Projections for Regularized Transportation Problems//e-print, 2015. (to appear in SISC) arXiv:1412.5154
  • Cuturi M., Peyr´e G., Rolet A. A Smoothed Dual Formulation for Variational Wasserstein Problems//e-print, 2015. arXiv:1503.02533
  • Cuturi M. Sinkhorn Distances: Lightspeed Computation of Optimal Transport//NIPS. 2013
  • Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979. http://www2.isye.gatech.edu/simnemirovs/Lect_EMCO.pdf
  • Boissard E., Le Gouic T., Loubes J.-M. Distribution’s Template Estimate with Wasserstein Metrics//e-print, 2013. (to be published in Bernoulli) arXiv:1111.5927
  • Bigot J., Klein T. Consistent estimation of a population barycenter in the Wasserstein space//e-print, 2015. arXiv:1212.2562
  • Nesterov Y. Smooth minimization of nonsmooth function//Math. Program. Ser. A. 2005. V. 103, N 1. P. 127-152
  • Fercoq O., Richtarik P. Accelerated, Parallel and Proximal Coordinate Descent//e-print, 2013. arXiv:1312.5799
  • Qu Z., Richtarik P. Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity//e-print, 2014. arXiv:1412.8060
  • Boyd S., Parikh N., Chu E., Peleato B., Eckstein J. Distributed optimization and statistical learning via the alternating direction method of multipliers//Foundations and Trends in Machine Learning. 2011. V. 3(1). P. 1-122. http://stanford.edu/boyd/papers.html
  • Boyd S., Vandenberghe L. Convex optimization. Cambridge University Press, 2004. http://stanford.edu/boyd/cvxbook/
  • Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983
  • Nemirovski A. Lectures on modern convex optimization analysis, algorithms, and engineering applications. Philadelphia: SIAM, 2013. http://www2.isye.gatech.edu/simnemirovs/Lect_ModConvOpt.pdf
  • Rabin J., Pey´er G., Delon J. Bernot M. Wasserstein barycenter and its applications to texture mixing//LNCS. 2011. Proc. SSVM’11. Springer. V. 6667. P. 435-446. https://hal.archives-ouvertes.fr/hal-00476064/document
  • Bonnel N., Pfister H. Sliced Wasserstein barycenter of multiple densities // Harvard Technical Report. 2013. TR-02-13. ftp://ftp.deas.harvard.edu/techreports/tr-02-13.pdf
  • Стецюк П.И. Методы эллипсоидов и 𝑟-алгоритмы. Кишинев: Эврика, 2014
  • Стецюк П.И., Гасников А.В. NLP-программы и 𝑟-алгоритм в задаче энтропийнолинейного программирования//Теория оптимальных решений. Киев: Институт кибернетики им. В.М.Глушкова НАН Украины, 2015. С. 73-78
  • Franklin J., Lorenz J. On the scaling of multidimensional matrices//Linear Algebra and its applications. 1989. V. 114. P. 717-735
  • Nesterov Yu. Universal gradient methods for convex optimization problems//CORE Discussion Paper 2013/63. 2013; Math. Program. Ser. A. 2015. V. 152. P. 381-404. https://www.uclouvain.be/cps/ucl/doc/core/documents/coredp2013_26web.pdf
  • Nesterov Yu. http://www.youtube.com/watch?v=Fm9h92pcbvg
  • Гасников А.В., Двуреченский П.Е., Дорн Ю.В., Максимов Ю.В. Численные методы поиска равновесного распределения потоков в моделях Бэкмана и стабильной динамики//Математическое моделирование. 2016. Т. 28, № 10. С. 40-64. arXiv:1506.00293
  • Гасников А.В., Гасникова Е.В., Ершов Е.И., Двуреченский П.Е., Лагуновская А.А. Поиск стохастических равновесий в моделях равновесного распределения потоков//Труды МФТИ. 2015. Т. 7, № 4. С. 114-128. arXiv:1505.07492
  • Гасников А.В, Двуреченский П.Е., Камзолов Д.И. Градиентные и прямые методы с неточным оракулом для задач стохастической оптимизации//Динамика систем и процессы управления. Труды Международной конференции, посвященной 90-летию со дня рождения академика Н.Н. Красовского. Екатеринбург, 15-20 сентября 2014. Издательство: Институт математики и механики УрО РАН им. Н.Н. Красовского (Екатеринбург). 2014. С. 111-117. arXiv:1502.06259
  • Devolder O. Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization. CORE UCL, PhD thesis, March 2013
  • Anikin A., Dvurechensky P., Gasnikov A., Golov A., Gornov A., Maximov Yu., Mendel M., Spokoiny V. Modern efficient numerical approaches to regularized regression problems in application to traffic demands matrix calculation from link loads//Proceedings of International Сonference ITAS-2015. Russia, Sochi, September, 2015. arXiv:1508.00858
  • Zhang F. The Schur Complement and Its Applications. Springer, 2005
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp