Аннотация результатов, полученных в 2018 году
Согласно поданной заявке, работа по проекту в отчётный период была посвящена алгоритмическим методам градиентного типа решения задач выпуклого программирования, использующим информацию первого порядка (значения функций и (суб)градиенты). Интерес к методам первого порядка естественен ввиду отсутствия больших затрат памяти и независимости оценок скорости сходимости от размерности, что важно для возникающих в последнее время задач в пространствах больших размерностей. Если заранее не известно точное решение исследуемой задачи, то вполне разумно для оценки качества найденного в ходе итеративного процесса приближённого решения использовать теоретические оценки. В этой связи численный метод вполне разумно оценивать с точки зрения оптимальной оценки скорости сходимости. Для алгоритмических методов выпуклой оптимизации известен подход к описанию оптимальной скорости сходимости метода в терминах теории нижних оракульных оценок, восходящих к известной монографии А.С. Немировского и Д.Б. Юдина "Сложность задач и эффективность методов оптимизации". Исследования по проекту в отчётный период были посвящены некоторым новым алгоритмическим схемам для задач выпуклой оптимизации с функциональными ограничениями-неравенствами с адаптацией остановки. Были доказаны теоретические оценки и их оптимальность с точки зрения теории оракульных оценок на соответствующих классах задач, а также экспериментально описывалась возможность ускорения работы за счёт адаптации остановки. Основная часть вычислений произведена техническим специалистом и руководителем проекта с помощью языка CPython 3.7 на компьютере с 3-ядерным процессором AMD Athlon II X3 450 с тактовой частотой 803,5 МГц на каждое ядро. ОЗУ компьютера составляло 8 Гб. Были проведены тесты не менее, чем для 50 различных задач. Опишем несколько направлений, по которым выполнялись исследования в отчётный период. 1. Были рассмотрены адаптивные методы зеркального спуска для задач выпуклого программирования с несколькими негладкими функциональными ограничениями. Согласно теории нижних оценок, для класса негладких задач выпуклого программирования оптимальным будет всякий метод, позволяющий найти eps-точное решение задачи по функции за O(1\eps^2) итераций с обращениями к подпрограмме расчёта (суб)градиента. Если целевая функция и функциональные ограничения задачи не только выпуклы, но и сильно выпуклы, то оптимальной скоростью сходимости будет O(1\eps). Были предложены 2 новые алгоритмические схемы для негладких задач выпуклого программирования с различными стратегиями выбора шага (h_k = eps\||\nabla f(x_k)||^2 или h_k = eps\||nabla f(x_k)||) и соответствующими им адаптивными критериями остановки. Выполнения критериев остановки гарантирует достижение нужного качества решения без знания параметров задачи типа константы Липшица или константы Липшица градиента. Рассмотрены модификации предложенных методов для случая большого количества ограничений (позволяющие игнорировать некоторые из ограничений на непродуктивных шагах). Для первого из предложенных алгоритмов доказана оптимальность метода, в случае липшицевых целевого функционала и ограничений, а для второго метода оптимальную оценку скорости сходимости можно получать для целевых функционалов различного уровня гладкости (липшицев функционал или липшицев градиент). Более того, получены оценки скорости для случая гельдерова целевого функционала (пример задачи из A. Nedic, A. Ozdaglar. Convex Optimization in Signal Processing and Communications. Cambrige Univ. Press, 2009. Available at https://wsl.stanford.edu/ITMANET/ITMANET_Publications/nedic_book.pdf ). С помощью техники рестартов (перезапусков) предложенных алгоритмов получены оптимальные с точки зрения нижних оценок методы зеркального спуска для негладких сильно выпуклых функций. Экспериментально результаты работы предложенных методов сопоставлены с аналогичными методами, ранее предложенными в работе Bayandina, A., Dvurechensky, P., Gasnikov, A., Stonyakin, F., Titov, A. Mirror descent and convex optimization problems with non-smooth inequality constraints // Lecture Notes in Mathematics 2227. Large-Scale and Distributed Optimization, 2018, pp. 181-213. Найдены примеры (результаты имеются в прикреплённом к отчёту файле), для которых новые методы работают не менее, чем в 1000 раз быстрее! Рассмотрены примеры негладких задач размерности 200 и 1000, для которых эти методы работают значительно быстрее, в том числе для аналога задачи Ферма-Торричелли-Штейнера (Монжа) размерности 200 с негладкими ограничениями. Результаты экспериментов прикладываются к отчету в п. 1.3 файла со вспомогательной информацией. Также разработан специальный адаптивный метод метод зеркального спуска, применимый к популярным в приложениях так называемым задачам онлайн-оптимизации. Задача онлайн-оптимизации состоит в том, чтобы минимизировать среднее арифметическое N целевых функционалов при наличии выпуклого липшицева негладкого ограничения. При этом важной особенностью , что (суб)градиент каждого целевого функционала можно вычислять всего один раз. Онлайн-оптимизация играет значительную роль в решении задач с регулярно обновляемыми входными данными. Существует множество примеров таких задач в области интернета сетей, финансовых рынков, приложений машинного обучения. Особенно важным примером является задача о принятии решения. Предположим, имеется несколько экспертов и множество допустимых решений какой-либо проблемы, распределенное на единичном симплексе. Каждый эксперт даёт свою оценку потерь от принятия того или иного решения. Необходимо минимизировать суммарные потери (среднее арифметическое) с точки зрения мнения всех экспертов. Предложен алгоритм зеркального спуска (для задачи об экспертах важно, что можно использовать неевклидово расстояние на единичном симплексе), гарантирующий достижение заданной точности решения при оптимальном количестве шагов O(N). Обоснована возможность ускорения для случая многих ограничений. 2. Отметим, что упомянутые в предыдущем пункте методы оптимальны лишь на классе выпуклых негладких задач. Для задач с выпуклыми функционалами более высокого уровня гладкости существуют методы, которые работают с более высокой скоростью сходимости. Некоторое время назад Ю.Е. Нестеровым в предложены так называемые универсальные градиентные методы для задач выпуклой минимизации. Под универсальностью метода понимается возможность адаптивной настройкой метода на уровень гладкости задачи, что может позволить ускорять работу метода. В частности, для негладкой задачи ввиду такой адаптивной настройки может наблюдаться скорость сходимости, теоретически свойственная для гладких задач. Если необходимо решать задачу с функциональными ограничениями и нет возможности эффективно (например, явно) построить двойственную задачу (или трудно найти градиент двойственной функции), то разумно по принципу множителей Лагранжа переходить к седловой задаче и соответствующему вариационному неравенству (далее будем называть такие седловые задачи лагранжиевыми). Недавно Ф.С. Стонякиным совместно с А.В. Ганисковым, П.Е. Двуреченским и А.А. Титовым был предложен универсальный вариант проксимального метода А.С. Немировского для решения вариационных неравенств. В ходе работы обоснована возможность применения универсального метода к выпукло-вогнутых седловых задачам. Доказано, что можно гарантированного получить eps-точное решение за (достаточного для достижения необходимого качества решения времени) O((1/eps)^{2/(1+nu)}) итераций. Известно, что эта оценка оптимальна при nu = 0 и nu = 1. При nu>0 такая оценка будет лучше описанной ранее для негладких задач (см. п.1 выше). При этом экспериментально для некоторых примеров показано, что адаптивность критерия остановки метода на практике может приводить к ускорению работы метода по сравнению с теоретическими оценками. В частности, найден такой пример лагранжиевой седловой задачи размерности 110, связанной с задачей Ферма-Торричелли-Штейнера (Монжа) минимизации суммы расстояний (целевая функция негладкая и не сильно выпуклая) до фиксированного набора точек с негладкими ограничениями-неравенствами, для которой может наблюдаться скорость сходимости O(1/eps), оптимальная для гладких седловых задач. 3. Сверх заявленного плана работ были разработаны также некоторые методы градиентного типа с линейной скоростью сходимости O(ln(1/eps)), которая имеет место при специальных допущениях (липшицевость градиента целевого функционала и сильная выпуклость или малая размерность решаемой задачи). При этом была описана степень влияния погрешностей задания функции и (суб)градиента на итоговые оценки. Показано, что погрешности не накапливаются на итерациях метода. Это важно для выполнения плана гранта на второй год, который предусматривает исследование применимости адаптивных (универсальных) методов градиентного типа к бесконечномерным задачам. Для реализации таких схем необходима замена решаемой бесконечномерной задачи конечномерным аналогом, что неизбежно приводит к погрешностям. Сданы в печать 5 научных статей в издания, индексируемые в Scopus или Web of Science (в том числе и Lecture Notes in Computer Science) с указанием на поддержку гранта, из которых 1 опубликована и 1 принята в печать. Поданы 2 заявки с докладами на X International Conference "Optimization and Applications" (OPTIMA-2019) с перспективой подачи статей, в которые будут включены последние результаты по проекту. Сделано 10 научных докладов по материалам исследований по гранту, среди которых отметим: - 30-минутный устный доклад на 23 Международном симпозиуме по математическому программированию (Бордо, Франция, 1 - 6 июля 2018 г.). - Устный доклад на IX Международной конференции "Optimization and Applications" (Petrovac, Черногория, 1 - 5 октября 2018 г.) с последующей публикацией в сборнике "Communications in Computer and Information Sciences", 90-минутные доклады руководителя проекта Стонякина Ф.С. на следующих научных семинарах: - Научный семинар "Задачи дифференциальных уравнений, анализа и управления: теория и приложения" под руководством член-корреспондента РАН М.И. Зеликина, член-корреспондента РАН В.Ю. Протасова, профессора В.М. Тихомирова и профессора А.В. Фурсикова. - Общемосковский постоянный научном семинаре «Теория автоматического управления и оптимизации». Институт проблем управления им. В. А. Трапезникова РАН под руководством профессора Б.Т. Поляка. - Научный семинар кафедры высшей математики МФТИ под руководством профессора Е.С. Половинкина

Аннотация результатов, полученных в 2019 году
1. Полностью завершено теоретическое обоснование применимости разработанных в первый год выполнения проекта адаптивных и универсальных численных методов к выпукло-вогнутым седловым задачам и задачам выпуклого программирования с целевыми функционалами и ограничениями промежуточной гладкости (гёльдеров градиент целевого функционала и функционалов ограничений). Дополнительно проведённые численные эксперименты показали реализуемость таких схем за приемлемое время со скоростью сходимости лучше О(1/eps^2), т.е. выше по сравнению с оптимальными теоретическими оценками. Прежде всего, речь идёт о задачах типа Ферма-Торричелли-Штейнера с соответствующими ограничениями. Также проведены вычислительные эксперименты для проводиться на задачах наилучшего приближения или минимизации суммы расстояний до нескольких точек с выпуклыми ограничениями-неравенствами промежуточной гладкости (гёльдеров градиент или ограниченный субградиент). Подготовлена статья по теме в журнал "Journal Optimization Theory and Applications" https://arxiv.org/pdf/1806.05140.pdf. Кратко полученные оценки для седловых задач изложены в опубликованной главе монографии "Adwances in Low-memory Subgradient Optimization" (прилагается к отчёту). 2. Обоснована оптимальность (с точностью до умножения на константу) оценок сложности для разработанных адаптивных алгоритмических методов зеркального спуска к задачам выпуклого программирования с гёльдеровыми целевыми функционалами и липшицевыми функционалами ограничений. Результат об оптимальности зеркальных (в случае евклидова расстояния - субградиентного метода) для гёльдеровых целевых функционалов получен впервые в рамках работ по проекту. Найдено приложение к задаче оптимального распределения ресурсов (задача максимизации пропускной способности компьютерной сети) с нелипшицевыми функционалами полезности. Экспериментально исследована степень эффективности предложенных методов к задаче проектирования механических конструкций (Truss Topology Design). Полученные результаты расчётов показывают, что предложенный нами метод гарантирует достижение аналогичного качества решения примерно раз в 10 быстрее по сравнению с аналогичными подходами из работ Ю.Е. Нестерова, С.В. Шпирко (2014) и S. Lagae(2017). По этой теме вышла статья в журнале "Компьютерные исследования и моделирование" (номер 2 за 2020 год), принята статья (именно по приложениям к задаче оптимизации компьютерной сети на международный конгресс IFAC 2020 года). 3. Введено новое понятие неточной оптимизационной модели выпуклого целевого функционала, которое в частности позволяет разграничить наличие погрешностей при задании целевой функции, а также градиента (субградиента в случае негладкого функционала). Такое разграничение позволяет, среди прочего, уточнять оценки скорости методов, уточняя влияние погрешностей задания градиента (она может в некоторых случаях не накапливаться). Для введённого варианта понятия неточной модели целевой функции предложен градиентный метод с адаптивной настройкой всех параметров (как с настройкой на параметр гладкости, так и на соответствующие погрешностям величины) неточной модели целевого функционала. Доказана теорема об оценке скорости сходимости разработанного градиентного метода. Полученная оценка скорости сходимости может считаться оптимальной на классе достаточно гладких задач при наличии погрешностей, поскольку можно обосновать то, что соответствующие им величины не накапливаются. Для неускоренного метода результат опубликован в http://journal.imm.uran.ru/2019-v.25-4-pp.210-225. 4. Разработан адаптивный градиентный метод для целевых функций с некоторой релаксацией условия липшицевости градиента, удовлетворяющих условию градиентного доминирования Поляка-Лоясиевича. При этом учитывается возможность неточного задания целевой функции и градиента. Адаптивный выбор параметров при работе метода выполняется как по величине константы Липшица градиента, так и по величине, соответствующей погрешности задания градиента и целевой функции. Обоснована линейная сходимость метода с точностью до величины, связанной с погрешностями. Получены оценки скорости сходимости методов градиентного типа с учетом величин, соответствующих погрешностям. При этом полностью реализована адаптивная настройку шага (не величину параметра локальной константы гладкости $L_k$), а также частичная настройка на параметры, соответствующие погрешностям задания целевого функционала и градиенте. Доказано, что адаптивная настройка на увеличивает в среднем стоимость итерации метода, однако экспериментально может приводить к существенному повышению качества решения, что продемонстрировано экспериментами. Важная особенность от отличие от градиентных методов для стандартного варианта $(\delta, L, \mu)$-оракула – возможность оценивать качество найденного решения только по значению целевого функционала в начальной точке $F(x^0) – F* \leq F(x^0)$, без использования оценки расстояния от $x^0$ до точного решения. Проведены некоторые численные эксперименты для задачи решения матричного уравнения с погрешностями задания целевой функции и градиента, которые продемонстрировали неплохую эффективность оценки для адаптивного метода. Проведены также эксперименты и для негладкой задачи минимизации максимума расстояния до фиксированных точек, которые показали неплохую эффективность метода. Результат опубликован в http://journal.imm.uran.ru/2019-v.25-4-pp.210-225. На базе разработанных методов градиентного типа с использованием разработанных концепций неточности задания целевой функции и (субградиента) разработаны оптимальные с точки зрения нижних оракульных оценок универсальные методы для безусловных бесконечномерных задач оптимизации. Адаптивность упомянутых в предыдущих двух пунктах методов на параметры неточностей задания функционала и градиента (погрешности аппроксимации бесконечномерной задачи её конечномерным аналогом) в частности означает для обратных (и вообще бесконечномерных) задач возможность адаптивного выбора оптимального шага дискретизации сетки аппроксимации для обратной задачи. 5. Введена концепция неточной оптимизационной модели для задания оператора поля вариационного неравенства. Для соответствующих классов вариационных неравенств предложен адаптивный аналог проксимального зеркального метода А.С. Немировского. При этом реализована как с адаптивной настройкой как на уровень гладкости оператора, так и величину погрешности задания оператора вариационного неравенства. Введение искусственной неточности и специальный выбор критерия выхода из итерации может приводить, в частности, к варианту универсального метода для бесконечномерных вариационных неравенств с монотонными операторами и выпукло-вогнутых седловых задач. По этому направлению вышла работа в "Communication in Computer and Information Sciences" (Conference Proceedings OPTIMA - 2019) . За отчётный год (2019 - 2020 гг.) опубликовано 3 научные статьи в журналах, индексируемых в Scopus/WOS (Журнал вычислительной математики и математической физики, Труды ИММ УрО РАН, Компьютерные исследования и моделирование), 2 работы в сборниках трудов международных конференций (MOTOR-2019, OPTIMA-2019), опубликованные в индексируемых в Scopus изданиях Lecture Notes in Computer Science и Communications in Computer and Information Science. Принята в печать работа в сборник IFAC Papers Online в рамках Международного конгресса по автоматическому управлению IFAC-2020. Опубликована (совместно с А.В. Гасниковым, Е.А. Нурминским и П.Е. Двуреченским) глава "Advances in Low-memory Subgradient Optimization" монографии "Numerical Nonsmooth Optimization: State of the Art Algorithms" в издательстве Springer. Подготовлена к изданию монография Стонякина Ф.С. "Адаптивные алгоритмические методы в негладкой оптимизации", в которую будут включены все полученные в рамках проекта результаты, получена рекомендация Учёного Совета Таврической академии Крымского федерального университета имени В.И. Вернадского к её опубликованию. Сделано 6 очных и 2 заочных доклада на научных конференциях по тематике проекта.