Глобальная оптимизация с помощью методов интервального анализа

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


Оглавление
Предисловие рецензента книги
Предисловие авторов
Перечень рисунков
Перечень таблиц
Список принятых сокращений и обозначений

ГЛАВА 1. Введение
1.1. Обзор
1.2. Предыстория возникновения интервального анализа
1.3. Круг вопросов настоящей книги
1.4. Преимущества и недостатки интервальных вычислений
1.4.1. Пример Румпа
1.4.2. Практические примеры
1.4.3. Простота использования
1.4.4. Показатели эффективности работы
1.4.5. Преимущества интервального анализа
1.5. Будущее интервальных вычислений
ГЛАВА 2. Интервалы и интервальная арифметика
2.1. Интервалы
2.2. Обозначения
2.3. Арифметика конечных интервалов
2.4. Зависимость интервалов
2.4.1. Арифметические операции между зависимыми интервалами
2.5. Расширенная интервальная арифметика
ГЛАВА 3. Функции от интервалов
3.1. Вещественные функции от интервалов
3.2. Интервальные функции
3.3. Формы интервальных функций
3.4. Дробление интервалов
3.5. Анализ граничных точек
3.6. Монотонные функции
3.7. Практическое оценивание интервальных функций
3.8. Грубые и точные функции

ГЛАВА 4. Замкнутые интервальные системы
4.1. Введение
4.2. Преимущества замкнутой системы
4.2.1. Свойство обобщённости
4.2.2. Скорость работы с системой и ширина интервалов
4.3. Теоретико-множественное обоснование замкнутых интервальных систем
4.4. Ограничение на локализующее множество
4.4.1. Ограничение на конечномерное интервальное локализующее множество
4.4.2. Ограничение на расширенное локализующее множество
4.5. Расширенное локализующее множество
4.5.1. История вопроса
4.5.2. Простой пример: деление 1/0
4.5.3. Обозначение локализующего множества
4.5.4. Локализующее множество результата деления 1/0
4.6. Арифметика над расширенным множеством вещественных чисел
4.6.1. Пустые множества и интервалы
4.6.2. Эквивалентные выражения локализующих множеств
4.7. Замкнутые интервальные системы
4.7.1. Операции алгоритмов с замкнутыми интервалами
4.8. Расширенная основная теорема
4.8.1. Локализующие множества и топологические замыкания
4.8.2. Многозначные выражения
4.8.3. Изотонность локализующих множеств по включению
4.8.4. Основная теорема интервальной арифметики
4.8.5. Непрерывность
4.9. Обозначения векторов и матриц
4.10. Заключение
ГЛАВА 5. Линейные уравнения
5.1. Определения
5.2. Введение
5.3. Множество решений
5.4. Метод Гаусса
5.5. Случаи аварийной остановки метода Гаусса
5.6. Предобуславливание
5.7. Метод Гаусса-Зейделя
5.8. Процедура Хансена-Блика-Рона
5.8.1. Теоретический алгоритм
5.8.2. Практические процедуры
5.9. Комбинирование метода Гаусса-Зейделя и процедуры Хансена-Блика-Рона
5.10. Оболочка множества решений системы Ах = Ь
5.11. Специальная предобуславливающая матрица
5.12. Переопределенные системы

ГЛАВА 6. Неравенства
6.1. Введение
6.2. Одиночное неравенство
6.3. Системы неравенств
6.4. Упорядочение неравенств
6.5. Вспомогательный выбор ведущих элементов
6.6. Перестановки столбцов
6.7. Предобуславливающая матрица
6.8. Решение неравенств

ГЛАВА 7. Разложения на основе наклонов и рядов Тейлора
7.1. Введение
7.2. Оценивание остаточного члена в разложении на основе рядов Тейлора
7.3. Многомерный случай
7.4. Якобиан и гессиан
7.5. Автоматическое дифференцирование
7.6. Уточнённые оценки, использующие тейлоровские разложения
7.7. Разложения, использующие наклоны
7.8. Наклоны для иррациональных функций
7.9. Многомерные наклоны
7.10. Наклоны высших порядков
7.11. Разложения негладких функций на основе наклонов
7.12. Автоматическое оценивание наклонов
7.13. Эквивалентные разложения

ГЛАВА 8. Квадратные интервальные уравнения и неравенства
8.1. Введение
8.2. Процедура
8.3. Структура алгоритма

ГЛАВА 9. Нелинейные уравнения одной переменной
9.1. Введение
9.2. Интервальный метод Ньютона
9.3. Процедура в случае, когда интервал f'(X) производной не содержит нуль
9.4. Критерий остановки
9.5. Структура алгоритма
9.6. Свойства алгоритма
9.7. Численный пример
9.8. Интервальный метод Ньютона на основе наклонов
9.9. Пример, использующий метод на основе наклонов
9.10. Задачи с возмущениями

ГЛАВА 10. Анализ совместности
10.1. Введение
10.2. Совместность по брусу
10.3. Совместность по значениям
10.4. Анализ совместности по значениям
10.5. Реализация анализа совместности по значениям
10.6. Сходимость
10.7. Сходимость в интервальном случае
10.8. Дробление бруса
10.9. Многомерный случай
10.10. Проверка несуществования решения
10.11. Линейные комбинации функций
10.12. Доказательство существования решения
10.13. Сравнение анализа совместности по брусу и анализа совместности по значениям
10.14. Уточнение границ области
10.15. Использование дискриминантов
10.16. Нелинейные уравнения одной переменной

ГЛАВА 11. Системы нелинейных уравнений
11.1. Введение
11.2. Вывод интервальных методов Ньютона
11.3. Варианты метода
11.4. Внутренняя итерация
11.4.1. Пост-ньютоновская внутренняя итерация
11.5. Критерии остановки процедуры
11.6. Процесс завершения процедуры
11.7. Скорость процесса
11.8. Дробление бруса
11.9. Аналитическое предобуславливание
11.9.1. Альтернативный метод
11.10. Исходный брус
11.11. Проверка линеаризации
11.12. Структура алгоритма
11.13. Обсуждение алгоритма
11.14. Один шаг метода Ньютона
11.15. Свойства интервальных методов Ньютона
11.16. Численный пример
11.17. Задачи с возмущениями и анализ чувствительности
11.18. Переопределенные системы
ГЛАВА 12. Безусловная оптимизация
12.1. Введение
12.2. Общая структура алгоритма
12.3. Исходный брус
12.4. Использование градиента
12.5. Ограничение сверху на глобальный минимум
12.5.1. Первый метод
12.5.2. Второй метод
12.5.3. Третий метод
12.5.4. Четвертый метод
12.5.5. Пример
12.6. Обновление органичсиия сверху

12.7. Выпуклость функции
12.8. Использование метода Ньютона
12.9. Остановка алгоритма
12.10. Ограничения на минимум
12.11. Список брусов
12.12. Выбор бруса для обработки
12.13. Дробление бруса
12.14. Структура алгоритма
12.15. Результаты работы алгоритма
12.16. Обсуждение алгоритма
12.17. Численный пример
12.18. Случай нескольких минимумов
12.19. Задачи с недифференцируемыми функциями
12.20. Нахождение всех стационарных точек

ГЛАВА 13. Оптимизация при наличии ограничений
13.1. Введение
13.2. Условия Джона (Фритца Джона)
13.3. Нормирование множителей Лагранжа
13.4. Использование ограничений
13.5. Решение условий Джона
13.6. Ограничение множителей Лагранжа
13.7. Первый численный пример
13.8. Второй численный пример
13.9. Использование совместности

ГЛАВА 14. Оптимизация с ограничениями в виде неравенств
14.1. Введение
14.2. Условия Джона
14.3. Ограничение сверху на минимум
14.4. Линейный поиск
14.5. Строго допустимые решения
14.6. Использование ограничений
14.7. Использование тейлоровских разложений
14.8. Структура алгоритма
14.9. Результаты работы алгоритма
14.10. Обсуждение алгоритма
14.11. Отделение границы
14.12. Внешняя аппроксимация бруса
14.13. Недифференцируемые функции

ГЛАВА 15. Оптимизация с ограничениями в виде равенств
15.1. Введение
15.2. Условия Джона
15.3. Ограничения на минимум
15.4. Использование ограничений для оценивания минимума
15.4.1. Первый метод
15.4.2. Второй метод
15.5. Выбор переменных
15.6. Удовлетворение основного предположения
15.7. Численный пример
15.8. Использование ограничения сверху
15.9. Использование ограничений
15.10. Информация о решении
15.11. Использование условий Джона
15.12. Структура алгоритма
15.13. Результаты работы алгоритма
15.14. Обсуждение алгоритма
15.15. Недифференцируемые функции

ГЛАВА 16. Общий случай задачи оптимизации
16.1. Введение
16.2. Линейные системы с ограничениями в виде неравенств и равенств
16.3. Существование допустимой точки
16.3.1. Случай 1
16.3.2. Случай 2
16.3.3. Случай 3
16.4. Структура алгоритма

ГЛАВА 17. Задачи с возмущениями и анализ чувствительности
17.1. Введение
17.2. Основные алгоритмы
17.3. Допуски
17.4. Несвязные множества решений
17.5. Точные ограничения в задачах оптимизации с возмущениями
17.6. Обоснование допущения 17.5.1
17.7. Первый численный пример
17.8. Второй численный пример
17.9. Третий численный пример

17.10. Ограничение сверху
17.11. Уточнённые ограничения для систем нелинейных уравнений

ГЛАВА 18. Другие случаи задач оптимизации
18.1. Недифференцируемые функции
18.2. Целочисленные и смешанные целочисленные задачи
Литература
Дополнительная литература к русскому изданию
Предметный указатель