Алгоритмическая выпуклая оптимизация

• Автор: Нестеров, Юрий Евгеньевич
• Шифр специальности: 01.01.07
• Научная степень: Докторская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 367 с.

Оглавление
Введение

1 Предварительные результаты

1.1 Классификация выпуклых функций

1.1.1 Нормы и производные

1.1.2 Классы гладких функций

1.1.3 Равномерно выпуклые функции

1.1.4 Сильно выпуклые функции

1.2 Методы гладкой минимизации первого порядка

1.2.1 Прямой и двойственный градиентные методы

1.2.2 Быстрый градиентный метод

1.2.3 Минимизация гладких сильно выпуклых функций
1.3 Самосогласованные функции и барьеры
1.3.1 Определение и свойства самосогласованных функций
1.3.2 Минимизация самосогласованных функций
1.3.3 Самосогласованные барьеры и метод отслеживания траектории
1.3.4 Конструирование самосогласованных барьеров
2 Современные субградиентные методы
2.1 Прямо-двойственные методы для негладких задач
2.1.1 Введение
2.1.2 Основные алгоритмические схемы
2.1.3 Минимизация на простых множествах
2.1.4 Седловые задачи
2.1.5 Вариационные неравенства
2.1.6 Стохастическая оптимизация
2.1.7 Приложения в моделировании
2.1.8 Обсуждение
2.2 Барьерный субградиентный метод
2.2.1 Введение
'2.2.2 Сглаживание с помощью самосогласованного барьера

2.2.3 Барьерный субградиентный метод
2.2.4 Максимизация положительной вогнутой функции
2.2.5 Приложения
2.2.6 Оптимизация в реальном времени как альтернатива стохастическому
программированию
2.3 Градиентные методы минимизации составных функций
2.3.1 Введение
2.3.2 Составное градиентное отображение
2.3.3 Составной градиентный метод
2.3.4 Быстрый градиентный метод
2.3.5 Примеры применения
2.3.6 Вычислительные эксперименты
2.4 Приложение: барьерная проекция на симплекс
3 Вариационные неравенства
3.1 Вариационные неравенства с гладким оператором
3.1.1 Введение
3.1.2 Двойственная экстраполяция
3.1.3 Алгоритмические схемы
3.1.4 Вычисление седловых точек
3.1.5 Билинейные матричные игры
3.1.6 Обсуждение
3.2 Сильно монотонные операторы и квазивариационные неравенства
3.2.1 Введение
3.2.2 Решение сильно монотонных вариационных неравенств
3.2.3 Квазивариационные неравенства
3.2.4 Оператор релаксации для квазивариационного неравенства
4 Методы второго порядка
4.1 Кубическая регуляризация метода Ньютона
4.1.1 Введение
4.1.2 Кубическая регуляризация квадратичной аппроксимации
4.1.3 Общие результаты о сходимости
4.1.4 Глобальные оценки эффективности для специальных классов задач .
4.1.5 Вычислительные детали
4.1.6 Обсуждение
4.2 Ускоренная кубическая регуляризация метода Ньютона
4.2.1 Введение
4.2.2 Итерация кубической регуляризации метода Ныотона
4.2.3 Ускоренный метод

4.2.4 Глобальная невырожденность для методов второго порядка
4.2.5 Минимизация сильно выпуклых функций
4.2.6 Ложное ускорение
4.2.7 Обсуждение
4.3 Модифицированный метод Гаусса-Ньютона
4.3.1 Введение
4.3.2 Модифицированный метод Гаусса-Ньютона
4.3.3 Процесс минимизации
4.3.4 Глобальная скорость сходимости
4.3.5 Обсуждение
5 Техника сглаживания
5.1 Сглаживание для явной модели целевой функции
5.1.1 Введение
5.1.2 Гладкие аппроксимации негладких функций
5.1.3 Примеры приложений
5.1.4 Вычислительные аспекты
5.1.5 Вычислительные эксперименты
5.2 Условие обратного зазора в негладкой выпуклой минимизации
5.2.1 Введение
5.2.2 Описание структуры задач
5.2.3 Условие обратного зазора
5.2.4 Метод с градиентным отображением
5.2.5 Метод с брегмановской проекцией
5.2.6 Анализ скорости сходимости
5.2.7 Минимизация сильно выпуклых функций
5.3 Техника сглаживания в полуопределенной оптимизации
5.3.1 Введение
5.3.2 Гладкие симметричные функции собственных значений
5.3.3 Минимизация максимального собственного значения симметрической
матрицы
5.3.4 Минимизация спектрального радиуса симметрических матриц
6 Оптимизация с относительной точностью
6.1 Однородная модель
6.1.1 Введение
6.1.2 Коническая задача безусловной минимизации
6.1.3 Субградиентная аппроксимирующая схема
6.1.4 Минимизация составной функции
6.1.5 Примеры приложений

Так как функция фк{х) сильно выпукла с параметром единица,
(1 1 зо) г
ф*к+1 > min |ф*к + ак\х - хк\2 + тд^[/(хк) + (V/(ar*), х - хк) + а2\х - х0||2]|
(1 2 3)
> Ф1 + 1^/Ы-
Осталось заметить, что фк+i(a) < |||ж — жо||2 + j~Akf(x,). Таким образом,
^+1 - ^[^x~Xo^ + L^A^f(T)] < III** “ xol!2 + T=^Akf(^)-
Поскольку j^a > е, теорема доказана. □
Как и для прямого градиентного метода (1.2.7), оценка скорости сходимости двойственного градиентного метода (1.2.26) непрерывна по а2. Когда <т2 стремится к нулю, правая часть неравенства (1.2.27) монотонно возрастает и достигает уровня (1.2.11).
Наконец, рассмотрим версию быстрого градиентного метода, применяемую для минимизации сильно выпуклых функций. Как и в двойственном градиентном методе, в методе (1.2.18) можно было бы изменить правила пересчета модели целевой функции, добавив соответствующий квадратичный член. Однако существует и другая возможность.
Обозначим через Optjv(x-o) точку ду, полученную с помощью метода (1.2.18) после N итераций, запущенных из точки Хо■ Зададим N =Jk1^2(/)L+1 и рассмотрим следующий процесс:
Щ £ Q-. Uk+i = OptiN{uk), к> 0. (1.2.29)
Мы пользуемся евклидовой метрикой, поэтому
,,11 .112 (1 2 20) (1 1 30)
* /К+:)-/(**) > f|k+1-z*||2.
Следовательно, ввиду определения числа N мы получим |k+i — а:*|| < |||щ — л*||. Таким образом, метод (1.2.29) достигнет точности е за
0(к1/2(/)1п1)
итераций. Для прямого и двойственного градиентного методов мы можем гарантировать только оценку в 0(к(/) In -) итераций.
1.3 Самосогласованные функции и барьеры
1.3.1 Определение и свойства самосогласованных функций
В этой работе мы не собираемся детально рассматривать полиномиальные методы внутренней точки. Поэтому ниже приводится очень краткая версия соответствующей теории,