Наверх

Ф.Гилл, У.Мюррей, М.Райт, 1985 (Rus)
Практическая оптимизация

Книга американских специалистов представляет собой пособие по математическому программированию. Авторы тщательно отобрали и изложили только те алгоритмы, которые эффективны при решении практических задач. Предназначена для математиков-прикладников, научных работников, специалистов, студентов и школьников, изучающих или применяющих в своей работе (практике) оптимизационные методы


ОГЛАВЛЕНИЕ

ПРЕДИСЛОВИЕ
ГЛАВА 1. ВВЕДЕНИЕ
1.1 Постановка задачи оптимизации
1.2 Классификация оптимизационных задач
1.3 Краткий обзор содержания

ГЛАВА 2. ОСНОВЫ
2.1 Введение в теорию ошибок вычислений
   2.1.1 Измерение ошибки
   2.1.2 Представление числа в машине
   2.1.3 Ошибки округления
   2.1.4 Ошибки при выполнении арифметических операций
   2.1.5 Ошибки компенсации
   2.1.6 Точность при последовательных вычислениях
   2.1.7 Анализ ошибок для алгоритмов
   2.2 Введение в вычислительную линейную алгебру
   2.2.1 Предварительные сведения
   2.2.2 Векторные пространства
   2.2.3 Линейные преобразования
   2.2.4 Линейные уравнения
   2.2.5 Разложения матриц
   2.2.6 Многомерная геометрия
2.3 Элементы многомерного анализа
   2.3.1 Функции многих переменных; линии уровня
   2.3.2 Непрерывные функции и их производные
   2.3.3 Порядок функции
   2.3.4 Теорема Тейлора
   2.3.5 Конечно-разностная аппроксимация производных
   2.3.6 Скорости сходимости последовательностей

ГЛАВА 3. УСЛОВИЯ ОПТИМИЗАЦИИ
3.1 Определение минимума
3.2 Безусловная оптимизация
   3.2.1 Одномерный случай
   3.2.2 Многомерный случай
   3.2.3 Свойства квадратичных функций
3.3 Оптимизация при линейных ограничениях
   3.3.1 Задачи с ограничениями типа линейных равенств
   3.3.2 Задачи с ограничениями типа линейных неравенств
3.4 Оптимизация при нелинейных ограничениях
   3.4.1 Задачи с ограничениями типа нелинейных
   3.4.2 Задачи с ограничениями типа нелинейных неравенств

ГЛАВА 4. МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ
4.1 Методы для функции одной переменной
   4.1.1 Поиск нуля функции одной переменной
   4.1.2 Методы одномерной минимизации
4.2 Методы для негладких функций многих переменных
   4.2.1 Применение методов с сопоставлением значений функции
   4.2.2 Метод многогранника
   4.2.3 Составные не дифференцируемые функции
4.3 Методы для гладких функций многих переменных
   4.3.1 Модельная схема минимизации гладких функций
   4.3.2 Сходимость модельной схемы
4.4 Методы второго порядка
   4.4.1 Метод Ньютона
   4.4.2 Стратегии для знаконеопределенной матрицы Гессе
4.5 Методы первого порядка
   4.5.1 Ньютоновские методы конечно-разностной аппроксимацией
   4.5.2 Квазиньютоновские методы
4.6 Методы минимизации гладких функций без вычислений производных
   4.6.1 Конечно-разностная аппроксимация первых производных
   4.6.2 Квазиньютоновские методы без вычисления производных
4.7 Методы решения задач о наименьших квадратах
   4.7.1 Происхождение задач о наименьших квадратах; основания для использования специальных методов
   4.7.2 Метод Гауса-Ньютона
   4.7.3 Метод Левенберга-Маркарда
   4.7.4 Квазиньютоновские методы
   4.7.5 Скорректированный метод Гаусса-Ньютона
   4.7.6 Нелинейные уравнения
4.8 Методы решения задач большой размерности
   4.8.1 Дискретные методы Ньютона для функций с разреженными матрицами Гессе 
   4.8.2 Квазиньютоновские методы для функций с разреженными матрицами Гессе
   4.8.3 Методы сопряженных градиентов
   4.8.4 Квазиньютоновские методы с ограниченной памятью
   4.8.5 Методы сопряженных градиентов с улучшением обусловленности
   4.8.6 Решение ньютоновских уравнений линейным методом сопряженных градиентов

ГЛАВА 5. ЗАДАЧИ С ЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ
5.1 Методы поиска минимума при ограничениях-равенствах
   5.1.1 Принцип организации алгоритмов
   5.1.2 Расчет направления поиска
   5.1.3 Представление нуль пространства ограничений
   5.1.4 Специальные формы целевой функции
   5.1.5 Оценка множителей Лагранжа
5.2 Методы активного набора для задач с ограничениями типа линейных неравенств
   5.2.1 Модельная схема
   5.2.2 Расчет направления поиска и длины шага
   5.2.3 Интерпретация оценок множителей Лагранжа
   5.2.4 Вычисления при изменении рабочего списка
5.3 Задачи специальных типов
   5.3.1 Линейное программирование
   5.3.2 Квадратичное программирование
   5.3.3 Линейная задача о наименьших квадратах с ограничениями
5.4 Задача с малым числом ограничений общего типа
   5.4.1 Квадратичные задачи с положительно определенными матрицами Гессе
   5.4.2 Методы вторых производных для решения задач общего вида
5.5 Задачи с ограничениями специального вида
   5.5.1 Минимизация при простых ограничениях на переменные
   5.5.2 Задача со смесью простых ограничений и ограничений общего вида
5.6 Большие задачи с линейными ограничениями
   5.6.1 Методы решения больших задач линейного программирования
   5.6.2 Большие задачи с линейными ограничениями и нелинейными критериями
5.7 Поиск начальной допустимой точки
5.8 Реализация методов активного набора
   5.8.1 Определение начального рабочего списка
   5.8.2 Линейно зависимые ограничения
   5.8.3 Нулевые множители Лагранжа

ГЛАВА 6. ЗАДАЧИ С НЕЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ
6.1 Общие определения
   6.1.1 Функция выигрыша
   6.1.2 Классификация подзадач
   6.2.2 Методы штрафных и барьерных функций
6.3 Методы приведенных градиентов и проекций градиентов
   6.3.1 Общие соображения
   6.3.2 Поиск при ограничениях-равенствах
   6.3.3 Определение рабочего списка
6.4 Методы модифицированных функций Лагранжа
   6.4.1 Определение модифицированной функции Лагранжа
   6.4.2 Схема Алгоритмов с модифицированными функциями Лагранжа
   6.4.3 Вариации стратегии поиска
6.5 Методы спроектированного лагранжиана
   6.5.1 Предварительные соображения
   6.5.2 Подзадача с целевой функцией общего вида
   6.5.3 Квадратичная подзадача
   6.5.4 Стратегии для дефектных подзадач
   6.5.5 Построение активного набора
6.6 Оценки множителей Лагранжа
   6.6.1 Оценки первого порядка
   6.6.2 Оценки второго порядка
   6.6.3 Оценки множителей для ограничений-неравенств
   6.6.4 проверки состоятельности
6.7 Задачи большой размерности
   6.7.1 Использование подзадачи с линейными ограничениями
   6.7.2 Использование квадратичной подзадачи
6.8 Задачи специальных типов
   6.8.1 Специальные задачи минимизации негладких функций
   6.8.2 Специальные задачи с ограничениями

ГЛАВА 7. МОДЕЛИРОВАНИЕ
7.1 Введение
7.2 Классификация оптимизационных задач
7.3 Исключение необязательных разрывностей
   7.3.1 Роль точности вычисления функций модели
   7.3.2 Аппроксимация по рядам и таблицам
   7.3.3 Определение функций подзадачей
7.4 Преобразование задач
   7.4.1 Упрощение или исключение ограничений
   7.4.2 Задачи с функциональными переменными
7.5 Масштабирование
   7.5.1 Масштабирование заменой переменных
   7.5.2 Масштабирование в нелинейных задачах о наименьших квадратах
7.6 Постановка ограничений
   7.6.1 Вырождение
   7.6.2 Использование ограничений с допусками
7.7 Задачи с дискретными и целочисленными переменными
   7.7.1 Псевдодискретные переменные
   7.7.2 Целочисленные переменные

ГЛАВА 8. ПРАКТИЧЕСКИЕ ВОПРОСЫ
8.1 Применение библиотечных программ
   8.1.1 Выбор метода
   8.1.2 Роль пользователя
   8.1.3 Выбор параметров пользователем
   8.1.4 Ошибки в программах пользователя
   8.1.5 Работа с ограниченным математическим обеспечением
8.2 Свойства численного решения
   8.2.1 Что такое правильный ответ?
   8.2.2 Предельная точность решения
   8.2.3 Критерии останова
8.3 Анализ результатов счета
   8.3.1 Оценка пригодности численного решения
   8.3.2 Другие способы подтверждения оптимальности
8.4 Что может не получаться (и как тогда поступать)?
   8.4.1 Переполнение при подсчете функций задачи
   8.4.2 Недостаточное уменьшение функции выигрыша
   8.4.3 Устойчиво медленный прогресс
   8.4.4 Выполнение максимального числа итераций или обращений к процедуре вычисления целевой сходимости
   8.4.5 Отсутствие ожидаемой скорости сходимости
   8.4.6 Неудачное направление поиска