URSS.ru Магазин научной книги
Обложка Нестеров Ю.Е. Алгоритмическая выпуклая оптимизация Обложка Нестеров Ю.Е. Алгоритмическая выпуклая оптимизация
Id: 305676
1259 р.

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

URSS. 2024. 364 с. ISBN 978-5-00237-001-6.
Белая офсетная бумага

Аннотация

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


Оглавление
top
Предисловие к серии «Учебник Школы прикладной математики и информатики МФТИ» (А. М. Райгородский)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

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

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