Современные эффективные методы выпуклой оптимизации, осень 2023

О курсе

Альтернативный курс для студентов 4 курса в осеннем семестре от кафедры МОУ.

1. Общая нелинейная оптимизация и ее сложность.

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

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

2. Оптимальные методы для гладких выпуклых задач.

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

3. Методы отсекающей гиперплоскости для задач выпуклой конечномерной минимизации.

Методы отсекающей гиперплоскости для задач выпуклой конечномерной минимизации. Постановка задачи разрешимости. Нижняя оценка сложности для данного класса задач. Принцип локализации решения. Методы отсекающей гиперплоскости. Обобщенный метод отсекающей гиперплоскости. Метод эллипсоидов. Структурная оптимизация. Самосогласованные функции. Примеры и свойства самосогласованных функций. Основные неравенства. Минимизация самосогласованных функций.

4. Структурная оптимизация. Гладкая минимизация для негладких функций.

Структурная оптимизация. Самосогласованные барьеры. Постановка задачи. Уравнение центральной траектории. Самосогласованный барьер. Примеры и свойства самосогласованного барьера. Аналитический центр множества. Метод отслеживания траектории и оценки его скорости сходимости. Гладкая минимизация для негладких функций: прорыв за пределы возможного. Постановка задачи. Функции с явно заданной структурой. Понятие сопряженной (дуальной) задачи. Прокс-функция. Техника сглаживания. Оптимальная схема для решения задач гладкой оптимизации. Применение данного подхода к матричным играм, задаче Штейнера, вариационным неравенствам.

5. Прямо-двойственные методы решения негладких задач. Минимизация составных функций.

Прямо-двойственные методы решения негладких задач. Нижняя линейная аппроксимация (модель) исходной целевой функции. Сильное и слабое решение негладкой задачи. Функция зазора и ее свойства. Общая схема двойственного усреднения. Метод простого двойственного усреднения. Метод взвешенного двойственного усреднения. Оценки скорости их сходимости. Применение метода двойственного усреднения к общей задаче минимизации, прямо-двойственной задаче, минимаксной задаче, седловой задаче. Экономическая интерпретация метода двойственного усреднения (модель сбалансированного развития). Минимизация составных функций. Генерация разреженных решений. Постановка задачи. Понятие градиентного композитного отображения и его свойства. Прямой градиентный метод. Оценки его скорости сходимости в выпуклом и сильно выпуклом случае. Двойственный градиентный метод и его оценки скорости сходимости. Двойственный градиентный метод с ускорением и его оценки скорости сходимости. Применение данных методов к решению задачи разреженных наименьших квадратов. Обсуждение численных результатов.

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

Методы покоординатного спуска решения задач сверхбольшой размерности. Специфика задач сверхбольшой размерности. Метод случайного покоординатного спуска для решения выпуклых задач безусловной минимизации и его оценки скорости сходимости. Метод случайного покоординатного спуска для решения сильно выпуклых задач безусловной минимизации и его оценки скорости сходимости. Метод случайного покоординатного спуска для решения выпуклых задач условной минимизации и его оценки скорости сходимости. Метод случайного покоординатного спуска с ускорением для решения выпуклых задач безусловной минимизации и его оценки скорости сходимости. Обсуждение численных результатов работы данных методов. Субградиентные методы решения задач сверхбольшой размерности. Эффективный пересчет матрично-векторного произведения в разреженном случае. Быстрый пересчет значения симметричной функции с помощью бинарного дерева. Субградиентный метод Б. Поляка для решения задач безусловной оптимизации и оценка его скорости сходимости. Субградиентный метод Н.Шора для решения задач условной оптмизации и оценка его скорости сходимости. Применение данной техники пересчета к задачам сверхбольшой размерности с разреженной структурой. Метод случайного покоординатного спуска для решения негладкой задачи минимизации с разреженным субградиентом. Применение техники пересчета к данному методу.