Алгоритмическая оптимизация для задач с большим числом переменных

КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

ОБЩИЕ СВЕДЕНИЯ

Номер проекта 17-11-01027

НазваниеАлгоритмическая оптимизация для задач с большим числом переменных

Руководитель Нестеров Юрий Евгеньевич, Доктор физико-математических наук

Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский университет "Высшая школа экономики" , г Москва

Конкурс №18 - Конкурс 2017 года «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами»

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-203 - Теория оптимизации и исследование операций

Ключевые слова Методы оптимизации, градиентный метод, метод Ньютона, универсальный метод, выпуклая оптимизация, локальная оптимизация, задачи большой размерности, машинное обучение, глубокое обучение, устойчивость линейных динамических систем, линейные системы с переключениями, оптимизация функции Ляпунова, разреженность, относительная точность, масштабирующий эллипсоид

Код ГРНТИ27.47.19

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

Аннотация
Начиная с 2010 года, область численных методов оптимизации переживает громадный всплеск активности исследований. Развитие техники (увеличение объемов носителей информации и оперативной памяти, скорости работы процессоров), а также программного обеспечения (архитектура больших хранилищ данных, параллельные алгоритмы) позволяют моделировать реальные социальные, экономические, инженерные, физические системы с большим числом элементов или агентов, накапливать и обрабатывать огромные массивы данных в биологии, Интернете, физике с целью извлечения из них полезной информации. Так или иначе, во всех указанных областях возникают задачи оптимизации с большим (десятки тысяч) и огромным (миллионы и миллиарды) числом переменных или ограничений. Одним из главных примеров являются задачи BigData, в частности задачи анализа данных и машинного обучения, которые сводятся к задачам выпуклой оптимизации типа минимизации эмпирического риска. Основной сложностью решения таких задач является большое или огромное число переменных. В последние несколько лет в фокусе исследований по BigData оптимизации помимо выпуклых оказались также невыпуклые задачи, возникающие при обучении глубоких нейронных сетей (http://www.deeplearningbook.org/). Существенная доля работ, принятых на ведущие мировые конференции по анализу данных, таких как International Conference on Machine Learning (http://icml.cc/), Conference on Learning Theory (http://www.learningtheory.org), Neural Information Processing Systems (https://nips.cc/) за это время так или иначе связаны с оптимизацией. Организуются специальные конференции, посвященные исследованиям на стыке машинного обучения и оптимизации, например, Optimization and Statistical Learning '13,'15,'17. Другим важным приложением численных методов оптимизации являются задачи моделирования транспортных сетей мегаполисов. В используемых моделях возникают задачи поиска равновесного распределения транспортных потоков по путям, которые сводятся к задаче минимизации функции специального вида. Число переменных в этой задаче соответствует числу всех различных разумных маршрутов в транспортной сети, которое равно примерно квадрату числа вершин в графе транспортной сети, что для Москвы сотни тысяч. Аналогичные задачи возникают в моделях равновесия в транспортно-экономических системах, применяемых, например, для оптимизации тарифной политики РЖД, а также в моделях компьютерных сетей, применяемых для оценки объемов трафика, передаваемого между узлами сети. Транспортному моделированию посвящено большое количество журналов, например, Transportation science, Transportation research и другие. Задачам оптимизации, возникающим в транспорте и в телекоммуникациях посвящаются целые секции на престижных конференциях по оптимизации, например, на проходящем раз в три года The International Symposium on Optimization '12, '15. Кроме того, многие прикладные задачи электродинамики, математической экономики, популяционной динамики, и т.д. сводятся к проблеме устойчивости динамической линейной системы с переключениями. Возникающие в связи с этим задачи оптимизации функции Ляпунова системы в заданных классах функций имеют большие размерности и часто являются невыпуклыми. Эти задачи широко изучаются в настоящее время. Так, на крупнейших международных конференциях задачам устойчивости систем с переключениями регулярно посвящается много докладов, либо организуются специальные секции. Например, на ежегожных ILAS Conferences (http://www.ilasic.org/conferences/ilas.html), IEEE Conference on Decision and Control (http://cdc2016.ieeecss.org/), SIAM Conference on Applied Linear Algebra (http://www.siam.org/meetings/la15/). Наконец, в таких журналах как IEEE Transactions on Automatic Control и Systems and Control Letters, которые являются одними из самых высокорейтинговых математических журналов (импакт фактор 2.777 и 1.908 соответственно), регулярно публикуются статьи, изучающие проблемы устойчивости линейных динамических систем. Наконец, в инженерии при проектировании механических конструкций (Shape design, Truss topology design), состоящих из большого числа элементов возникают выпуклые задачи оптимизации с числом переменных порядка числа элементов в конструкции, которое может достигать десятков тысяч. Аналогичные задачи могут возникать при разработке материалов со специальными свойствами с использованием уравнений математической физики и методов конечных элементов. Эти задачи широко изучаются в настоящее время. Так, в системе Web of Science по теме Shape optimization проиндексировано более 10 тыс. работ за последние 5 лет. Целью предлагаемого исследования является разработка численных методов оптимизации, способных решать задачи высокой (т.е. большой или огромной) размерности в перечисленных приложениях. Отличительной особенностью разрабатываемых методов будет их универсальность и адаптивность, позволяющая работать без априорной информации о типе задачи (например, гладкая она или нет) или о ее параметрах (например, степень гладкости). Решение таких задач невозможно без эффективного использования их структуры. Например, в задачах машинного обучения представление целевой функции как суммы большого числа слагаемых будет использовано для существенного увеличения скорости работы алгоритмов. Особое внимание будет уделено теоретическим оценкам скорости сходимости предлагаемых алгоритмов, что позволит оценивать качество приближенного решения, вычисленного алгоритмами. Также будут проводиться численные эксперименты для проверки работы алгоритмов на реальных задачах. Для достижения поставленной цели в проекте планируется решить четыре задачи, каждая из которых мотивирована своей прикладной областью. 1. Задача “Универсальные градиентные методы (УГМ)”. Разработать линейку универсальных градиентных методов (УГМ) для задач выпуклой оптимизации. Приложения: моделирование равновесий в транспортных сетях мегаполисов, моделирование компьютерных сетей, машинное обучение, анализ данных. 2. Задача “Невыпуклая оптимизация (НВО)”. Разработать новые методы первого и второго порядка, в т.ч. универсальные, для задач невыпуклой, в т.ч. стохастической, оптимизации. Приложения: машинное обучение, анализ данных. 3. Задача “Линейные динамические системы (ЛДС)”. Разработать методы выпуклой оптимизации для исследования устойчивости линейных динамических систем. Приложения: моделирование электрических сетей, экономическое моделирование, экологическое моделирование. 4. Задача “Выпуклые задачи огромной размерности (ВЗОР)”. Разработать новые градиентные методы выпуклой оптимизации для задач огромной размерности. Приложения: оптимальный структурный дизайн (Shape design) деформируемого твердого тела в промышленности, автомобилестроении, самолетостроении.

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Публикации

1. Баяндина А. Adaptive Mirror Descent for Constrained Optimization. Proceedings of Conference: Constructive Nonsmooth Analysis and Related Topics, St.Petersbourg (год публикации - 2017)
10.1109/CNSA.2017.7973937

2. Протасов В.Ю. Comprehensive Lyapunov functions for linear dynamical systems Automatica (год публикации - 2018)

3. Воронцова Е.А., Гасников А.В., Горбунов Э.А. Ускоренные спуски по случайному направлению с неевклидовой прокс-структурой Автоматика и Телемеханика (год публикации - 2018)

4. Гасников А.В., Нестеров Ю.Е. Универсальный метод для задач стохастической композитной минимизации Журнал Вычислительной Математики и Математической Физики (год публикации - 2018)

5. Нестеров Ю.Е. Complexity bounds for primal-dual methods minimizing the model of objective function Mathematical Programming (год публикации - 2017)
10.1007s/10107-017-1188-6

6. Двуреченский П., Гасников А., Камзолов Д. Universal Intermediate Triangle Method Optimization Methods and Software (год публикации - 2018)

7. Нестеров Ю.Е., Протасов В.Ю. Computing closest stable non-negative matrix SIMAX (год публикации - 2018)

8. Грапилия Д., Нестеров Ю.Е. Accelerated regularized Newton methods for minimizing composite functions SIAM Journal on Optimization (год публикации - 2018)

9. Гуминов С., Гасников А., Аникин А., Горнов А. A universal modification of the linear coupling method Optimization Methods and Software (год публикации - 2018)

10. Баяндина А. Adaptive Stochastic Mirror Descent for Constrained Optimization. Proceedings of Conference: Constructive Nonsmooth Analysis and Related Topics. St.Petersbiug (год публикации - 2017)
10.1109/CNSA.2017.7973938

11. Тюрин А.И., Гасников А.В. Быстрый градиентный спуск для задач выпуклой минимизации с оракулом, выдающим (δ,L)-модель функции в запрошенной точке Журнал Вычислительной Математики и Математической Физики (год публикации - 2018)

12. Нестеров Ю.Е., Шихман В. Dual subgradient method with averaging for optimal resource allocation EJOR (год публикации - 2018)

Публикации

1. Гасников А.В., Гасникова Е.В., Нестеров Ю.Е. Dual Methods for finding Equilibriums in Mixed Models of Flow Distribution in Large Transportation Networks Computational Mathematics and Mathematical Physics, 58(9) 1395-1403 (год публикации - 2018)

2. Нестеров Ю.Е. Complexity bounds of primal-dual methods based on the model of objective function Mathematical Programming, 171(1-2), 311-330 (год публикации - 2018)

3. Чиконе А.,Гулильми, Протасов В. Linear dynamical switching systems on graphs Nonlinear Analysis: Hybrid Systems, 29, 165-186 (год публикации - 2018)

4. Гулельми Н., Протасов В. On the Closest Stable/Unstable Nonnegative Matrix and Related Stability Radii SIAM Journal of Matrix Analysis and Applications, 39(4) 1642-1669 (год публикации - 2018)

5. Нестеров Ю., Шихман В. Dual subgradient method with averaging for optimal resource allocation European Journal of Operational Research, 270, 907-916 (год публикации - 2018)

6. Нестеров Ю., Шихман В. Computation of Fisher–Gale Equilibrium by Auction Journal of Operations Research Society China (год публикации - 2018)
10.1007/s40305-018-0195-5

7. Гасников А., Нестеров Ю. Universal Method for Stochastic Composite Optimization Problems Computational Mathematics and Mathematical Physics, 58(1), 48-64 (год публикации - 2018)

8. Гуминов С., Гасников А., Аникин А., Горнов А. A universal modification of the linear coupling Optimization Methods and Software (год публикации - 2018)
10.1080/10556788.2018.1517158

9. Тюрин А., Гасников А. Fast Gradient method for minimization problems based on (d,L)-model of the oracle of the objective function Computational Mathematics and Mathematical Physics (год публикации - 2019)

10. Тюрин А. Adaptive fast gradient method in stochastic optimization tasks Computational Mathematics and Mathematical Physics (год публикации - 2019)

Публикации

1. Ю.Е. Нестеров, В.Ю. Протасов Nesterov_Protasov_Computing closest stable non-negative matrix SIAM Journal on Matrix Analysis and Applications (год публикации - 2020)

2. В. Ю. Протасов Protasov,_How to make the Perron eigenvalue simple Calcolo, 56:17 (год публикации - 2019)
10.1007/s10092-019-0314-7

3. Аникин А.С., Большакова О.А., Гасников А.В., Горнов А.Ю., Ермак Т.В., Макаренко Д.В., Морозов В.П., Нетеребский Б.О., Яковлев П.А. Anikin_et_al_Local Algorithms for Minimizing the Force Field for 3D Representation of Macromolecules Computational Mathematics and Mathematical Physics, Vol. 59, No. 12, pp. 1994–2008 (год публикации - 2019)
10.1134/S0965542519120030

4. Воронцова Е.А., Гасников А.В., Горбунов Э.А., Двуреченский П.Е. Vorontsova_et_al_Accelerated Gradient-Free Optimization Methods with a Non-Euclidean Proximal Operator Automation and Remote Control, Volume 80, Issue 8, pp 1487–1501 (год публикации - 2019)
10.1134/S0005117919080095

5. Гасников А.В., Двуреченский П.Е., Горбунов Э.А., Воронцова Е.А., Селиханович Д.С., Урибе Ц. Gasnikov_et_al_Optimal Tensor Methods in Smooth Convex and Uniformly Convex Optimization Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:1374-1391 (год публикации - 2019)

6. Двуреченский П.Е., Гасников А.В., Крошнин А.В. Dvurechensky_Gasnikov_Kroshnin_Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn’s Algorithm Proceedings of the 35th International Conference on Machine Learning, PMLR 80:1367-1376 (год публикации - 2018)

7. Нестеров Ю.Е. Nesterov_Implementable tensor methods in unconstrained convex optimization Mathematical Programming (год публикации - 2019)
10.1007/s10107-019-01449-1