|
ОГЛАВЛЕНИЕ
Предисловие редактора перевода................... 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.5. Конечно-разностная аппроксимация производных..... 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. Задачи с линейными ограничениями............. 218
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.1.1. Функция выигрыша................... 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.1. Выбор метода...................... 385
8.1.2. Роль пользователя................... 392
8.1.3. Выбор параметров пользователем............ 394
8.1.4. Ошибки в программах пользователя............ 400
8.1.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
|