| Предисловие к серии «Учебник Школы прикладной математики и информатики МФТИ» (А. М. Райгородский) | 3
|
| Предисловие | 5
|
| Введение | 6
|
| Глава 1. Линейные задачи дополнительности | 10
|
| 1.1. Постановка и источники линейных задач дополнительности | 10
|
| 1.1.1. Постановка задачи | 10
|
| 1.1.2. Источники линейных задач дополнительности | 11
|
| 1.2. Разрешимость линейных задач дополнительности | 19
|
| 1.2.1. Комплементарная область значений | 19
|
| 1.2.2. Q и Q 0 -матрицы | 20
|
| 1.3. Классы матриц и их связь с Q 0 и Q-матрицами | 23
|
| 1.3.1. Положительно определенные и полуопределенные матрицы | 24
|
| 1.3.2. S и S 0 -матрицы | 25
|
| 1.3.3. Полумонотонные и строго полумонотонные матрицы | 29
|
| 1.3.4. Коположительные и строго коположительные матрицы | 32
|
| 1.3.5. Достаточные матрицы | 35
|
| 1.3.6. P и P 0 -матрицы | 36
|
| 1.4. Существование решений ЛЗД и их единственность | 40
|
| 1.4.1. ЛЗД с положительно определенными матрицами | 40
|
| 1.4.2. ЛЗД со строго коположительными матрицами | 43
|
| 1.4.3. ЛЗД c P-матрицами | 49
|
| 1.5. Метод решения ЛЗД симплексного типа | 50
|
| 1.5.1. Ведущее преобразование | 50
|
| 1.5.2. Метод Лемке | 54
|
| 1.5.3. Сходимость метода Лемке | 62
|
| 1.6. Мультипликативно-барьерный метод для ЛЗД | 66
|
| Глава 2. Вариационные неравенства и задачи дополнительности | 80
|
| 2.1. Начальные сведения о вариационных неравенствах | 80
|
| 2.1.1. Постановки задач и их взаимосвязь | 80
|
| 2.1.2. Сведение вариационных неравенств и задач дополнительности к другим задачам | 84
|
| 2.2. Существование решений и единственность | 88
|
| 2.3. Численные методы решения вариационных неравенств и НЗД | 103
|
| 2.3.1. Проекционный метод | 103
|
| 2.3.2. Методы линеаризации | 105
|
| 2.3.3. Методы оценочных функций | 107
|
| Глава 3. Линейное полуопределенное программирование | 114
|
| 3.1. Симметричные положительно полуопределенные матрицы | 114
|
| 3.2. Прямая и двойственная задачи | 123
|
| 3.3. Полуопределенное программирование и оптимизация | 127
|
| 3.4. Допустимые множества и невырожденность | 134
|
| 3.4.1. Строение допустимого множества и невырожденность в прямой задаче | 134
|
| 3.4.2. Строение допустимого множества и невырожденность в двойственной задаче | 139
|
| 3.5. Условия оптимальности и единственность решений | 144
|
| Глава 4. Численные методы решения задач полуопределенного программирования | 149
|
| 4.1. Симплекс-метод | 150
|
| 4.2. Двойственный симплекс-метод | 161
|
| 4.3. Мультипликативно-барьерный метод | 173
|
| 4.4. Двойственный мультипликативно-барьерный метод | 188
|
| 4.5. Прямо-двойственный метод Ньютона | 209
|
| Приложение | 217
|
| Вспомогательные сведения из матричного анализа | 217
|
| Ссылки на литературу и комментарии | 237
|
| Литература | 240
|
Жадан Виталий Григорьевич Доктор физико-математических наук, профессор Московского физико-технического института (МФТИ). Специалист в области методов оптимизации. Окончил МФТИ по специальности «инженер-физик». Работал в Вычислительном центре АН СССР (позже ВЦ РАН, ныне Вычислительный центр им. А. А. Дородницына ФИЦ «Информатика и управление» РАН, ВЦ ФИЦ ИУ РАН). В 1992 г. защитил докторскую диссертацию на тему «Разработка и систематизация численных методов условной оптимизации». В 1993–2015 гг. руководил отделом прикладных проблем оптимизации ВЦ РАН, затем был главным научным сотрудником ВЦ РАН. Преподавал в МФТИ, читал лекции по курсам оптимизации и оптимального управления. За педагогическую работу был удостоен звания «Заслуженный профессор МФТИ». Автор более 100 научных работ и учебных пособий.
С начала 1970-х гг. в лаборатории исследования операций ВЦ АН СССР (на ее основе в 1978 г. был создан отдел прикладных проблем оптимизации) велись работы по построению методов внутренней точки для решения различных задач нелинейного программирования. Эти методы, перенесённые на задачи линейного программирования, породили новый класс несимплексных методов. Почти сразу к этим исследованиям был привлечён и В. Г. Жадан, получивший основные результаты и разработавший общий подход к построению методов внутренней точки для решения задач линейного и нелинейного программирования, основанный на преобразовании пространств. Позже, с середины 1980-х гг., Ю. Г. Евтушенко и В. Г. Жадан исследовали применение разнообразных вспомогательных функций для методов условной оптимизации, и развитый подход по построению этих функций позволил В. Г. Жадану в конце 1980-х гг. перенести его на задачи обобщённого линейного программирования и на задачи многокритериальной оптимизации. В обобщение соответствующих методов нелинейного программирования им были предложены новые численные методы, в которых в ходе итерации меняются целевые точки. На основе этих исследований была создана система для решения многокритериальных задач нелинейного программирования ДИСО/ПК-МКО.
