Mirror descent for constrained optimization problems with large subgradient values of functional constraints
Fedor Sergeevich Stonyakin, Aleksej N Stepanov, Alexander Vladimirovich Gasnikov, Alexander A Titov · Computer Research and Modeling · 2020
В работе рассмотрена задача минимизации выпуклого и, вообще говоря, негладкого функционала f при наличии липшицевого неположительного выпуклого негладкого функционального ограничения g.При этом обоснованы оценки скорости сходимости методов адаптивного зеркального спуска также и для случая квазивыпуклого целевого функционала в случае выпуклого функционального ограничения.Предложен также метод и для задачи минимизации квазивыпуклого целевого функционала с квазивыпуклым неположительным функционалом ограничения.В работе предложен специальный подход к выбору шагов и количества итераций в алгоритме зеркального спуска для рассматриваемого класса задач.В случае когда значения норм (суб)градиентов функциональных ограничений достаточно велики, предложенный подход к выбору шагов и остановке метода может ускорить работу метода по сравнению с его аналогами.В работе приведены численные эксперименты, демонстрирующие преимущества использования таких методов.Также показано, что методы применимы к целевым функционалам различных уровней гладкости.В частности, рассмотрен класс гёльдеровых целевых функционалов.На базе техники рестартов для рассмотренного варианта метода зеркального спуска был предложен оптимальный метод решения задач оптимизации с сильно выпуклыми целевыми функционалами.Получены оценки скорости сходимости рассмотренных алгоритмов для выделенных классов оптимизационных задач.Доказанные оценки демонстрируют оптимальность рассматриваемых методов с точки зрения теории нижних оракульных оценок.Ключевые слова: негладкая условная оптимизация, квазивыпуклый функционал, адаптивный зеркальный спуск, уровень гладкости, гёльдеров целевой функционал, оптимальный метод Исследования Ф. С. Стонякина по разработке алгоритмов 2 и 4, замечаний 2 и 3, обоснованию теорем 2 и 5 выполнены при поддержке Российского научного фонда (проект 18-71-00048).Исследования Ф. С. Стонякина и А. Н. Степанова по вычислительным экспериментам (примеры 1 и 2) выполнены при поддержке Российского научного фонда (проект 18-71-00048).Исследования по разработке алгоритма 3, обоснованию теорем 3 и 4, а также по вычислительным экспериментам (примеры 3 и 4) выполнены при поддержке Российского фонда фундаментальных исследований (проект 18-31-00219 мол-а).Исследования Ф. С. Стонякина по разработке замечания 4 выполнены при поддержке гранта Президента Российской Федерации для государственной поддержки молодых российских ученых-кандидатов наук (проект МК-15.2020.1).Исследование А. В. Гасникова по разработке алгоритма 3 и обоснованию леммы 3 выполнено при поддержке Министерства науки и высшего образования Российской Федерации (Госзадание МФТИ, проект 075-00337-20-03).