Развитие теории адаптивных и универсальных численных методов решения задач выпуклой оптимизации с функциональными ограничениями и большим объёмом данных

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

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

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

Номер проекта 18-71-00048

НазваниеРазвитие теории адаптивных и универсальных численных методов решения задач выпуклой оптимизации с функциональными ограничениями и большим объёмом данных

Руководитель Стонякин Федор Сергеевич, Доктор физико-математических наук

Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Крымский федеральный университет имени В.И. Вернадского" , Республика Крым

Конкурс №29 - Конкурс 2018 года по мероприятию «Проведение инициативных исследований молодыми учеными» Президентской программы исследовательских проектов, реализуемых ведущими учеными, в том числе молодыми учеными

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

Ключевые слова негладкая оптимизация, функциональные ограничения, большие объёмы данных, адаптивный (самонастраивающийся) метод, универсальный метод, метод зеркального спуска, вариационное неравенства, универсальный проксимальный зеркальный метод, седловая задача, универсальный метод множителей Лагранжа, задача Ферма-Торричелли-Штейнера, обратные задачи, компактная липшицевость градиента

Код ГРНТИ27.41.00

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

Аннотация
Работа по предлагаемому проекту будет направлена на достижение следующих основных целей: 1. Для случая большого числа ограничений будут предложены модификации адаптивных методов зеркального спуска для решения задач условной негладкой оптимизации, рассмотренные ранее в - A. Bayandina, P. Dvurechensky, A. Gasnikov, F. Stonyakin, A. Titov (2017). Mirror Descent and Convex Optimization Problems With Non-Smooth Inequality Constraints.// Available: https://arxiv.org/abs/1710.06612. - Stonyakin F., Titov A. One Mirror Descent Algorithm for Convex Constrained Optimization Problems with non-standard growth properties. // Avaible at https://arxiv.org/abs/1803.01329. Суть предлагаемых модификаций заключается в том, что в некоторой ситуации для ограничения g(x), равного максимуму конечного набора функционалов g_k(x), на "непродуктивном" шаге можно вместо субградиента g использовать субградиент отдельно взятого ограничения g_k, игнорируя остальные. Этот подход должен сэкономить время работы алгоритма. Планируется доказать оценки на скорость сходимости этих методов, с помощью программ продемонстрировать экономию времени. Намечено применить эту идеологию к функционалам, возникающим в задачах децентрализованной оптимизации, а также в задаче Truss Topology Design. 2. На базе универсального (адаптивного) проксимального зеркального метода для вариационных неравенств (недавно предложен А.В. Гасниковым, Ф.С. Стонякиным, П.Е. Двуреченским и А.А. Титовым), а также аналога метода Ю.Е. Нестерова для вариационных неравенств с сильно монотонным полем (недавно предложен руководителем проекта Ф.С. Стонякиным) будут исследованы методы для выпукло-вогнутых седловых задач различного уровня гладкости. С использованием метода множителей Лагранжа на базе этих методов для седловых задам намечено исследование подхода к условным задачам с функциональными ограничениями различного уровня гладкости. Такой методикой можно рассматривать задачи выпуклой оптимизации с линейными ограничениями вида равенств и выпуклыми ограничениями вида неравенств. Если нельзя эффективно (в частности, явно) построить двойственную задачу, то можно решать седловую задачу, получаемую при использовании принципа множителей Лагранжа. Стоит отметить, что в этом случае метод универсального проксимального зеркального спуска оптимален с точки зрения нижних оракульных оценок. 3. Будут исследованы адаптивные универсальные методы решения задач оптимизации в бесконечномерных пространствах. Поясним подробнее. В последние годы Ю.Е. Нестеровым, А.В. Гасниковым и другими их соавторами активно развивается теория универсальных методов решения задач гладкой и негладкой выпуклой оптимизации с адаптивным выбором шага и критерием остановки. Отметим, что в недавней работе Nesterov Yu. Universal gradient methods for convex optimization problems // Math. Program. Ser. A. – 2015. – V. 152. – P. 381–404 предложен аналог градиентного спуска для решения задач выпуклой оптимизации с адаптивным выбором шага. При этом такой подход позволяет самому методу в некотором смысле осуществлять «настройку» на уровень гладкости задачи. В частности, в случае липшицевости (гёльдеровости) (суб)градиента целевой функции, данная методика не предполагает знания точного значения этой константы Липшица (Гёльдера). В указанной выше работе приводятся примеры прикладных задач, которые удачно могут быть решены на базе указанной методики. Например, это задача проектирования сети газоснабжения, а также известная задача Ферма-Торричелли-Штейнера о нахождении кратчайшей сети, соединяющей фиксированных набор точек. Далее, в 2009 - 2016 годах руководителем проекта Ф.С. Стонякиным были исследованы компактные аналоги условий Липшица и абсолютной непрерывности для отображений в бесконечномерных пространствах. Идея этого подхода заключается в замене исходной нормы бесконечномерного пространства на функционал Минковского некоторого выпуклого симметричного компакта. В частности, всякое компактно абсолютно непрерывное отображение вещественного отрезка в банахово пространство почти всюду дифференцируемо. В то же время абсолютно непрерывное отображение со значениями в бесконечномерном пространстве может быть нигде не дифференцируемым, как отмечено в известной монографии Э. Хилле и Р. Филлипса "Функциональный анализ и полугруппы". В ходе работ по предлагаемому проекту намечается соединить идеологию адаптивных (самонастраивающихся) универсальных методов решения задач оптимизации Ю.Е. Нестерова и предложить соответствующие методы для решения бесконечномерных задач с целевыми функционалами, удовлетворяющими компактному аналога условия Липшица (Гельдера) для градиента. В частности, недавно появилась работа об общем адаптивном универсальном способе решения большого числа обратных задач Gasnikov A.V., Kabanikhin S.I., Mohammed A.A.M., Shishlenin M.A. Convex optimization in Hilbert space with application to inverse problems // Appl. Numer. Math. – 2017. Available https://arxiv.org/ftp/arxiv/papers/1703/1703.00267.pdf Такие задачи возникают в самых разных прикладных задачах. Основная идея этой работы - сведение обратной задачи к задаче квадратичной оптимизации (в случае линейной постановки прямой задачи), которую можно решать наиболее быстрым численным методом, не требующим никакой априорной информации о спектральных свойствах задачи. Новизна тут не только в адаптивности подхода, но и в том, что прорабатывается неточность, неизбежно возникающая из-за рассмотрения пространства функций (а не конечномерного пространства), и значение градиента функционала можно получать лишь приближенно. Естественно возникает вопрос о выборе шага сетки. Ставится цель разработать метод, который по заданной точности решения будет предусматривать адаптивный выбор адекватного шага сетки. При этом не очевидно, что надо использовать именно самый быстрый с точки зрения оптимизации метод. Причина в том, что быстрые оптимизационные методы, как правило, чувствительны к неточности, а более медленные методы часто обладают лучшими свойствами робастности. Интересно исследовать возможность подбора метода для решения обратных выгодный в смысле общих затрат времени метод (затраты = число итераций (это и есть быстрота метода, для быстрых методов это число меньше) * (стоимость итерации - для быстрых методов придется более точно все считать и потому итерация будет дороже)). Изучение этих вопросов составляет часть плана работ по проекту.

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

Публикации

1. Титов А.А., Стонякин Ф.С., Гасников А.В., Алкуса М.С. Mirror Descent and Constrained Online Optimization Problems Optimization and Applications. 9th International Conference OPTIMA2018 (Petrovac, Montenegro, October 1–5, 2018). Revised Selected Papers. Communications in Computer and Information Science., Optimization and Applications. 9th International Conference OPTIMA2018 (Petrovac, Montenegro, October 1–5, 2018). Revised Selected Papers. Communications in Computer and Information Science. — 2019. — Vol. 974. — P. 64–78. (год публикации - 2019)
10.1007/978-3-030-10934-9_5

2. Пасечнюк Д.А., Стонякин Ф.С. Об одном методе минимизации выпуклой липшицевой функции двух переменных на квадрате Компьютерные исследования и моделирование (год публикации - 2019)

3. Гасников А.В., Двуреченский П.Е., Стонякин Ф.С., Титов А.А. Адаптивный проксимальный метод для вариационных неравенств Журнал вычислительной математики и математической физики (год публикации - 2019)
10.1134/S0965542519050075

4. Стонякин Ф.С., Двинских Д.М., Двуреческий П.Е., Крошнин А.В., Кузнецова О.А., Агафонов А.Д., Гасников А.В., Тюрин А.И., Цезарь Урибе, Пасечнюк Д. А., Артамонов С.Ю. Gradient methods for problems with inexact model of the objective Lecture Notes in Computer Science, Vol. 11548, pp. 97–114, 2019. (год публикации - 2019)
10.1007/978-3-030-22629-9_8

5. Стонякин Ф.С. Адаптация к величинам погрешностей для некоторых методов оптимизации градиентного типа Труды Института математики и механики УрО РАН, Т. 25, № 4. С. 210-225. (год публикации - 2019)
10.21538/0134-4889-2019-25-4-210-225

6. Стонякин Ф.С., Воронцова Е.А., Алкуса М.С. New Version of Mirror Prox for Variational Inequalities with Adaptation to Inexactness Communications in Computer and Information Science, Vol. 1145. P. 427 - 442. (год публикации - 2020)
10.1007/978-3-030-38603-0_31

7. Стонякин Ф.С., Степанов А.Н., Гасников А.В., Титов А.А. Метод зеркального спуска для условных задач оптимизации с большими значениями норм субградиентов функциональных ограничений Компьютерные исследования и моделирование (год публикации - 2020)
10.20537/2076-7633-2020-12-2-301-317

8. Иванова А.С., Стонякин Ф.С., Пасечнюк Д.А., Воронцова Е.А., Гасников А.В. Adaptive Mirror Descent for the Network Utility Maximization Problem IFAC PapersOnline (год публикации - 2020)

9. П.Е. Двуреченский, А.В. Гасников, Е.А. Нурминский, Ф.С. Стонякин Advances in Low-Memory Subgradient Optimization Dvurechensky P.E., Gasnikov A.V., Nurminski E.A., Stonyakin F.S. (2020) Advances in Low-Memory Subgradient Optimization.In: Bagirov A., Gaudioso M., Karmitsa N., Mäkelä M., Taheri S. (eds) Numerical Nonsmooth Optimization. Springer, Cham, Switzerland., P. 19 - 59 (год публикации - 2020)
10.1007/978-3-030-34910-3_2

10. Стонякин Ф.С. Адаптивный аналог метода Ю. Е. Нестерова для вариационных неравенств с сильно монотонным оператором Сибирский журнал вычислительной математики, 2019, том 22, номер 2, страницы 201–211 (год публикации - 2019)
10.15372/SJNM20190206

Публикации