Адаптивные субградиентные методы для минимизации функций с условием Липшица и его аналогами тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Аблаев Сейдамет Серверович

• Аблаев Сейдамет Серверович
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Аблаев Сейдамет Серверович

Введение

Глава 1. Субградиентные методы для некоторых классов

негладких задач без ограничений

1.1 Понятие А-острого минимума

1.2 Оценка качества выдаваемого субградиентным методом

решения на классе слабо в-квазивыпуклых функций

1.2.1 Классический острый минимум

1.2.2 Обобщение результата о сходимости субградиентного

А

минимумом

1.3 Субградиентный метод с шагом Поляка на классе квазивыпуклых функций

1.4 Субградиентные методы на классе ц-слабо выпуклых функций

1.5 Субградиентные методы на классе относительно ц-слабо выпуклых функций

Глава 2. Методы субградиентного типа для задач

минимизации с функциональными ограничениями

2.1 Адаптивные субградиентные методы для задач математического программирования

2.1.1 Случай выпуклой целевой функции и квазивыпуклых ограничений

2.1.2 Случай квазивыпуклой целевой функции и выпуклых ограничений

2.1.3 Случай квазивыпуклой целевой функции и квазивыпуклых ограничений

2.2 Методы зеркального спуска для задачи композитной оптимизации с ограничениями

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

2.2.2 Зеркальный спуск с использованием 6-субградиентов для относительно липшицевых композитных задач

Стр.

2.3 Рестарты субградиентных методов для задач нелинейного программирования с аналогом острого минимума

2.4 Субградиентный метод с переключениями для ц-слабо выпуклых задач нелинейного программирования с аналогом острого минимума

Глава 3. Минимизация выпуклой положительно однородной

функции с относительной точностью

Глава 4. Адаптивные методы для вариационных неравенств с относительно гладкими и относительно сильно монотонными операторами

4.1 Адаптивный метод для вариационных неравенств с относительно гладким сильно монотонным оператором

4.2 Универсальные методы для задачи с 6-обобгцённым условием

гладкости оператора вариационного неравенства

4.2.1 Вычислительные эксперименты

Заключение

Благодарности

Список рисунков

Список таблиц

Список литературы

Введение диссертации (часть автореферата) на тему «Адаптивные субградиентные методы для минимизации функций с условием Липшица и его аналогами»

Введение

Актуальность темы. Методы оптимизации — одна из наиболее актуальных и активно развивающихся областей современной вычислительной математики. В первую очередь, в силу широкого применения в различных областях науки и индустриальных проектах. Одним из основных численных методов современной оптимизации считается градиентный метод [1]. Спектр всевозможных приложений его очень разнообразен: от эпидемиологии [2] до анализа данных и машинного обучения [3; 4]. Процедура градиентного спуска возникла ещё в работах Коши, но затем повышенный интерес к ней вернулся лишь в середине XX века. Обычно анализ методов градиентного типа сводится к асимптотической оценке скорости сходимости, или же к оценке объёма вычислений, достаточного для получения приближённого решения с заданной точностью [5].

Известно, что оценки скорости сходимости методов градиентного типа лучше для выпуклых гладких задач по сравнению с негладкими и тем более невыпуклыми задачами. Стоит отметить, что на практике часто необходимо минимизировать негладкие, а также невыпуклые функции [4; 6—8].

Ясно, что задача минимизации произвольной негладкой функции без каких-либо дополнительных предположений может оказаться довольно трудоёмкой [5]. Поэтому в диссертации сделан акцент на важном классе задач негладкой минимизации — задачах с условием Липшица или его аналогами. Говорят, что функция /(х) : Q ^ К ^ С удовлетворяет условию Липшица па множестве если Ух,у € Q справедливо неравенство

|/(х) - /Ы| ^ М||Ж - у\\2,

где символ || • ||2 обозначает евклидову норму.

Известно, что для минимизации негладких целевых функций вместо градиентного метода можно использовать субградиентный метод, впервые предложенный Н. 3. Шором [9]. Идея метода заключается в замене градиента на произвольный субградиент функции. Напомним, что векторУ/(х) называется субградиентом выпуклой функции /(х) : ^ К в точке у € если Ух € Q выполняется неравенство /(х) ^ /(у) + (V/(х),х — у). Итерационный процесс

субградиентного метода имеет вид

xk+í = PrQ[xk — hkVf(хк)},

где hk > 0 Vf (хк) Е df (хк) — произвольный субградиент (df (х) —

субдифференциал, т.е. множество всех субградиентов функции f (х) в точке

ж), a PfQ(y) := argmin{||y — ж||2} — оператор проектирования на множество

xeQ

Q. Как известно [5], вектор —Vf(хк) не обязательно задаёт направление наискорейшего убывания функции. Поэтому нельзя гарантировать, что значения функции в субградиентном методе монотонно убывают с ростом количества итераций. Однако можно доказать, что монотонно убывают расстояния от текущей точки до точки минимума [5]. При этом оценка скорости сходимости субградиентного метода Шора сублинейная [10].

Однако при дополнительном предположении о том, что выпуклая функция удовлетворяет условию острого минимума, можно доказать линейную скорость сходимости субградиентного метода в пространствах больших размерностей [11]. Условие острого минимума предложил Б. Т. Поляк. Говорят, что функция f (х) : Q ^ R удовлетворяет условию острого минимума на множестве Q, тел и Ух Е Q справедливо неравенство

f (х) — f* ^ a min Цх — х*Ц2,

где a > 0 - фиксированное число, а X* - множество точек минимума. При этом линейная скорость сходимости возможна только при определенной стратегии выбора шага. Также отметим, что в работах Б.Т. Поляка и других авторов (см., например, [11; 12]) в понятии острого минимума используется инфимум (inf Ix — ж*||2), а не минимум (min ||ж — ж*||2)- Это связано с тем, что он рассматривал задачи оптимизации в гильбертовых пространствах. В конечномерных пространствах, для функций, принимающих конечные значения, эти понятия равносильны.

Выбор шага является особенностью субградиентных методов. Если выбирать шаг постоянным, то метод может не сходиться. Нужно выбирать либо сходящуюся к 0 последовательность, либо использовать какие-то процедуры регулировки шага. Например, Б. Т. Поляк предложил использовать разность между значением функции в текущей точке и минимальным значением [11]. Это возможно, если известно минимальное значение функции. Отметим, что

минимальное значение f * = f (х* ) = min f (x) известно во многих прикладных

xeQ

задачах, но при этом не известно, для какого аргумента достигается это значение. Используя f * можно построить адаптивный шаг, который не содержит таких параметров задачи, как константа Липшица или расстояние от точки старта до точки минимума:

, = f te ) - f ' = IVte )II2 •

Такой шаг принято называть шагом Поляка. Отметим, что различные вариации шага Поляка изучаются и по сей день [13—15].

Если f (ж) - выпуклая липшицева функция, то для субградиентного метода можно гарантировать оценку скорости сходимости О ^[5]. Если дополнительно предположить, что f (х) удовлетворяет условию острого минимума, то известно, что субградиентный метод с шагом Поляка сходится со скоростью геометрической прогрессии [5; 11].

В данной диссертационной работе расширен класс липшицевых задач с острым минимумом, для которых можно гарантировать аналог результата о сходимости субградиентного метода со скоростью геометрической прогрессии. Для некоторых типов невыпуклых задач, включая квазивыпуклые, слабо в-квазивыпуклые (их ещё называют квазар-выпуклыми) [16; 17], предложены различные варианты шага Поляка для субградиентного метода. Для относительно липшицевых [18; 19], в том числе ц-слабо выпуклых задач, тоже предложены некоторые аналоги шага Поляка. Для задач с нелинейными ограничениями-неравенствами предложен подход, использующий технику рестартов и аналог условия острого минимума (в некоторых источниках его называют geometry bound condition) [3]. Также получен результат о вычислительных гарантиях субградиентного метода в случае неточной информации о функции или субградиенте. Предложено обобщенное условие острого минимума для случая, когда оптимальное значение f ' известно лишь приближенно, что позволяет применять предложенные подходы к задачам с разными типами условия роста или к задачам, где f ' неизвестно.

Выделим такие основные направления диссертационного исследования.

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

функционалы бывают невыпуклыми. Тем не менее часто бывает так, что они удовлетворяют некоторому аналогу свойства выпуклости [6; 7; 16]. Наиболее известные примеры таких условий это квазивыпуклость, слабая выпуклость, а также, например, недавно введённое в работе [16] условие слабой в"квазивыпУклости- В случае задач без ограничений исследуется субградиентный метод с шагом Поляка для минимизации негладких липшицевых функций, при описанных предположениях о выпуклости. Стоит отметить, что с точки зрения приложений наиболее интересен класс ц-слабо выпуклых функций, поскольку многие прикладные задачи слабо выпуклы (например, задача восстановления фазы [7]). Для задач с функциональными ограничениями рассматривается класс задач с соответствующей вариацией острого минимума. Условие острого минимума для задач линейного программирования хорошо известно [5], а для нелинейных задач появилось недавно [3]. Исследуются вычислительные гарантии применения техники рестартов субградиентного метода для задач с острым минимумом.

Второе направление связано с идеологией универсальных градиентных методов, предложенных Ю.Е. Нестеровым [20]. Универсальный градиентный метод сам в ходе работы настраивается на гладкость задачи и при этом не требует никакой информации о гладкости на вход [1]. Отметим, что отличие универсального метода от адаптивного в том, что настройка идёт не только на константу гладкости, но и на уровень гладкости функции [1]. Такая настройка не позволяет улучшить оценки в худшей ситуации, но за счёт использования адаптивно подбираемых параметров на итерациях метода может наблюдаться повышение скорости сходимости для конкретных примеров.

В таком контексте рассматриваются два типа задач. Первый — оптимизация с относительной точностью, а второй — решение вариационных неравенств. Задача оптимизации с относительной точностью мотивирована главой 6 докторской диссертации Ю.Е. Нестерова. Он показал, что такой подход можно использовать при решении задач оптимизации на неограниченных допустимых множествах. Также относительная точность позволяет оценивать качество приближенного решения некоторых прикладных задач (например, проектирование механических конструкций [21]). При этом, как показано в [21], разумно рассматривать класс выпуклых положительно однородных функций. Для такого класса задач нами предложен аналог универсального

метода подобных треугольников с критерием остановки, предназначенным для задач с относительной точностью.

Альтернативным подходом к задачам негладкой оптимизации может служить обобщение условия гладкости и анализ метода в случае такого обобщения. Например, в теории вариационных неравенств используется условие Ь-гладкости оператора, которое обобщает свойство липшицевости градиента функции для обычных задач минимизации. Известно, что обобщением задачи оптимизации является задача поиска решения вариационного неравенства: задачи оптимизации с ограничениями сводятся к седловым, а седловые задачи, в свою очередь, к вариационным неравенствам. В работе исследуются адаптивные методы для вариационных неравенств с относительно гладкими и относительно сильно монотонными операторами. Свойства относительной гладкости и относительной сильной монотонности для вариационных неравенств были введены довольно недавно, в [22] и [23] соответственно, как аналоги свойств липшицевости градиента и относительной сильной выпуклости для минимизационных задач [24; 25].

Диссертационная работа выполнена в федеральном государственном автономном образовательном учреждении высшего образования «Крымский федеральный университет им. В.И. Вернадского» и в федеральном государственном автономном образовательном учреждении высшего образования «Московский физико-технический институт (национальный исследовательский университет)».

Цель работы — расширение класса липшицевых задач с острым минимумом, для которых можно гарантировать аналог результата о сходимости субградиентного метода со скоростью геометрической прогрессии, исследование задачи минимизации выпуклой положительно однородной функции с помощью универсального аналога метода подобных треугольников и, наконец, разработка и анализ адаптивных методов решения вариационных неравенств с относительно гладким сильно монотонным оператором.

Для достижения цели были поставлены следующие задачи диссертации: 1. Исследовать методы субградиентного типа с шагом Поляка и его аналогами на классе негладких задач, для которых справедливо условие острого минимума, которое потенциально приводит к линейной скорости сходимости метода. Получить оценки скорости

сходимости субградиентного метода с шагом Поляка и его вариациями для задач невыпуклой (квазивыпуклой, ц-слабо выпуклой, слабо |3-квазивыпуклой, относительно ц-слабо выпуклой) оптимизации. Исследовать влияние неточной информации о минимальном значении функции на оценку качества выдаваемого методом решения. Получить оценки качества выдаваемого решения в случае доступности неточной информации о субградиенте целевой функции.

2. Разработать рестартованные версии субградиентных схем с переключениями для выпуклых и квазивыпуклых негладких задач с обобщенным условием острого минимума. Получить оценки скорости сходимости. Исследовать адаптивный алгоритм зеркального спуска для задачи композитной оптимизации с ограничениями.

3. Исследовать аналог метода подобных треугольников для задачи минимизации выпуклой положительно однородной функции с относительной точностью. Получить оценку количества итераций алгоритма, которая гарантирует достижение требуемой относительной точности.

4. Исследовать адаптивные варианты проксимального зеркального метода для вариационных неравенств с относительно гладким сильно монотонным оператором в случае произвольной проке-функции. Предложить аналог проксимального метода па случай 6-обобщеппо гладкого оператора вариационного неравенства.

Научная новизна работы.

1. Впервые получены оценки скорости сходимости субградиентного метода с аналогом шага Поляка для квазивыпуклых, слабо |3-квазивыпуклых и относительно ц-слабо выпуклых задач с острым минимумом.

2. Впервые получена оценка скорости сходимости субградиентного метода с аналогом шага Поляка для задач с неточным аналогом острого минимума в предположении доступности методу в каждой текущей точке неточного 6-субграднента.

3. Впервые предложена техника рестартов субградиентных схем с переключениями для выпуклых (квазивыпуклых) задач с выпуклыми (квазивыпуклыми) ограничениями при условии острого минимума.

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

5. Впервые предложен адаптивный вариант проксимального зеркального метода для вариационных неравенств с относительно сильно монотонными и обобщённо относительно гладкими операторами в случае произвольной проке-функции.

Положения, выносимые на защиту.

1. Получена оценка скорости сходимости субградиентного метода с аналогом шага Поляка на классе слабо |вквазивыпУклых задач с острым минимумом. Получена оценка скорости сходимости субградиентного метода с аналогом шага Поляка на классе квазивыпуклых задач с аналогом острого минимума, при условии доступности методу неточной информации о минимальном значении функции.

2. Получена оценка скорости сходимости субградиентного метода с аналогом шага Поляка на классе относительно ц-слабо выпуклых задач с относительным острым минимумом. Исследовано влияние неточной информации о функции или субградиенте на качество выдаваемого методом решения.

3. Разработаны рестартованные версии субградиентных схем с переключениями для выпуклых (квазивыпуклых) задач с выпуклыми (квазивыпуклыми) ограничениями при условии острого минимума. Доказана линейная скорость сходимости таких методов.

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

5. Получена оценка скорости сходимости адаптивного проксимального зеркального метода для вариационных неравенств с относительно гладким сильно монотонным оператором в случае произвольной проке-функции. Исследован случай 6-обобщенной гладкости.

и

Апробация работы. Основные результаты работы докладывались на следующих конференциях:

1. Международная конференция «Equation of convolution type in science and technology (ECTST)», 2019, Ялта, Россия.

2. Международная конференция «Mathematical optimization theory and operations research (MOTOR)», 2020, Новосибирск, Россия.

3. Международная конференция «Optimization without Borders», 2021, Сочи, Россия.

4. VII, VIII и IX международные конференции «Quasilinear Equations, Inverse Problems and Their Applications (QIPA)», 2021, 2022, 2023, Россия.

5. 64-ая и 65-ая конференции МФТИ, 2021, 2023, Долгопрудный, Россия.

Достоверность научных достижений и публикации. Все основные результаты являются математически строго обоснованными и опубликованы в рецензируемых изданиях, индексируемых в базах Scopus и RSCI. Всего автором опубликовано 8 работ по теме диссертации, из них 6 в изданиях, индексируемых в базе Scopus и 2 статьи в журналах, которые индексируются в RSCI.

Личный вклад. Все приведенные в диссертации результаты из совместных публикаций получены автором лично.

Структура и объем диссертации. Диссертация состоит из введения, 4 глав и заключения.

В первой главе исследуется субградиентный метод с различными аналогами шага Поляка для невыпуклых функций. Получены оценки скорости сходимости метода на классе квазивыпуклых, ц-слабо выпуклых и слабо |3-квазивыпуклых функций. Изучен вопрос о влиянии неточной информации о минимальном значении функции на работу метода. Предложен вариант субградиентного метода с аналогом шага Поляка в случае использования вместо субградиентов значений функции в текущей точке 6-субградиентов.

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

ограничениями, доказана линейная скорость сходимости рестартованной версии субградиентного метода. Также исследована задача композитной оптимизации с ограничениями.

Третья глава посвящена задаче минимизации с относительной точностью, которая исследовалась в работах Ю.Е. Нестерова [21; 26; 27]. На базе адаптивного варианта метода подобных треугольников получен аналог универсального градиентного метода для задач с относительной точностью. Доказана оптимальная оценка его скорости сходимости на классе выпуклых положительно однородных функций.

В четвёртой главе исследуется сходимость адаптивного проксимального метода для вариационных неравенств с относительно гладким сильно монотонным оператором и изучается случай еще более общего предположения

0 гладкости.

Полный объём диссертации составляет 100 страниц, включая 3 рисунка и

1 таблицу. Список литературы содержит 68 наименований.

Глава 1. Субградиентные методы для некоторых классов негладких

задач без ограничений

Первая глава диссертации посвящена исследованию субградиентных методов с шагом Поляка для задач негладкой оптимизации. В пункте 1.1 приводится понятие А-острого минимума и приводятся примеры задач, для которых верно это условие. В пункте 1.2 изучается субградиентный метод на классе слабо |вквазивыпУклых функций в случае как обычного

А

субградиентный метод на классе квазивыпуклых функций с острым минимумом или его аналогом. Также рассматривается вопрос о возможности отказа от операции проектирования на допустимое множество и оценивается степень удаления траектории метода от начальной точки. Анализируется работа субградиентного метода на классе квазивыпуклых функций в случае доступности 6-субградиентов вместо обычных. В пункте 1.4 рассматривается субградиентный метод с шагом Поляка на классе ц-слабо выпуклых функций, а в пункте 1.5 — на классе относительно ц-слабо выпуклых функций.

Итак, рассмотрим задачу минимизации функции /(х) : Q ^ К вида

I М ^ тт, (1.1)

где Q € — выпуклое замкнутое множество. Точку минимума будем обозначать через ж*, а минимальное значение функции через /*. Множество всех точек минимума обозначим как А*, т.е. X* = { х* € Q; /(х*) = /* }. Будем считать, что X* — замкнутое выпуклое множество. Пусть Ргд(у) := а^шт{||у — ж||2} — оператор проектирования на множество

Всюду в тексте символ || • ||2 обозначает евклидову норму.

В работе часто используются понятия субградиента и субдифференциала. Для выпуклых функций эти термины понимаются в смысле выпуклого анализа. Для невыпуклых локально липшицевых функций в качестве субдифференциала можно использовать субдифференциал Кларка.

Субдифференциал Кларка [28]. Пусть ^ ^ множество в

/(х) : Q ^ К — локально липшицева на ф функция, д €

Рассмотрим

fd(х'; 9) = lim sup1 [f (x' + кд) - f (ж')], (1.2)

[a,x' J—[+0,x] а

&(x; g) = lim inf i [f (x' + ад) - f (¿)]. (1.3)

[a,x ]—>-[+U,xJ ia

Величина fh (x; g) называется верхней производной Кларка функции f по направлению д, а величина (х; д) называется нижней производной Кларка функции / по направлению д [29]. Отметим, что пределы в (1.2) и (1.3) существуют всегда.

Ф. Кларк предложил определить субдифференциал f в точке х следующим образом

da f (х) = е Rn : (x,g) > (v,g) V g e Rn}. (1.4)

При этом,

fh(x; 9)= max (v,g), (1.5)

vedcif (x)

где dcif (x) — субдифференциал Кларка функции f (•) в точке х.

Отметим связь субдифференциала Кларка с субдифференциалом Шора. По теореме Радемахера функция, удовлетворяющая условию Липшица, дифференцируема на своей области определения почти всюду [30]. Пусть Т( f) — множество точек дифференцируемое™ функции f (х). Множество

dshf (х) = {v е R | 3{хк} : хк е Т(f), хк — х, Vf(хк) — v} (1.6)

было введено Н. 3. Шором [31] и называется субдифференциалом Шора функции f в точке х. Выпуклая оболочка этого множества совпадает с субдифференциалом Кларка:

даf (х) = conv {v е Rn | 3{хк} : xk e T(f), xk — x, Vf (xk) — v} , (1.7)

где conv{•} обозначает выпуклую оболочку множества.

Если не оговорено иного, то всюду далее в работе под субдифференциалом невыпуклой функции f (х) понимается субдифференциал Кларка, а под субградиентом — произвольный элемент субдифференциала Кларка.

1.1 Понятие A-острого минимума

Условие острого минимума было впервые предложено Б. Т. Поляком в работе [11]. Его можно сформулировать следующим образом: говорят, что ж* — точка острого минимума f (х) [5; 11], если

f (х) — f (х*) ^ a min \\х — х*\\2 Ух £ Q, (1.8)

для некоторого a > 0. Это условие не может быть выполнено для гладких функций [5]. Используя условие (1.8) и зная оценку разности между f (х) и f*, можно оценить расстояние \\х — х*\\2. Также известно, что условие острого минимума (1.8) позволяет получить линейную скорость сходимости субградиентного метода для негладких задач в пространствах больших размерностей [11]. Однако требование доступности f * сильно сужает класс задач, к которым можно применить метод. Поэтому мы рассматриваем следующее обобщение условия (1.8), предложенное в статье [32]:

f (х) — f ^ a min \\х — х*\\2 — A, (1.9)

ж* £-Х ф

где параметры a > 0 и A > 0 фиксированы и задано число f (его можно интерпретировать как приближение минимума).

Заметим, что условие (1.9) можно рассматривать и как обобщение острого минимума, аналогичное концепции неточного оракула Деволдера, Нестерова и Глинёра [33].

Пример 1.1.1. В качестве примера задачи, для которой верно обобщенное условие острого минимума, рассмотрим условие слабого острого минимума вида

f(х) — f* ^ ц min \\ж — х*\\2, Ух £ Q (1.10)

ж* £-Х ф

при, некотором р £ (1; то).

В частности, при, р = 2 неравенство (1.10) верно для всякой 2 ц-сильно выпуклой функции. Также отметим, что х* — единственная точка минимума, поскольку функция f сильно выпукла. Если \\х — х*\\2 ^ t, то

f (х) — /* ^ Ц£Р—1 \\ж — Ж*\\2.

В противном случае (т.е. при \\х — х*\\2 < е) имеем,

у\\х — х*\\р > у\\х — х*\\2 — уе,

откуда

f(х) — f* > уер—1 \\х — х*\\2 — уе, т.е. выполнено условие обобщённого острого минимума (1.9) при

а = уер—\ А = уе, J = f*.

Более того, можно рассмотреть ситуацию неточной информации об f * для удовлетворяющей (1.10) функции, f, т.е. когда известно лишь f такое, что f — f * ^ А .В этом случае условие обобщённого острого минимума (1.9) будет верно при,

а = уер—1 и А = уе + А.

Пример 1.1.2. Пусть

f (х) = \\ж\\2 + У\\Х — С\\\

для некоторого фиксированного вектора с, имеющего малую норм,у. Тогда, 0 < f * ^ f (0) = у\с\2- Ясно тогда, что при \\х\\2 > у\\с\\2 х заведомо не совпадёт с х*, т.е. х* лежит в шаре с центром в 0 радиуса у\\с\\2- В этом случае

f(х) ^ \\х — Х*\\2 — ||ж*\\2 + у\\х — с\\2,

и тогда

f(х) — f* ^ \\Х — Х*\\2 — \\Х*\\2 + j\\x — С\2 — У\\С\\2,

т.е.

f (х) — f* ^ f (х) — y\\c\\2 ^ \\х — Х*\\2 — \\ж*\2 — У\м\2 ^ \\х — Х*\\2 — 2у\\с\\2, и можно применять метод для таких значений параметров f = у\\с\\2, а = 1

и А = 2у\с\2-

Отметим, что значение f* бывает известно в геометрических задачах (проекция точки на множество или нахождение общей точки системы множеств). Также можно упомянуть задачу f (х) = \\Ах — Ь\\2 ^ min, где А _ матрица п х щ b Е Rn. Она разрешима, если существует х0 такой, что Ах0 = b [32].

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

Пусть имеется некоторое число в € (0; 1], х* — точка минимума задачи (1.1). Функция / называется слабо в_квазивь1ПУкл°й относительно х* на множестве если для произвольного х € Q выполнено неравенство [16]:

где V/(х) — произвольный субградиент / в точке х.

Ясно, что если неравенство (1.11) верно для некоторого в = во € (0; 1], то оно верно и при в € (0; во]- Примеры функционалов, для которых

в

в

/(х) = |ж|(1 — е—|ж|) при в = 1 [16]- Отметим также, что субградиент / может быть нулевым только в точке минимума: равенство V/(х) = 0 влечет /(х) ^ /(ж*), что автоматически означает /(х) = /*.

Рассмотрим задачу (1.1) в случае, когда f * = f (х*) = min f (ж), а f —

слабо функция при некотором ß G (0; 1].

Предположим, что также верно условие острого минимума (1.8) для некоторого а > 0, где X* — множество точек минимума функции f на множестве Q, ^ртчём min ||ж — ж*Ц2 существует для произвольного х G Q.

В частности, условие (1.8) верно для задачи евклидова проектирования точки х0 па выпуклый ком пакт X* С причём / * = 0.

Предложим следующий вариант субградиентного метода с шагом

в

(1.11)

1.2.1 Классический острый минимум

xeQ

х ^ G.X^

xk+i = PrQ[xk — hk V/(хк)},

(1.12)

где при всяком к ^ 0 верно (IV/(хк)||2 = 0 (иначе решение уже найдено), а также

, = в(/(хк) — Я

Пк ты)|2 ■

Справедлива следующая

Теорема 1.2.1. Пусть / — елабо в-КвазивыпУКлая функция и для задачи минимизации / (1.1) с острым минимумом используется алгоритм, (1.12) с шагом

, = в(/(хк) — я п" ты)||2 ■

Тогда, после к итераций алгоритма (1.12) верно неравенство:

2о2

min ||^k+i — ж*||2 < П ( 1 — и J^r^ м,2 ) min ||жо — х*Ц\.

x*GX* |Vj (^)||2/ х* GX*

Доказательство. Как известно ([11], соотношения (3) из доказательства теоремы 1), для всякого х* G X* верно неравенство

hk(V/(xk),Xk — х*) < hk||V/(xk)||2 + min ||^k — х*Ц2 — min ||^k+i — ж*||2-

x % G XX* x % G XX *

ß

2ßhk(f(xk) — f(x*)) < hk||V/(^k)||2 + min ||tfk — ж*||2 — min ||zk+i — ^*||2•

x X x X

Поэтому

Список литературы диссертационного исследования кандидат наук Аблаев Сейдамет Серверович, 2024 год

Список литературы

1. Гасников А. В. Современные численные методы оптимизации. Метод универсального градиентного спуска. — М.: МЦНМО, 2021. — С. 272.

2. Криворот,ъко О. И. Математические модели эпидемиологии: идентифицируемость, регуляризация и программный комплекс : дис. ... д. физ.-мат. наук. — Моск. физ.-техн. ин-т., 2022. — С. 404.

3. A Parameter-free and projection free restarting level set method for adaptive constrained convex optimization under the error bound condition / Q. Lin [et al.] // arXiv preprint. — 2022. — URL: https://arxiv.org/pdf/2010. 15267.pdf.

4. Huang Y., Lin Q. Oracle complexity of single-loop switching subgradient methods for non-smooth weakly convex functional constrained optimization // arXiv preprint. ^ 2023. — URL: https://arxiv.org/pdf/2301.13314. pdf.

5. Поляк Б. Т. Введение в оптимизацию. — М: Наука, 1983. — С. 384.

6. Subgradient methods for sharp weakly convex functions / D. Davis [et al.] // Journal of Optimization Theory and Applications. — 2018. — Vol. 179. — P. 962-982.

7. Davis D., Drusvyatskiy D., Paquette C. The nonsmooth landscape of phase retrieval // IMA Journal of Numerical Analysis. — 2020. — Vol. 40, no. 4. — P. 2652-2695.

8. Duchi J., Ruan F. Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval Information and Inference //A Journal of the IMA. — 2019. — Vol. 8, no. 3. — P. 471-529.

9. Шор H. 3. Методы минимизации недифференцируемых функций и их применения. — Киев: Наук, думка, 1979.

10. О некоторых работах Бориса Теодоровича Поляка по сходимости градиентных методов и их развитии / С. С. Аблаев [и др.] // arXiv preprint. — 2023. — URL: https://arxiv.org/pdf/2311.16743.pdf.

11. Поляк Б. Т. Минимизация негладких функционалов // Журн. вычисл. математики и мат. физики. — 1969. Т. 9. Л'° 3. О. 509 521.

12. Burke J., Deng S. Weak Sharp Minima Revisited Part I: Basic Theory // Control and Cybernetics. — 2002. — Vol. 31. — P. 439-469.

13. Stochastic Polyak step-size for SGD: An adaptive learning rate for fast convergence / N. Loizou [et al.] // International Conference on Artificial Intelligence and Statistics. — PMLR. 2021. — P. 1306-1314.

14. Wang X., Johansson M.. Zhang T. Generalized Polyak step size for first order optimization with momentum // arXiv preprint arXiv:2305.12939. — 2023.

15. Jiang X., Stick S. U. Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction // arXiv preprint arXiv:2308.06058v. — 2023.

16. Hardt M.. Ма, Т., Recht B. Gradient descent learns linear dynamical systems // Journal of Machine Learning Research. — 2018. — Vol. 19. — P. 1-44.

17. Hinder О., Sidford A., Sohoni N. Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond // Proceedings of Machine Learning Research. — 2020. — Vol. 125. — P. 1-45.

18. Lu H. Relative Continuity for Non-Lipschitz Nonsmooth Convex Optimization Using Stochastic (or Deterministic) Mirror Descent // Informs Journal on Optimization. — 2019. — Vol. 1, no. 4. — P. 288-303.

19. Nesterov Y. Relative Smoothness: New Paradigm in Convex Optimization //. — EUSIPCO-2019. A Coruna, Spain, 2019. — Conference report.

20. Nesterov Y. Universal gradient methods for convex optimization problems // Mathematical Programming. — 2015. — Vol. 152, no. 1. — P. 381-404.

21. Нестеров Ю. E. Алгоритмическая выпуклая оптимизация. — M.: Моск. физ.-техн. ин-г.. 2013. - С. 367.

22. Inexact Relative Smoothness and Strong Convexity for Optimization and Variational Inequalities by Inexact Model / F. Stonyakin [et al.] // Optim. Methods and Software. — 2021. — Vol. 36, no. 6. — P. 1155-1201.

23. Cohen M.. Sidford A., Tian К. Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration // arXiv preprint. — 2020. — URL: https: //arxiv. org/pdf/2011.06572. pdf.

24. Some Adaptive First-Order Methods for Variational Inequalities with Relatively Strongly Monotone Operators and Generalized Smoothness / A. A. Titov [et al.] // Lecture Notes in Computer Science. — 2022. — Vol. 13781_ _ P 135^150.

25. Адаптивные методы для вариационных неравенств с относительно гладкими и относительно сильно монотонными операторами / С. С. Аблаев [и др.] // Программирование. — 2023. — № 6. — С. 5 13.

26. Nesterov Y. Rounding of convex sets and efficient gradient methods for linear programming problems // Optimization Methods and Software. — 2008. — Vol. 23, no. 1. — P. 109-128.

27. Nesterov Y. Unconstrained Convex Minimization in Relative Scale // Mathematics of Operations Research. — 2009. —Vol. 34, no. 1. — P. 180-193.

28. Кларк Ф. Оптимизация и негладкий анализ. — М. : Наука, 1988. — С. 279.

29. Демьянов В. Ф., Рощина В. А. Обобщенные субдифференциалы и экзостеры // Владикавказский математический журнал. — 2006. Т. 8. Л" 4. - С. 4 20.

30. Rademacher Н. Über partielle und totale differenzierbarkeit von Funktionen mehrerer Variabein und über die Transformation der Doppelintegrale // Mathematische Annalen. — 1919. — No. 79. — P. 340-359.

31. Шор H. 3. О классе почти-дифференцируемых функций и одном методе минимизации функций этого класса // Кибернетика. — 1972. - № 4. -С. 65^70.

32. Стонякин Ф. С., Аблаев С. С., Баран И. В. Адаптивные методы градиентного типа для задач оптимизации с относительной точностью и острым минимумом // Тр. Ин-та математики и механики УрО РАН. — 2021. - Т. 27, № 4. - С. 175—188.

33. Субградиентные методы для задач негладкой оптимизации с некоторой релаксацией условия острого минимума / С. С. Аблаев [и др.] // Компьютерные исследования и моделирование. — 2022. — Т. 14, № 2. — С. 473 495.

34. Тюрин А. Я., Гасников А. В. Быстрый градиентный спуск для задач выпуклой минимизации с оракулом, выдающим (6,Ь)-модель функции в запрошенной точке // Журн. вычисл. математики и мат. физики. —

2019. - Т. 59, № 7. - С. 1137—1150.

35. Нестеров Ю. Е. Методы выпуклой оптимизации. — М.: МЦНМО, 2010. — С. 281.

36. Нурминский Е. А. Квазиградиентный метод решения задачи нелинейного программирования // Кибернетика. — 1973. Л'° 1. С. 122 126.

37. Субградиентные методы для слабо выпуклых и относительно слабо выпуклых задач с острым минимумом / Ф. С. Стонякин [и др.] // Компьютерные исследования и моделирование. — 2023. — Т. 15, № 2. — С. 393 412.

38. Eldar Y., Mendelson S. Phase retrieval: stability and recovery guarantees // Appl. Comput. Harmon. Anal. — 2014. — Vol. 36, no. 3. — P. 473-494.

39. Incremental methods for weakly convex optimization / X. Li [et al.] // OPT2020: 12th Annual Workshop on Optimization for Machine Learning. —

2020.

40. Davis D., Drusvyatskiy D., Kellie M. Stochastic model-based minimization under high-order growth // arXiv preprint. — 2018. — URL: https : / / arxiv.org/pdf/1807.00255.pdf.

41. Брэгман Л. M. Релаксационный метод нахождения общей точки выпуклых множеств и его применение для решения задач выпуклого программирования // ЖВМ и МФ. — 1967. — Т. 7, № 3. — С. 200 217.

42. Макаренко Д. В. Разработка численных методов решения задач оптимизации при ослабленных условиях гладкости : дис. ... канд. / Макаренко Дмитрий Владимирович. — Моск. физ.-техн. ин-т., 2022. — С. 90.

43. Численные методы для некоторых классов вариационных неравенств с относительно сильно монотонными операторами / Ф. С. Стонякин [и др.] // Матем. заметки. - 2022. - Т. 112, № 6. - С. 879 894.

44. Поляк Б. Т. Один общий метод решения экстремальных задач // Докл. АН СССР. - 1967. - Т. 174, № 1. - С. 33 36.

45. Кларк Ф. Оптимизация и негладкий анализ. — М.: Наука, 1998. — С. 280. — Пер. с англ. под ред. В. И. Благодатских.

46. Adaptive mirror descent algorithms for convex and strongly convex optimization problems with functional constraints / F. Stonyakin [et al.] // J. Appl. Ind. Math. — 2019. — Vol. 13, no. 3. — P. 557-574.

47. Нестеров Ю. E. Эффективные методы нелинейного программирования. — М.: Радио и связь, 1989. — С. 301.

48. Адаптивные субградиентные методы для задач математического программирования с квазивыпуклыми функциями / С. С. Аблаев [и др.] // Тр. Ин-та математики и механики УрО РАН. — 2023. — Т. 29, Л" 3. - С. 7—25.

49. Метод зеркального спуска для условных задач оптимизации с большими значениями норм субградиентов функциональных ограничений / Ф. С. Стонякин [и др.] // Компьютерные исследования и моделирование. — 2020. - Т. 12, № 2. - С. 301—317.

50. Стонякин Ф. С. Адаптивные методы для вариационных неравенств и задач минимизации функционалов с обобщёнными условиями гладкости: дис. ... д. физ. мат. наук. - Моск. физ.-техн. ин-т., 2020. - С. 417.

51. Стонякин Ф. С. Адаптивные градиентные методы для некоторых классов задач негладкой оптимизации // arXiv preprint. — 2020. — URL: https : //arxiv.org/pdf/1911.08425.pdf.

52. Nesterov Y. Gradient methods for minimizing composite functions // Math. Program. — 2013. — Vol. 140. — P. 125-161.

53. Mirror descent and convex optimization problems with non-smooth inequality constraints / A. Bayandina [et al.] // Lecture Notes in Math. — 2018. — Vol. 2227. — P. 181-213.

54. Analogues of Switching Subgradient Schemes for Relatively Lipschitz-Continuous Convex Programming Problems / A. A. Titov [et al.] // arXiv preprint. ^ 2020. — URL: http://arxiv.org/pdf/2003.09147.pdf.

55. Analogues of Switching Subgradient Schemes for Relatively Lipschitz-Continuous Convex Programming Problems / A. A. Titov [et al.] // Mathematical Optimization Theory and Operations Research. — 2020. — Vol. 1275. — P. 133-149.

56. Титов А. А. Методы оптимизации для негладких задач в пространствах больших размерностей: дис. ... канд. физ. мат. наук. — Моск. физ.-техн. ин-т.. 2023. - С. 114.

57. Аблаев С. С., Баран И. В. О методах зеркального спуска для некоторых типов задач композитной оптимизации с функциональными ограничениями // Таврический вестник информатики и математики. — 2023. Л" 3. С. 7—18.

58. Стонякин Ф. С. Адаптивные зеркальные спуски для задач выпуклого программирования с использованием 6-субградиентов // arXiv preprint. — 2020. — URL: http://arxiv.org/pdf/2012.12856.pdf.

59. Субградиентные методы с шагом типа Б. Т. Поляка для задач минимизации квазивыпуклых функций с ограничениями-неравенствами и аналогами острого минимума / С. М. Пучинин [и др.] // arXiv preprint. — 2023. — URL: https://arxiv.org/pdf/2312.07465.pdf.

60. Стонякин Ф. С., Баран И. В. О некоторых алгоритмах для условных задач оптимизации с относительной точностью по целевому функционалу // Тр. ИММ УрО РАН. - 2020. - Т. 26, № 3. - С. 198-210.

61. Немировский А. С., Б Ю. Д. Сложность задач и эффективность методов оптимизации. — М.: Наука, 1979. — С. 384.

62. Jin Y., Sidford A., Tian К. Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods // arXiv preprint. — 2022. — URL: https://arxiv.org/pdf/2202.04640.pdf.

63. Численные методы для некоторых классов относительно сильно монотонных вариационных неравенств / Ф. С. Стонякин [и др.] // arXiv preprint. — 2022. — URL: https://arxiv.org/pdf/2109.03314.pdf.

64. Bauschke Я, Bolte i., Teboulle M. A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications // Mathematics of Operations Research. — 2017. — Vol. 42, no. 2. — P. 330-348.

65. Lu Я, Freund R. M.. Nesterov Y. Relatively smooth convex optimization by first-order methods, and applications // SIAM Journal on Optimization. — 2018. — Vol. 28, no. 1. — P. 333-354.

66. Statistically preconditioned accelerated gradient method for distributed optimization / H. Hendrikx [et al.] //In International conference on machine learning. — 2020. — P. 4203-4227. — PMLR.

67. Ben-Tal A., Nemirovski A. Robust Truss Topology Design via Semidefinite Programming // SIAM J. Optim. — 1997. — Vol. 7, no. 4. — P. 991-1016.

68. Shpirko S., Nesterov Y. Primal-dual subgradient methods for huge-scale linear conic problem // SIAM J. Optim. — 2014. — Vol. 24, no. 3. — P. 1444-1457.