Предисловие к серии «Учебник Школы прикладной математики и информатики МФТИ» (А. М. Райгородский) | 4
|
Предисловие | 6
|
Введение | 7
|
Глава 1. Основные определения | 10
|
Глава 2. Методы одномерной и безусловной минимизации | 16
|
2.1. Методы одномерной минимизации | 16
|
2.2. Методы спуска | 28
|
2.2.1. Общая схема методов спуска | 28
|
2.2.2. Правила выбора длины шага | 30
|
2.3. Метод градиентного спуска | 34
|
2.4. Метод Ньютона | 41
|
2.4.1. Метод Ньютона с постоянным шагом | 42
|
2.4.2. Метод Ньютона с переменным шагом | 46
|
2.4.3. Квазиньютоновские методы | 49
|
2.5. Метод сопряженных градиентов | 56
|
2.5.1. Метод сопряженных направлений для квадратичных функций | 57
|
2.5.2. Метод сопряженных градиентов для квадратичных функций | 60
|
2.5.3. Метод сопряженных градиентов для произвольных функций | 64
|
Глава 3. Методы линейной и квадратичной оптимизации | 68
|
3.1. Симплекс-метод для задач линейного программирования | 68
|
3.1.1. Оптимальные решения в задачах линейного программирования | 69
|
3.1.2. Базис угловой точки | 72
|
3.1.3. Симплекс-метод | 75
|
3.1.4. Двойственный симплекс-метод | 86
|
3.2. Методы квадратичного программирования | 89
|
Глава 4. Методы минимизации на множествах простого вида | 97
|
4.1. Метод проекции градиента | 97
|
4.2. Метод условного градиента и условный метод Ньютона | 106
|
4.3. Метод приведенного градиента | 112
|
4.4. Метод приведенных ньютоновских направлений | 116
|
Глава 5. Методы линеаризации и последовательного квадратичного программирования | 120
|
5.1. Метод возможных направлений | 120
|
5.2. Метод линеаризации | 127
|
5.3. Методы последовательного квадратичного программирования | 137
|
Глава 6. Методы последовательной безусловной минимизации | 143
|
6.1. Методы штрафных функций | 143
|
6.1.1. Методы внешних штрафных функций | 144
|
6.1.2. Методы внутренних штрафных функций | 152
|
6.2. Методы параметризации целевой функции | 160
|
6.3. Методы центров | 168
|
6.3.1. Вспомогательные функции и классификация методов | 168
|
6.3.2. Методы внутренних центров | 171
|
Глава 7. Методы, использующие функцию Лагранжа или ее модификации | 178
|
7.1. Метод Удзавы | 178
|
7.2. Метод модифицированной функции Лагранжа | 184
|
7.3. Другие варианты методов МФЛ | 196
|
7.3.1. Двойственные методы МФЛ | 197
|
7.3.2. Прямые методы МФЛ | 203
|
Глава 8. Методы внутренней точки | 212
|
8.1. Мультипликативно-барьерный метод | 213
|
8.2. Аффинно-масштабирующий метод | 225
|
8.3. Метод Кармаркара | 228
|
8.4. Прямо-двойственные методы центрального пути | 234
|
Глава 9. Сложность задач и эффективность методов | 245
|
9.1. Сложность задачи для методов | 245
|
9.2. Самосогласованные функции | 252
|
9.3. Ньютоновские методы в выпуклой оптимизации | 261
|
Глава 10. Методы многокритериальной оптимизации | 267
|
10.1. Метод внешних центров для многокритериальной оптимизации | 269
|
10.2. Метод возможных направлений для многокритериальной оптимизации | 273
|
10.3. Метод модифицированной функции Лагранжа для многокритериальной оптимизации | 281
|
Глава 11. Методы глобальной оптимизации | 288
|
11.1. Постановка задачи глобальной оптимизации | 288
|
11.2. Метод ломаных | 291
|
11.3. Метод неравномерных покрытий | 294
|
11.4. Метод секущих углов | 299
|
Ссылки на литературу и комментарии | 309
|
Литература | 314
|
Жадан Виталий Григорьевич Доктор физико-математических наук, профессор Московского физико-технического института (МФТИ). Специалист в области методов оптимизации. Окончил МФТИ по специальности «инженер-физик». Работал в Вычислительном центре АН СССР (позже ВЦ РАН, ныне Вычислительный центр им. А. А. Дородницына ФИЦ «Информатика и управление» РАН, ВЦ ФИЦ ИУ РАН). В 1992 г. защитил докторскую диссертацию на тему «Разработка и систематизация численных методов условной оптимизации». В 1993–2015 гг. руководил отделом прикладных проблем оптимизации ВЦ РАН, затем был главным научным сотрудником ВЦ РАН. Преподавал в МФТИ, читал лекции по курсам оптимизации и оптимального управления. За педагогическую работу был удостоен звания «Заслуженный профессор МФТИ». Автор более 100 научных работ и учебных пособий.
С начала 1970-х гг. в лаборатории исследования операций ВЦ АН СССР (на ее основе в 1978 г. был создан отдел прикладных проблем оптимизации) велись работы по построению методов внутренней точки для решения различных задач нелинейного программирования. Эти методы, перенесённые на задачи линейного программирования, породили новый класс несимплексных методов. Почти сразу к этим исследованиям был привлечён и В. Г. Жадан, получивший основные результаты и разработавший общий подход к построению методов внутренней точки для решения задач линейного и нелинейного программирования, основанный на преобразовании пространств. Позже, с середины 1980-х гг., Ю. Г. Евтушенко и В. Г. Жадан исследовали применение разнообразных вспомогательных функций для методов условной оптимизации, и развитый подход по построению этих функций позволил В. Г. Жадану в конце 1980-х гг. перенести его на задачи обобщённого линейного программирования и на задачи многокритериальной оптимизации. В обобщение соответствующих методов нелинейного программирования им были предложены новые численные методы, в которых в ходе итерации меняются целевые точки. На основе этих исследований была создана система для решения многокритериальных задач нелинейного программирования ДИСО/ПК-МКО.