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

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

 

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


Номер 18-71-00048

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

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

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

Срок выполнения при поддержке РНФ 07.2018 - 06.2020 

КонкурсКонкурс 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. Для случая большого числа ограничений будут предложены модификации адаптивных методов зеркального спуска для решения задач условной негладкой оптимизации, рассмотренные ранее в работах - 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 (принята в печать как глава Springer book). - 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. Будут доказаны оценки на скорость сходимости этих модифицированных методов, с помощью программ продемонстрирована экономию времени работы и применить эти методы к функционалам, возникающим а также в задачах Truss Topology Design, а также в задачах распределённой оптимизации. С использованием техники рестартов будут рассмотрены постановки данных задач для сильно выпуклых функционалов. 2. На базе аналога универсального проксимального зеркального метода для вариационных неравенств (недавно предложен А.В. Гасниковым, Ф.С. Стонякиным, П.Е. Двуреченским и А.А. Титовым), а также аналога метода Ю.Е. Нестерова для вариационных неравенств с сильно монотонным полем (недавно предложен руководителем проекта Ф.С. Стонякиным) будет предложен новый подход к задачам выпуклой оптимизации с линейными ограничениями вида равенств и выпуклыми ограничениями вида неравенств (с функционалами различного уровня гладкости). Назовём этот подход универсальным методом множителей Лагранжа. Он будет полезен при невозможности эффективного (в частности, явного) построения двойственной задачи. Будут получены оценки на скорость сходимости и обоснована оптимальность такого подхода с точки зрения нижних оракульных оценок. В качестве примера будут рассмотрены приложения методики к условным задачам на нахождение кратчайших сетей. 3. Будут предложены аналоги универсальных (адаптивных) методов градиентного спуска для задач оптимизации в бесконечномерных пространствах с использованием ранее рассмотренного Ф.С. Стонякиным условия компактной липшицевости, получены оценки на их скорость сходимости. На базе этих результатов будут развиты идеи работы 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 at https://arxiv.org/ftp/arxiv/papers/1703/1703.00267.pdf, посвящённой универсальному методу решения широкого класса обратных задач. Будет исследована возможность подбора выгодный в смысле общих затрат времени метод для решения обратных задач с приближённым вычислением градиента на базе адаптивного выбора как уровня гладкости градиента, так и сетки для приближения. Ожидается, что все намеченные результаты будут соответствовать мировому уровню исследований в области численных методов оптимизации. Они должны открыть перспективы их использования в широком классе условных задач оптимизации, возникающих в приложениях (транспортные задачи, задачи проектирования механических конструкций Truss Topology Design, обратные задачи).


 

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


Аннотация результатов, полученных в 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-минутные доклады руководителя проекта Стонякина Ф.С. на следующих научных семинарах: - Научный семинар "Задачи дифференциальных уравнений, анализа и управления: теория и приложения" под руководством член-корреспондента РАН М.И. Зеликина, член-корреспондента РАН В.Ю. Протасова, профессора В.М. Тихомирова и профессора А.В. Фурсикова. - Общемосковский постоянный научном семинаре «Теория автоматического управления и оптимизации». Институт проблем управления им. В. А. Трапезникова РАН под руководством профессора Б.Т. Поляка. - Научный семинар кафедры высшей математики МФТИ под руководством профессора Е.С. Половинкина

 

Публикации

1. - Проект КФУ по улучшению работы программ получил грант РНФ РИА Новости Крым, - (год публикации - ).

2. - Крымский ученый получил грант в 1,5 миллиона на исследования Комсомольская правда. Крым, - (год публикации - ).

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

4. Титов А.А., Стонякин Ф.С., Гасников А.В., Алкуса М.С. 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).


Аннотация результатов, полученных в 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 заочных доклада на научных конференциях по тематике проекта.

 

Публикации

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

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

3. П.Е. Двуреченский, А.В. Гасников, Е.А. Нурминский, Ф.С. Стонякин 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).

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

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

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).

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

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


Возможность практического использования результатов
не указано