Все
 
 
 


Прямо-двойственный метод зеркального спуска для условных задач стохастической оптимизации
 
Код статьиS004446690003533-7-1
DOI10.31857/S004446690003533-7
Тип публикации Статья
Статус публикации Опубликовано
Авторы
Баяндина А. С. 
Аффилиация: Факультет управления и прикладной математики Национального исследовательского Университета «Московский физико-технический институт»
Адрес: 141700 Долгопрудный, М. о., Институтский пер., 9
Гасников А. В.
Аффилиация:
Кафедра Математических основ управления Национального исследовательского Университета «Московский физико-технический институт»
Ин-т проблем передачи информации РАН
Адрес: 141700 Долгопрудный, М. о., Институтский пер., 9; 127051 Москва, Большой каретный пер., 19, стр. 1
Гасникова Е. В.
Аффилиация: МФТИ
Адрес: 141700 Долгопрудный, М. о., Институтский пер., 9
Мациевский C. В.
Аффилиация: Балтийский федеральный университет им. И. Канта
Адрес: 236016 Калининград, ул. А. Невского, 14
Название журналаЖурнал вычислительной математики и математической физики
ВыпускТом 58 Номер 11
Страницы1794-1803
Аннотация

В данной статье изучается возможность распространения метода зеркального спуска для задач выпуклой стохастической оптимизации на выпуклые задачи условной стохастической оптимизации (с функциональными ограничениями вида неравенств). Предлагается конкретный метод, состоящий в том, что осуществляется шаг обычного зеркального спуска, если ограничения не сильно нарушены и осуществляется шаг зеркального спуска по нарушенному ограничению, в случае если оно нарушено достаточно сильно. При специальном выборе параметров метода устанавливается (оптимальная для данного класса задач) оценка скорости его сходимости (с точными оценками вероятностей больших уклонений). Устанавливается (в детерминированном случае) также прямо-двойственность предложенного метода. Другими словами, показывается, что по генерируемой методом последовательности можно восстановить решение двойственной задачи (с той же точностью, с которой решается прямая задача). Обсуждается эффективность метода для задач с огромным числом ограничений. Отметим, что в полученную в работе оценку убывания зазора двойственности не входит неизвестный размер решения двойственной задачи. Библ.23.

Ключевые словаметод зеркального спуска, стохастическая выпуклая оптимизация, условная оптимизация, вероятности больших уклонений, рандомизация
Источник финансированияРабота А.В. Гасникова выполнена в ИППИ РАН при финансовой поддержке РНФ(проект № 14-50-00150); работа Е.В. Гасниковой выполнена при финансовой поддержке РФФИ (код проекта 15-31-20571-мол_а_вед) и гранта Президента РФ МД-1320.2018.1.
Получено15.01.2019
Дата публикации15.01.2019
Цитировать   Скачать pdf Для скачивания PDF необходимо авторизоваться
Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

всего просмотров: 1217

Оценка читателей: голосов 0 

1. Немировский А.С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979.
2. Аникин А.С., Гасников А. В., Горнов А. Ю. Р андомизация и разреженность в задачах huge-scale оптимизации на примере работы метода зеркального спуска // Труды МФТИ. 2016. Т. 8. № 1. С. 11–24. arXiv:1602.00594
3. Ким К., Нестеров Ю., Скоков В., Черкасский Б. Эффективные алгоритмы для дифференцирования и задачи экстремали // Экономика и математические методы.– 1984. – Т . 20. – С. 309–318.
4. Nesterov Yu. Lexicographic differentiation of nonsmooth functions // Math. Prog.– 2005. – V. 104. – no. 2–3. – P. 669–700.
5. Гасников А.В., Двуреченский П. Е., Дорн Ю. В., Максимов Ю. В. Численные методы поиска равновесного распределения потоков в модели Бэкмана и модели стабильной динамики // Математическое моделирование. 2016. Т. 28. № 10. С. 40–64. arXiv:1506.00293
6. Juditsky A., Lan G., Nemirovski A., Shapiro A. Stochastic approximation approach to stochastic programming // SIAM Journal on Optimization. 2009. V. 19. № 4. P. 1574–1609.
7. Boucheron S., Lugoshi G., Massart P. Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press, 2013.
8. Nesterov Yu., Shpirko S. Primal-dual subgradient method for huge-scale linear conic problem // SIAM Journal on Optimization. 2014. V. 24. № . 3. P. 1444–1457. http://www.optimization-online.org/DB_FILE/2012/08/3590.pdf 
9. Nesterov Yu. New primal-dual subgradient methods for convex optimization problems with functional constraints // International Workshop “Optimization and Statistical Learning”. January 11–16. France, Les Houches, 2015. http://lear.inrialpes.fr/workshop/osl2015/program.html 
10. Аникин А.С., Гасников А. В., Двуреченский П. Е., Тюрин А. И., Чернов А. В. Двойственные подходы к задачам минимизации сильно выпуклых функционалов простой структуры при аффинных ограничениях // ЖВМ и МФ. 2017. Т. 57. № 6. (в печати) arXiv:1602.01686
11. Nemirovski A., Onn S., Rothblum U. G. Accuracy certificates for computational problems with convex structure // Mathematics of Operation Research. 2010. V. 35. № 1. P. 52–78.
12. Cox B., Juditsky A., Nemirovski A. 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
13. Juditsky A., Nemirovski A. First order methods for nonsmooth convex large-scale optimization, I, II. // Optimization for Machine Learning. // Eds. S. Sra, S. Nowozin, S. Wright. – MIT Press, 2012.
14. Гасников А.В., Крымова Е. А., Лагуновская А. А., Усманова И. Н., Федоренко Ф. А. Стохастическая онлайн оптимизация. Одноточечные и двухточечные нелинейные многорукие бандиты. Выпуклый и сильно выпуклый случаи // Автоматика и телемеханика. 2017. (в печати) arXiv:1509.01679
15. Duchi J. C. Introductory Lectures on Stochastic Optimization // IAS/Park City Mathematics Series. 2016. P. 1–84. http://stanford.edu/~jduchi/PCMIConvex/Duchi16.pdf 
16. Nesterov Yu. Subgradient methods for convex function with nonstandart growth properties // e-print, 2016. http://www.mathnet.ru:8080/PresentFiles/16179/growthbm_nesterov.pdf 
17. Duchi J.C., Shalev-Shwartz S., Singer Y., Tewari A. Composite objective mirror descent // Proceedings of COLT.– 2010. – P. 14–26.
18. Juditsky A., Nesterov Yu. Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization // Stoch. System.– 2014. – V. 4. – no. 1. – P. 44–80.
19. Аникин А.С., Гасников А. В., Горнов А. Ю., Камзолов Д. И., Максимов Ю. В., Нестеров Ю. Е. Эффективные численные методы решения задачи PageRank для дважды разреженных матриц // Труды МФТИ. 2015. Т. 7. № 4. С. 74–94. arXiv:1508.07607
20. https://github.com/anastasiabayandina/Mirror 
21. Beck A., Ben-Tal A., Guttmann-Beck N., Tetruashvili L. The CoMirror algorithm for solving nonsmooth constrained convex problems // Operations Research Letters.– 2011. V. 38. No. 6. P. 493–498.
22. Juditsky A., Nemirovski A., Tauvel C. Solving variational inequalities with Stochastic Mirror-Prox algorithm // Stochastic Systems.– 2011. V. 1. no. 1. P. 17–58.
23. Lan G., Zhou Z. Algorithms for stochastic optimization with expectation constraints // e-print, 2016.
24. http://pwp.gatech.edu/guanghui-lan/wp-content/uploads/sites/330/2016/08/SPCS8–19–16.pdf

Система Orphus

Загрузка...
Вверх