Книга известного американского математика профессора Э. Полака занимает особое место в огромном потоке литературы, посвященной методам оптимизации. Алгоритм, как это справедливо заметил автор, — некоторое изобретение, и, как всякое изобретение, он проходит большой путь, прежде чем превратится в надежную конструкцию и начнет служить людям. Исходная идея, которая рождается у автора алгоритма, никогда в «чистом виде» не может быть реализована.
Автор вводит понятия «принципиального» и «реализуемого» алгоритмов. При описании идеи «принципиального» алгоритма обычно не заботятся о том, чтобы каждая итерация требовала конечного (и, как правило, относительно небольшого) количества машинных операций. Например, при перечислении процедур «принципиального» алгоритма может быть и такая: «найти нуль функции /(я)», хотя сама эта процедура может оказаться весьма трудоемкой. Описание «реализуемого» алгоритма должно содержать указание о необходимой точности выполнения каждой из итераций. Введение подобных понятий позволило автору построить очень удобную и полезную инфраструктуру книги и проследить последовательную эволюцию алгоритма от его исходной «принципиальной» формулировки до «реализуемого» варианта, который, вообще говоря, жестко связан с природой решаемой задачи.
В основе алгоритмов оптимизации не так уже много идей и, значит, существует лишь несколько исходных моделей алгоритмов и их принципиальных схем. Это позволяет провести довольно простую классификацию и сделать попытку построения некоторой «теории алгоритмов оптимизации». Книга профессора Полака, собственно говоря, и является попыткой построения такой теории алгоритмов с единым языком и единой схемой анализа основных «принципиальных» алгоритмов и их «реализуемых» вариантов.
В центре внимания монографии, как и большинства книг, посвященных методам оптимизации, — проблема сходимости. Несмотря на то что автор очень четко описывает схемы алгоритмов, давая почти блок-схемы необходимых расчетов, больше ;
ОГЛАВЛЕНИЕ
Предисловие к русскому изданию............... 5
Из предисловия автора ................... 8
К сведению читателя........... . ......... 11
Обозначения и символы........-'............ 12
1. Обозначения . ...................12
2. Символы ......................13
1. Предварительные результаты................15
1.1. Задачи нелинейного программирования и оптимального управления ....................... 15
1.2. Условия оптимальности................ 21
1.3. Модели и условия сходимости численных методов...... 27
2. Минимизация без ограничений................46
2.1. Градиентные и квазиньютоновские методы в Rn...... 46
2.2 Связь с вычислением производных............ 60
2.3. Методы сопряженных градиентов в Rn.......... 65
2.4. Задачи дискретного оптимального управления без ограничений 88 2 5. Задачи непрерывного оптимального управления без ограничений 93
3. Ограничения типа равенств: задачи о поиске корней и краевые задачи 102
3.1 Нули функции и задачи с ограничениями типа равенств в R™ 102
3.2 Краевые задачи и оптимальное управление дискретными процессами .......................'06
3.3. Краевые задачи и непрерывное оптимальное управление . . . 128
4. Ограничения типа равенств и неравенств...........154
4.1. Методы штрафных функций..............154
4.2. Методы центров...................183
4.3. Методы возможных направлений ............193
4.4. Методы возможных направлений второго порядка......217
4.5. Методы проекции градиента..............222
5. Выпуклые задачи оптимального управления..........247
5.1. Сведение к нелинейному программированию....... 247
5.2. Двойственный алгоритм декомпозиции..........259
5.3. Алгоритм декомпозиции прямого типа..........275
6. Скорость сходимости...................285
6.1. Линейная сходимость......,...........Я85
6.2. Сверхлинейная сходимость: квазиньютоновские методы .... 234
6.3. Сверхлинейная сходимость: методы сопряженных градиентов . . 303
6.4. Сверхлинейная сходимость: алгоритм с переменной метрикой 314
Приложение А. Дальнейшие модели для вычислительных методов . . . 329
АЛ. Модель для реализации некоторых принципиальных алгоритмов
оптимального управления ............... 329
А.2. Модель без обратной связи для реализации принципиальных алгоритмов ......................334
Приложение В. Свойства непрерывных функций..........338
8.1. Разложения непрерывных функций..... .....338
8.2. Выпуклые функции..................339
8.3. Ряд вспомогательных результатов............341
Приложение С. Руководство по реализации алгоритмов.......344
С.1. Общие рассуждения........... .....344
С.2. Градиентные методы.................346
С.З. Квазиньютоновские методы..............343
С.4. Алгоритмы сопряженных градиентов........ 351
С.5. Методы штрафных функций..............354
С.6. Методы возможных направлений с линейным поиском .... 358 J С.7. Методы возможных направлений с квадратичным поиском . . 362
' Список литературы............... .....364
Именной указатель.....................370
Предметный указатель....................372
Цена: 300руб.
