Лекция 9 (часть 1). Разреженные задачи Huge-scale оптимизации

1. Метод условного градиента и линейный минимизационный оракул (Франк–Вульф (ФВ)). В каких случаях (на каких множествах) метод оптимальный (оценки Немировского–Гузмана).
2. Разреженность метода ФВ, возникающая в случае оптимизации на симплексе. Пример G. Lugosi для LASSO.
3. Сочетание разреженности метода ФВ с разреженностью матрицы при минимизации квадратичного функционала на симплексе. Приложение к задаче PageRank.
4. Об эффективности линейного минимизационного оракула и динамическом программировании. Приложение к седловым задачам. Приложения метода ФВ к различным задачам композитной оптимизации.
5. О связи наличия эффективного линейного минимизационного оракула и возможности сжатия задачи путем перехода к двойственной. Пример поиск равновесного распределения потоков в транспортных сетях.
6. Truss Topology Design.
7. ПГМ с l1-нормой (альтернативное понимание (при сепарабельных ограничениях): неускоренный покомпонентный метод с выбором максимальной компоненты) при оптимизации на симплексе, на неотрицательном ортанте. Пример квадратичный функционал, функционал S-класса. Приложение к задаче PageRank.
8. Разреженность и рандомизация в задачах huge-scale оптимизации (продолжение).
Литература:
- Nesterov Yu., Shpirko S. http://www.optimization-online.org/DB_FILE/2012/08/3590.pdf
- Jaggi M. Revisiting Frank–Wolfe: Projection-free sparse convex optimization // Proceedings of the 30th International Conference on Machine Learning, Atlanta, Georgia, USA, 2013. https://sites.google.com/site/frankwolfegreedytutorial/
- Bubeck S. Convex optimization: algorithms and complexity // In Foundations and Trends in Machine Learning. 2015. V. 8. no. 3-4. P. 231–357. arXiv:1405.4980 Guzman C., Nemirovski A. On lower complexity bounds for large-scale smooth convex optimization // Journal of Complexity. 2015. arXiv:1307.5001
- Harchaoui Z., Juditsky A., Nemirovski A. Conditional gradient algorithms for norm-regularized smooth convex optimization // Math. Program. Ser. B. 2015. http://www2.isye.gatech.edu/~nemirovs/ccg_revised_apr02.pdf
- 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 http://www.mathnet.ru/php/presentation.phtml?option_lang=rus&presentid=11955
- Аникин А.С., Гасников А.В., Горнов А.Ю., Камзолов Д.И., Максимов Ю.В., Нестеров Ю.Е. Эффективные численные методы решения задачи PageRank для дважды разреженных матриц // Труды МФТИ. 2015. Т. 7. № 4. С. 74–94. arXiv:1508.07607
- Гасников А.В., Двуреченский П.Е., Дорн Ю.В., Максимов Ю.В. Численные методы поиска равновесного распределения потоков в модели Бэкмана и модели стабильной динамики // Математическое моделирование. 2016. Т. 28. arXiv:1506.00293
- Аникин А.С., Гасников А.В., Горнов А.Ю., Максимов Ю.В. О рандомизированном методе зеркального спуска для решения разреженных задач выпуклой оптимизации огромных размеров // Труды МФТИ. 2016. Т. 8. arXiv:1602.00594
- Аникин А.С., Гасников А.В., Горнов А.Ю., Максимов Ю.В. О неускоренных эффективных методах решения разреженных задач квадратичной оптимизации // e-print, 2016. arXiv:1602.01124