Читатель знаком с Ф. Гиллом и У. Мюрреем не только по их шогочисленным статьям в научных журналах. Они редактировали борник трудов конференции по методам условной оптимизации, [роведенной Национальной физической лабораторией (Великобри-ания, Тэддингтон) в январе 1974 года. Сборник был переведен на >усский язык °. Это был обзор тогдашнего состояния численных ме-рдов отыскания экстремума функции при ограничениях. Он имел рткую прикладную направленность: концентрировал внимание ргсателя на трудностях, возникающих при практическом решении адач, и способах преодоления этих трудностей.
Предлагаемая монография Ф. Гилла, У. Мюррея и М. Райт (Практическая оптимизация» имеет столь же острую практическую аправленность. Как и упомянутый сборник статей, она отражает ^временное — теперь уже спустя десятилетие — состояние мето-|>в и техники решения задач оптимизации. Общая картина пред-jteer перед читателем преломленной через призму опыта и, если Годно, научных вкусов авторов — больших знатоков своего дела. ko придает изложению и ясность, и логическую стройность, и ори-Йнальность. Правда, отдельные детали получились не совсем удач-рвди и потребовали от переводчика дополнительных усилий, чтобы |чно передать существо дела,
ff Авторы старались написать книгу так, чтобы даже не слишком уготовленный читатель мог понять ее, не обращаясь к учебникам, ее чтения достаточно знать только основы математического шиза и линейной алгебры. Изложение начинается со сведений япособах представления чисел в ЭВМ, о возникающих при этом •решностях и о погрешностях, сопутствующих вычислениям, казано, как ошибки могут влиять на результаты работы алго-B. Так, с самого начала внимание читателя привлекается к штическим вычислениям. Затем сообщаются нужные сведения линейной алгебры и выводятся необходимые и достаточные усло-| минимума функции как для случая, когда на независимые пере-ише не наложено никаких условий, так и для случая, когда ус-ря наложены.
ОГЛАВЛЕНИЕ
Предисловие редактора перевода ................... 5
Предисловие............................. 7
Глава 1. Введение.......................... 9
1.1. Постановка задачи оптимизации ............... 9
1.2. Классификация оптимизационных задач........... 12
1.3. Краткий обзор содержания................. 14
Глава 2. Основы........................... 16
2.1. Введение в теорию ошибок вычислений............ 16
2.1.1. Измерение ошибки.................... 16
2.1.2. Представление числа в машине.............. 17
2.1.3. Ошибки округления................... 19
2.1.4. Ошибки при выполнении арифметических операций .... 21
2.1.5. Ошибки компенсации................... 23
2.1.6. Точность при последовательных вычислениях....... 24
2.1.7. Анализ ошибок для алгоритмов............. 25
2.2. Введение в вычислительную линейную алгебру........ 26
2.2.1. Предварительные сведения................ 26
2.2.2. Векторные пространства........,........ 33
2.2.3. Линейные преобразования................ 38
2.2.4. Линейные уравнения................... 41
2.2.5. Разложения матриц................... 50
2.2.6. Многомерная геометрия................. 64
2.3. Элементы многомерного анализа............... 66
2.3.1. Функции многих переменных; линии-уровня....... 66
2.3.2. Непрерывные функции и их производные......... 66
2.3.3. Порядок функции.....'..'.•............ 72
2.3.4. Теорема Тейлора.................... 73
2.3.6. Конечно-разностная аппроксимация производных ..... 74
2.3.6. Скорости сходимости последовательностей........ 78
Глава 3. Условия оптимальности................... 81
3.1. Определение минимума.................... 81
3.2. Безусловная оптимизация.................. 84
3.2.1. Одномерный случай................... 84
3.2.2. Многомерный случай................... 86
3.2.3. Свойства квадратичных функций............. 88
3.3. Оптимизация при линейных ограничениях.......... 90
3.3.1. Задачи с ограничениями типа линейных равенств..... 91
3.3.2. Задачи с ограничениями типа линейных неравенств .... 95
3.4. Оптимизация при нелинейных ограничениях......... 104
3.4.1. Задачи с ограничениями типа нелинейных........ 104
3.4.2. Задачи с ограничениями типа нелинейных неравенств . . . 109
Глава 4. Методы безусловной минимизации.............. 111
4.1. Методы для функции одной переменной............ 111
4.1.1. Поиск нуля функции одной переменной.......... 111
4.1.2. Методы одномерной минимизации............. 118
4.2. Методы для негладких функций многих переменных ..... 124
4.2.1. Применение методов с сопоставлением значений функции . . 124
4.2.2. Метод многогранника....., . . ,......... 125
4.2.3. Составные недифференцируемые функции......... 128
4.3. Методы для гладких функций многих переменных...... 132
4.3.1. Модельная схема минимизации гладких функций..... 132
4.3.2. Сходимость модельной схемы................ 133
4.4. Методы второго порядка................... 141
4.4.1. Метод Ньютона..................... 141
4.4.2. Стратегии для знаконеопределенной матрицы Гессе .... 144
4.5. Методы первого порядка................... 158
4.5.1. Ньютоновские методы с конечно-разностной аппроксимацией 158
.4.5.2. Квазиньютоновские методы........'....... 160
4.6. Методы минимизации гладких функций без вычислений производных............................... 174
4.6.1. Конечно-разностная аппроксимация первых производных . 175
4.6.2. Квазиньютоновские методы без вычисления производных . 180
4.7. Методы решения задач о наименьших квадратах ........ 183
4.7.1. Происхождение задач о наименьших квадратах; основания
для использования специальных методов . ........... 183
4.7.2. Метод Гаусса — Ньютона ... ............. 184
4.7.3. Метод Левенберга — Маркардта............. 188
4.7.4. Квазиньютоновские методы................ 189
4.7.5. Скорректированный метод Гаусса — Ньютона....... 190
4.7.6. Нелинейные уравнения.................. 193
4.8. Методы решения задач большой размерности......... 195
4.8.1. Дискретные методы Ньютона для функций с разреженными матрицами Гессе........................ 196
4.8.2. Квазиньютоновские методы для функций с разреженными матрицами Гессе ........................ 198
4.8.3. Методы сопряженных градиентов............ 200
4.8.4. Квазиньютоновские методы с ограниченной памятью .... 208
4.8.5. Методы сопряженных градиентов с улучшением обусловленности ............................. 209
4.8.6. Решение ньютоновских уравнений линейным методом сопряженных градиентов.............<........ 212
Глава 5. Задачи с линейными ограничениями............. 216
5.1. Методы поиска минимума при ограничениях-равенствах . . . 216
5.1.1. Принцип организации алгоритмов............ 217
5.1.2. Расчет направления поиска............... 220
5.1.3. Представление нуль-пространства ограничений...... 225
5.1.4. Специальные формы целевой функции........... 228
5.1.5. Оценки множителей Лагранжа.............. 229
5.2. Методы активного набора для задач с ограничениями типа линейных неравенств........................ 233
5.2.1. Модельная схема.................... 235
5.2.2. Расчет направления поиска и длины шага........ 236
5.2.3. Интерпретация оценок множителей Лагранжа....... 238
5.2.4. Вычисления при изменении рабочего списка....... 240
5.3. Задачи специальных типов................. 246
5.3.1. Линейное программирование............... 246
5.3.2. Квадратичное программирование............. 248
5.3.3. Линейная задача о наименьших квадратах с ограничениями 252
5.4. Задачи с малым числом ограничений общего вида....... 256
5.4.1. Квадратичные задачи с положительно определенными матрицами Гессе.......................... 256
5.4.2. Методы вторых производных для решения задач общего вида 258
5.5. Задачи с ограничениями специального вида ......... 261
5.5.1. Минимизация при простых ограничениях на переменные . 261
5.5.2. Задача со смесью простых ограничений и ограничений общего
вида.............................. 264
5.6. Большие задачи с линейными ограничениями ........ 266
5.6.1. Методы решения больших задач линейного программирования .......................... .... 266
5.6.2. Большие задачи с линейными ограничениями и нелинейными критериями ... ..................... 270
5.7. Поиск "начальной допустимой точки............. 278
5.8. Реализация методов активного набора............ 280
5.8.1. Определение начального рабочего списка......... 280
5.8.2. Линейно зависимые ограничения............. 282
5.8.3. Нулевые множители Лагранжа............. 283
Глава 6. Задачи с нелинейными ограничениями............ 286
6.1. Общие определения..................... 287
6.ГЛ. Функция выигрыша................... 287
6.1.2. Классификация подзадач................. 288
6.2. Методы штрафных и барьерных функций.......... 289
6.2.1. Методы гладких штрафных и барьерных функций..... 289
6.2.2. Методы негладких штрафных функций.......... 298
6.3. Методы приведенных градиентов и проекций градиентов . . . 304
6.3.1. Общие соображения.................... 304
6.3.2. Поиск при ограничениях-равенствах........... 305
6.3.3. Определение рабочего списка............... 309
6.4. Методы модифицированных функций Лагранжа......., 310
6.4.1. Определение модифицированной функции Лагранжа .... 311
6.4.2. Схема алгоритмов с модифицированными функциями Лагранжа.............................. 314
6.4.3. Вариации стратегии поиска............... 317
6.5. Методы спроектированного лагранжиана........... 320
6.5.1. Предварительные соображения.............. 320
6.5.2. Подзадача с целевой функцией общего вида....... 322
6.5.3. Квадратичная подзадача................. 325
6.5.4. Стратегии для дефектных подзадач............ 332
6.5.5. Построение активного набора.............. 333
6.6. Оценки множителей Лагранжа............... 338
6.6.1. Оценки первого порядка................. 339
6.6.2. Оценки второго порядка................ 340
6.6.3. Оценки множителей для ограничений-неравенств..... 342
6.6.4. Проверки состоятельности................ 343
6.7. Задачи большой размерности................ 344
6.7.1. Использование подзадачи с линейными ограничениями . . 344
6.7.2. Использование квадратичной подзадачи.......... 346
6.8. Задачи специальных типов .................. 351
6.8.1. Специальные задачи минимизации негладких функций . . 351
6.8.2. Специальные задачи с ограничениями........... 352
Глава 7. Моделирование....................... 356
7.1. Введение.......................... 356
7.2. Классификация оптимизационных задач........... 357
7.3. Исключение необязательных разрывностей.......... 359
7.3.1. Роль точности вычисления функций модели ...... 359
7.3.2. Аппроксимация по рядам и таблицам .......... 361
7.3.3. Определение функций подзадачей . ._.......... 362
7.4. Преобразования задач..........'........... 364
7.4.1. Упрощение или исключение ограничений......... 364
7.4.2. Задачи с функциональными переменными........ 370
7.5. Масштабирование...................... 371
7.5.1. Масштабирование заменой переменных ........... 371
7.5.2. Масштабирование в нелинейных задачах о наименьших квадратах........................... 373
7.6. Постановка ограничений . . . . ,............. 375
7.6.1. Вырождение..............,....... 375
7.6.2. Использование ограничении с допусками........ 376
7.7. Задачи с дискретными и целочисленными переменными . . . 380
7.7.1. Псевдодискретные переменные............. 380
7.7.2. Целочисленные переменные............... 382
Глава 8. Практические вопросы.................... 385
8.1. Применение библиотечных программ . ......... . . . 385
8. .1. Выбор метода..................... . 385
8. .2. Роль пользователя................... 392
8. .3. Выбор параметров пользователем............ 394
8. .4. Ошибки в программах пользователя............ 400
8. .5. Работа с ограниченным математическим обеспечением . . . 403
8.2. Свойства численного решения . ............... 406
8.2.1. Что такое правильный ответ? ............. . 406
8.2.2. Предельная точность решения.............. 407
8.2.3. Критерии останова ... . , ............... 412
8.3. Анализ результатов счета.................. 421
8.3.1. Оценка пригодности численного решения......... 421
8.3.2. Другие способы подтверждения оптимальности...... 427
8.3.3. Анализ чувствительности................ 429
8.4. Что может не получаться (и как тогда поступать)....... 433
8.4.1. Переполнение при подсчете функций задачи....... 433
8.4.2. Недостаточное уменьшение функции выигрыша...... 434
8.4.3. Устойчиво медленный прогресс.............. 438
8.4.4. Выполнение максимального числа итераций или обращений
к процедуре вычисления целевой функции.........'. . 440
8.4.5. Отсутствие ожидаемой скорости сходимости........ 440
8.4.6. Неудачное направление поиска............. 441
8.5. Оценка точности вычисления функций задачи ........ 442
8.5.1. Роль точности...................... 442
8.5.2. Оценивание точности................... 445
8.5.3. Переоценивание точности................ 451
8.6. Выбор конечных разностей................. 452
8.6.1. Ошибки конечно-разностных приближений; хорошо отмасшта-бированные функции...................... 452
8.6.2, Процедура автоматического оценивания конечно-разностных интервалов..........~................ 455
8.7. Подробнее о масштабировании............... 461
8.7.1. Масштабирование заменой переменных.......... 461
8.7.2. Масштабирование значений целевой функции....... 467
8.7.3. Масштабирование ограничений ...........- . . 468
Вопросы и ответы.......................... 472
Библиография...............«............ 478
Цена: 600руб.
