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

Nesterov Yu.E. /Algorithmic convex optimization

2024. 364 с.

Серия: Учебник Школы прикладной математики и информатики МФТИ

Белая офсетная бумага

Мягкая обложка
Твердый переплет 1712 р. ››

Аннотация

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

Оглавление

Предисловие к серии «Учебник Школы прикладной математики и информатики МФТИ» (А. М. Райгородский)				8
Введение				10
Глава 1. Предварительные результаты				16
1.1. Классификация выпуклых функций				16
1.1.1. Нормы и производные				16
1.1.2. Классы гладких функций				18
1.1.3. Равномерно выпуклые функции				22
1.1.4. Сильно выпуклые функции				26
1.2. Методы гладкой минимизации первого порядка				28
1.2.1. Прямой и двойственный градиентные методы				28
1.2.2. Быстрый градиентный метод				31
1.2.3. Минимизация гладких сильно выпуклых функций				34
1.3. Самосогласованные функции и барьеры				38
1.3.1. Определение и свойства самосогласованных функций				38
1.3.1.1. Основные неравенства				43
1.3.2. Минимизация самосогласованных функций				49
1.3.3. Самосогласованные барьеры и метод отслеживания траектории				54
1.3.3.1. Мотивировка				54
1.3.3.2. Определение самосогласованного барьера				55
1.3.3.3. Основные неравенства				58
1.3.3.4. Метод отслеживания траектории				62
1.3.3.5. Нахождение аналитического центра				65
1.3.3.6. Логарифмически однородные барьеры				68
1.3.4. Конструирование самосогласованных барьеров				69
1.3.4.1. Границы на параметр				69
1.3.4.2. Положительный ортант				72
1.3.4.3. Конус Лоренца				72
1.3.4.4. Полуопределенная оптимизация				74
1.3.4.5. Надграфики функций одной переменной				76
Глава 2. Современные субградиентные методы				78
2.1. Прямо-двойственные методы для негладких задач				78
2.1.1. Введение				78
2.1.1.1. Мотивировка				78
2.1.1.2. Содержание				80
2.1.1.3. Общие факты и обозначения				82
2.1.2. Основные алгоритмические схемы				82
2.1.3. Минимизация на простых множествах				89
2.1.3.1. A. Общая задача минимизации				89
2.1.3.2. B. Прямо-двойственная задача				90
2.1.3.3. C. Минимаксные задачи				92
2.1.3.4. D. Задачи с простыми функциональными ограничениями				94
2.1.4. Седловые задачи				97
2.1.5. Вариационные неравенства				100
2.1.6. Стохастическая оптимизация				101
2.1.7. Приложения в моделировании				104
2.1.7.1. Алгоритм сбалансированного развития				104
2.1.7.2. Предварительное планирование в сравнении с динамической настройкой				108
2.1.8. Обсуждение				110
2.2. Барьерный субградиентный метод				112
2.2.1. Введение				112
2.2.1.1. Мотивировка				112
2.2.1.2. Содержание				113
2.2.1.3. Обозначения				114
2.2.2. Сглаживание с помощью самосогласованного барьера				114
2.2.3. Барьерный субградиентный метод				116
2.2.4. Максимизация положительной вогнутой функции				121
2.2.5. Приложения				123
2.2.5.1. Вычисление дробных покрытий				124
2.2.5.2. Максимальные многопродуктовые потоки				124
2.2.5.3. Минимаксные задачи с неотрицательными компонентами				125
2.2.5.4. Полуопределенная релаксация булевского квадратичного программирования				126
2.2.6. Оптимизация в реальном времени как альтернатива стохастическому программированию				127
2.2.6.1. Принятие решений в условиях неопределенности				127
2.2.6.2. Управление портфелем ценных бумаг				130
2.2.6.3. Процессы с полным производственным циклом				131
2.2.6.4. Обсуждение				131
2.3. Градиентные методы минимизации составных функций				132
2.3.1. Введение				132
2.3.1.1. Мотивировка				132
2.3.1.2. Содержание				133
2.3.1.3. Обозначения				134
2.3.2. Составное градиентное отображение				135
2.3.3. Составной градиентный метод				140
2.3.4. Быстрый градиентный метод				146
2.3.5. Примеры применения				153
2.3.5.1. Строго выпуклая целевая функция с известным параметром				153
2.3.5.2. Приближенное условие оптимальности первого порядка				154
2.3.5.3. Неизвестный параметр сильной выпуклости				156
2.3.6. Вычислительные эксперименты				157
2.4. Приложение: барьерная проекция на симплекс				167
Глава 3. Вариационные неравенства				170
3.1. Вариационные неравенства с гладким оператором				170
3.1.1. Введение				170
3.1.1.1. Мотивировка				170
3.1.1.2. Содержание				170
3.1.1.3. Обозначения				171
3.1.2. Двойственная экстраполяция				171
3.1.3. Алгоритмические схемы				176
3.1.4. Вычисление седловых точек				180
3.1.5. Билинейные матричные игры				184
3.1.6. Обсуждение				189
3.2. Сильно монотонные операторы и квазивариационные неравенства				190
3.2.1. Введение				190
3.2.1.1. Мотивировка				190
3.2.1.2. Содержание				191
3.2.1.3. Обозначения				191
3.2.2. Решение сильно монотонных вариационных неравенств				191
3.2.3. Квазивариационные неравенства				196
3.2.4. Оператор релаксации для квазивариационного неравенства				199
Глава 4. Методы второго порядка				204
4.1. Кубическая регуляризация метода Ньютона				204
4.1.1. Введение				204
4.1.1.1. Мотивировка				204
4.1.1.2. Содержание				206
4.1.1.3. Обозначения				206
4.1.2. Кубическая регуляризация квадратичной аппроксимации				207
4.1.3. Общие результаты о сходимости				210
4.1.4. Глобальные оценки эффективности для специальных классов задач				214
4.1.4.1. Звездно-выпуклые функции				215
4.1.4.2. Градиентно доминируемые функции				218
4.1.4.3. Нелинейные преобразования выпуклых функций				222
4.1.5. Вычислительные детали				225
4.1.5.1. Минимизируя кубическую регуляризацию				225
4.1.5.2. Стратегии одномерного поиска				229
4.1.6. Обсуждение				230
4.2. Ускоренная кубическая регуляризация метода Ньютона				233
4.2.1. Введение				233
4.2.1.1. Мотивировка				233
4.2.1.2. Содержание				233
4.2.1.3. Обозначения				234
4.2.2. Итерация кубической регуляризации метода Ньютона				235
4.2.3. Ускоренный метод				238
4.2.4. Глобальная невырожденность для методов второго порядка				241
4.2.5. Минимизация сильно выпуклых функций				244
4.2.6. Ложное ускорение				246
4.2.7. Обсуждение				247
4.3. Модифицированный метод Гаусса—Ньютона				248
4.3.1. Введение				248
4.3.1.1. Мотивировка				248
4.3.1.2. Содержание				249
4.3.1.3. Обозначения				250
4.3.2. Модифицированный метод Гаусса—Ньютона				250
4.3.3. Процесс минимизации				255
4.3.4. Глобальная скорость сходимости				257
4.3.5. Обсуждение				261
4.3.5.1. Сравнительный анализ модифицированного метода Гаусса—Ньютона				261
4.3.5.2. Вычислительные аспекты				262
Глава 5. Техника сглаживания				264
5.1. Сглаживание для явной модели целевой функции				264
5.1.1. Введение				264
5.1.1.1. Мотивировка				264
5.1.1.2. Содержание				265
5.1.1.3. Обозначения				265
5.1.2. Гладкие аппроксимации негладких функций				266
5.1.3. Примеры приложений				269
5.1.3.1. Минимаксные стратегии для матричных игр				270
5.1.3.2. Непрерывная задача размещения				273
5.1.3.3. Вариационные неравенства с линейным оператором				274
5.1.3.4. Минимизация кусочно-линейных функций				276
5.1.4. Вычислительные аспекты				278
5.1.4.1. Вычислительная сложность				278
5.1.4.2. Вычислительная устойчивость				280
5.1.4.3. Модифицированный метод				281
5.1.5. Вычислительные эксперименты				283
5.2. Условие обратного зазора в негладкой выпуклой минимизации				285
5.2.1. Введение				285
5.2.1.1. Мотивировка				285
5.2.1.2. Содержание				286
5.2.2. Описание структуры задач				286
5.2.3. Условие обратного зазора				287
5.2.4. Метод с градиентным отображением				288
5.2.5. Метод с брегмановской проекцией				290
5.2.6. Анализ скорости сходимости				293
5.2.7. Минимизация сильно выпуклых функций				295
5.3. Техника сглаживания в полуопределенной оптимизации				300
5.3.1. Введение				300
5.3.1.1. Мотивировка				300
5.3.1.2. Содержание				301
5.3.1.3. Обозначения				302
5.3.2. Гладкие симметричные функции собственных значений				303
5.3.3. Минимизация максимального собственного значения симметрической матрицы				306
5.3.4. Минимизация спектрального радиуса симметрических матриц				308
Глава 6. Оптимизация с относительной точностью				312
6.1. Однородная модель				312
6.1.1. Введение				312
6.1.1.1. Мотивировка				312
6.1.1.2. Содержание				313
6.1.1.3. Обозначения				313
6.1.2. Коническая задача безусловной минимизации				314
6.1.3. Субградиентная аппроксимирующая схема				318
6.1.4. Минимизация составной функции				320
6.1.5. Примеры приложений				325
6.1.5.1. Линейное программирование				325
6.1.5.2. Минимизация спектрального радиуса				327
6.1.5.3. Расчет оптимальных механических конструкций				330
6.2. Эллипсоидальная аппроксимация выпуклых тел				332
6.2.1. Введение				332
6.2.1.1. Мотивировка				332
6.2.1.2. Содержание				333
6.2.1.3.Обозначения				334
6.2.2. Вычисление эллипсоидов Джона				335
6.2.2.1. A. Центрально симметричные выпуклые множества				335
6.2.2.2. B. Общие выпуклые множества				339
6.2.2.3. C. Знакоинвариантные множества				342
6.2.3. Минимизация максимального модуля линейных форм				346
6.2.4. Билинейные матричные игры с неотрицательными коэффициентами				350
Заключение				352
Литература				354

Об авторе

Нестеров Юрий Евгеньевич

Доктор физико-математических наук. С 1993 г. работает в Католическом университете города Лувен в Бельгии; ныне состоит в должности ординарного профессора Католического университета Лувена. Его основные результаты связаны с построением новых эффективных методов выпуклой оптимизации. Опубликовал более 150 статей и пять монографий. Среди его главных достижений можно отметить разработку полиномиальных методов внутренней точки, быстрых градиентных методов и современных методов второго и более высоких порядков. Лауреат нескольких престижных международных премий (Данцига, фон Неймана, Ланчестера и др.). Член Европейской академии наук и Национальной академии наук США.

В 2023 г. совместно с А. С. Немировским удостоен Премии Всемирной ассоциации лауреатов (WLA) в области компьютерных наук или математики (World Laureates Association Prize in Computer Science or Mathematics) — аналога Нобелевской премии в этих дисциплинах.