URSS.ru Магазин научной книги
Обложка Жадан В.Г. Методы оптимизации. Часть 2: Численные алгоритмы Обложка Жадан В.Г. Методы оптимизации. Часть 2: Численные алгоритмы
Id: 315132
1020 р.

Методы оптимизации.
Часть 2: ЧИСЛЕННЫЕ АЛГОРИТМЫ. Ч.2. Изд. 2

Методы оптимизации. Часть 2: Численные алгоритмы URSS. 2024. 328 с. ISBN 978-5-9710-9990-1.
Белая офсетная бумага

Аннотация

Настоящая книга написана на основе материалов курса «Методы оптимизации». Автор книги, доктор физико-математических наук В.Г.Жадан, читал этот курс в течение нескольких лет студентам-третьекурсникам факультета управления и прикладной математики Московского физико-технического института. Книга является учебным пособием по теории и численным методам решения оптимизационных задач.

Издание состоит из трех частей. Данная, вторая часть посвящена численным... (Подробнее)


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

Об авторе
top
photoЖадан Виталий Григорьевич
Доктор физико-математических наук, профессор Московского физико-технического института (МФТИ). Специалист в области методов оптимизации. Окончил МФТИ по специальности «инженер-физик». Работал в Вычислительном центре АН СССР (позже ВЦ РАН, ныне Вычислительный центр им. А. А. Дородницына ФИЦ «Информатика и управление» РАН, ВЦ ФИЦ ИУ РАН). В 1992 г. защитил докторскую диссертацию на тему «Разработка и систематизация численных методов условной оптимизации». В 1993–2015 гг. руководил отделом прикладных проблем оптимизации ВЦ РАН, затем был главным научным сотрудником ВЦ РАН. Преподавал в МФТИ, читал лекции по курсам оптимизации и оптимального управления. За педагогическую работу был удостоен звания «Заслуженный профессор МФТИ». Автор более 100 научных работ и учебных пособий.

С начала 1970-х гг. в лаборатории исследования операций ВЦ АН СССР (на ее основе в 1978 г. был создан отдел прикладных проблем оптимизации) велись работы по построению методов внутренней точки для решения различных задач нелинейного программирования. Эти методы, перенесённые на задачи линейного программирования, породили новый класс несимплексных методов. Почти сразу к этим исследованиям был привлечён и В. Г. Жадан, получивший основные результаты и разработавший общий подход к построению методов внутренней точки для решения задач линейного и нелинейного программирования, основанный на преобразовании пространств. Позже, с середины 1980-х гг., Ю. Г. Евтушенко и В. Г. Жадан исследовали применение разнообразных вспомогательных функций для методов условной оптимизации, и развитый подход по построению этих функций позволил В. Г. Жадану в конце 1980-х гг. перенести его на задачи обобщённого линейного программирования и на задачи многокритериальной оптимизации. В обобщение соответствующих методов нелинейного программирования им были предложены новые численные методы, в которых в ходе итерации меняются целевые точки. На основе этих исследований была создана система для решения многокритериальных задач нелинейного программирования ДИСО/ПК-МКО.