Основные конструкции над алгоритмами выпуклой оптимизации и их приложения к получению новых оценок для сильно выпуклых задач
Автор: Гасников А.В., Камзолов Д.И., Мендель М.А.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Информатика, вычислительная техника и упровление
Статья в выпуске: 3 (31) т.8, 2016 года.
Бесплатный доступ
В статье собраны вместе основные современные конструкции работы с алгоритмами (численными методами) решения задач выпуклой оптимизации. В частности, с помощью искусственного введения неточности в вычисление градиента, следуя Ю.Е. Нестерову, рассматривается «адаптивная игра на гладкости задачи», позволяющая использовать методы, настроенные на гладкие задачи для решения негладких задач; рассматривается конструкция рестартов, позволяющая получить из численного метода, ищущего решение задачи выпуклой оптимизации, метод, пригодный к использованию для задач сильно выпуклой оптимизации; рассматривается прием регуляризации, позволяющий сводить любую выпуклую задачу к сильно выпуклой. Все эти (и некоторые другие) конструкции (например, композитной оптимизации) описываются, исходя из одной общей линии - руководствуясь принципом «бритвы Оккама»: попытаться изложить современное состояние «оптимальных» численных методов выпуклой оптимизации в пространствах больших размеров (для детерминированных постановок: размерность пространства больше необходимого числа итераций). Статья написана по просьбам коллег и студентов, планирующих использовать собранные в статье конструкции в своей работе.
Композитная оптимизация, быстрый градиентный метод, неточный оракул, универсальный метод ю.е. нестерова, рестарт-техника, регуляризация
Короткий адрес: https://sciup.org/142186145
IDR: 142186145
Список литературы Основные конструкции над алгоритмами выпуклой оптимизации и их приложения к получению новых оценок для сильно выпуклых задач
- Гасников А.В. Стохастическая и Huge-scale оптимизация. Курс лекций для студентов МФТИ, НМУ, ВШЭ. Весна 2016. http://www.mathnet.ru/php/conference.phtml?option_lang=rus&eventID=25&confid=394
- Nesterov Yu. Gradient methods for minimizing composite functions//Math. Prog. 2013. V. 140, N 1. P. 125-161
- Devolder O. Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization. CORE UCL, PhD thesis, March 2013
- Devolder O., Glineur F., Nesterov Yu. First order methods of smooth convex optimization with inexact oracle//Math. Progr. Ser. A. 2014. V. 146 (1-2). P. 37-75
- Devolder O., Glineur F., Nesterov Yu. Intermediate gradient methods for smooth convex problems with inexact oracle//CORE Discussion Paper 2013/17. 2013
- Nesterov Yu. Universal gradient methods for convex optimization problems//Math. Prog. 2015. V. 152, N 1-2. P. 381-404; CORE Discussion Paper 2013/63. 2013
- Devolder O., Glineur F., Nesterov Yu. First order methods with inexact oracle: the smooth strongly convex case//CORE Discussion Paper 2013/16. 2013
- Гасников А.В., Двуреченский П.Е., Камзолов Д.И., Нестеров Ю.Е., Спокойный В.Г., Стецюк П.И., Суворикова А.Л., Чернов А.В. Поиск равновесий в многостадийных транспортных моделях//Труды МФТИ. 2015. Т. 7, № 4. С. 143-155
- Гасников А.В., Двуреченский П.Е., Камзолов Д.И. Градиентные и прямые методы с неточным оракулом для задач стохастической оптимизации//Динамика систем и процессы управления. Труды Международной конференции, посвященной 90-летию со дня рождения академика Н.Н. Красовского. Екатеринбург, 15-20 сентября 2014. Издательство: Институт математики и механики УрО РАН им. Н.Н. Красовского (Екатеринбург). 2014. С. 111-117. arXiv:1502.06259
- Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979
- Nemirovski A. Lectures on modern convex optimization analysis, algorithms, and engineering applications. Philadelphia: SIAM, 2013. http://www2.isye.gatech.edu/∼nemirovs/Lect_ModConvOpt.pdf
- Гасников А.В., Двуреченский П.Е. Стохастический промежуточный метод для задач выпуклой оптимизации//ДАН РАН. 2016. Т. 467, № 2. С. 131-134. arXiv:1411.2876
- Juditsky A., Nesterov Yu. Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization//Stoch. System. 2014. V. 4, N 1. P. 44-80
- Гасников А.В., Двуреченский П.Е., Нестеров Ю.Е. Стохастические градиентные методы с неточным оракулом//Труды МФТИ. 2016. Т. 8, № 1. С. 41-91. arxiv:1411.4218
- Аникин А.С., Гасников А.В., Двуреченский П.Е., Тюрин А.И., Чернов А.В. Двойственные подходы к задачам минимизации сильно выпуклых функционалов простой структуры при аффинных ограничениях//ЖВМ и МФ. 2017. Т. 57 (в печати). arXiv:1602.01686
- Нестеров Ю.Е. Введение в выпуклую оптимизацию. М.: МЦНМО, 2010
- Гасников А.В., Двуреченский П.Е., Спокойный В.Г., Стецюк П.И., Суворикова А.Л. Суперпозиция метода балансировки и универсального градиентного метода для поиска энтропийно-сглаженного барицентра Вассерштейна и равновесий в многостадийных моделях транспортных потоков//Труды МФТИ. 2016. Т. 8, № 3. C. 5-24. arXiv:1506.00292
- Гасников А.В., Двуреченский П.Е., Усманова И.Н. О нетривиальности быстрых (ускоренных) рандомизированных методов//Труды МФТИ. 2016. Т. 8, № 2. С. 67-100. arXiv:1508.02182
- Аникин А.С., Гасников А.В., Горнов А.Ю. О неускоренных эффективных методах решения разреженных задач квадратичной оптимизации//Труды МФТИ. 2016. Т. 8, № 2. С. 44-59. arXiv:1602.01124
- Гасников А.В., Лагуновская А.А., Усманова И.Н., Федоренко Ф.А. Безградиентные прокс-методы с неточным оракулом для негладких задач выпуклой стохастической оптимизации на симплексе//Автоматика и телемеханика. 2016. № 10. C. 57-77. arXiv:1412.3890
- Гасников А.В., Крымова Е.А., Лагуновская А.А., Усманова И.Н., Федоренко Ф.А. Стохастическая онлайн оптимизация. Одноточечные и двухточечные нелинейные многорукие бандиты. Выпуклый и сильно выпуклый случаи//Автоматика и телемеханика. 2017 (в печати). arXiv:1509.01679
- Bubeck S. Convex optimization: algorithms and complexity//In Foundations and Trends in Machine Learning. 2015. V. 8, N 3-4. P. 231-357. arXiv:1405.4980
- Nesterov Y.E. Efficiency of coordinate descent methods on large scale optimization problem//SIAM Journal on Optimization. 2012. V. 22, N 2. P. 341-362
- Nesterov Yu. Random gradient-free minimization of convex functions//CORE Discussion Paper 2011/1. 2011
- Devolder O. Stochastic first order methods in smooth convex optimization//CORE Discussion Paper 2011/70. 2011
- Nesterov Y. Smooth minimization of non-smooth function//Math. Program. Ser. A. 2005. V. 103, N 1. P. 127-152
- 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 conference ITAS-2015. Russia, Sochi, September, 2015. arXiv:1508.00858
- Гасников А.В., Гасникова Е.В., Двуреченский П.Е., Ершов Е.И., Лагуновская А.А. Поиск стохастических равновесий в транспортных моделях равновесного распределения потоков//Труды МФТИ. 2015. Т. 7, № 4. С. 114-128. arXiv:1505.07492
- Allen-Zhu Z., Orecchia L. Linear coupling: An ultimate unification of gradient and mirror descent//e-print, 2014. arXiv:1407.1537
- Юдицкий А.Б., Назин А.В., Цыбаков А.Б., Ваятис Н. Рекуррентное агрегирование оценок методом зеркального спуска с усреднением//Проблемы передачи информации. 2005. Т. 41:4, С. 78-96
- Васильев Ф.П. Методы оптимизации. М.: МЦНМО, 2011
- Bertsekas D.P. Nonlinear programming. Athena Scientific, 1999
- Поляк Б.Т. Введение в оптимизацию. М.: УРСС, 2014
- Nemirovski A., Onn S., Rothblum U.G. Accuracy certificates for computational problems with convex structure//Mathematics of Operation Research. 2010. V. 35, N 1. P. 52-78
- Allen-Zhu Z., Hazan E. Optimal Black-Box Reductions Between Optimization Objectives//e-print, 2016. arXiv:1603.05642
