Учебное пособие. - Томск: Томский межвузовский центр дистанционного
образования, 2002. - 192 с.
Содержание.
Введение.
Исторический путь становления различных методов оптимизации. Связь с теорией автоматического управления.
Основные понятия и определения.
Анализ экстремальных задач.
Постановка и классификация задач оптимизации.
Необходимые и достаточные условия существования экстремума.
Характеристики алгоритмов оптимизации.
Методы поиска нулей функции.
Критерии останова.
Численная аппроксимация градиентов.
Классы алгоритмов оптимизации.
Методы минимизации функций.
Одномерный поиск.
Методы исключения интервалов.
Полиномиальная аппроксимация и методы точечного оценивания.
Квадратичная аппроксимация.
Методы с использованием производных.
Метод поиска с использованием кубичной аппроксимации.
Сравнение методов.
Функции нескольких переменных (нелинейная оптимизация без ограничений).
Методы прямого поиска.
Симплексный метод.
Метод Хука-Дживса.
Метод сопряженных направлений Пауэла.
Градиентные методы.
Метод наискорейшего спуска (метод Коши).
Метод Ньютона.
Модифицированный метод Ньютона.
Метод Марквардта.
Метод сопряженных градиентов.
Квазиньютоновские методы (методы с переменной метрикой).
Численная аппроксимация градиентов.
Сравнение методов безусловной оптимизации.
Условная оптимизация.
Линейное программирование.
Разработка моделей линейного программирования.
Формы записи задач линейного программирования.
Графическое решение задач линейного программирования с двумя переменными.
Основы симплекс-метода.
Двойственность (в задачах линейного программирования).
Нелинейное программирование.
Прямые методы.
Задачи с ограничениями в виде равенств.
Необходимые и достаточные условия оптимальности задач с ограничениями.
Методы штрафов.
Понятие штрафных функций. Основные типы штрафов.
Алгоритмы.
Методы линеаризации для задач условной оптимизации.
Методы выбора направления, основанные на линеаризации.
Случай линейных ограничений. Алгоритм Франка-Вульфа.
Случай нелинейных ограничений. Метод допустимых направлений Зойтендейка.
Метод условного градиента.
Метод проекции градиента.
Сепарабельное программирование.
Квадратичное программирование.
Условие Куна-Таккера для задач квадратичного программирования.
Задача о дополнительности.
Алгоритм решения задачи квадратичного программирования Мицеля-Хващевского.
Методы квадратичной аппроксимации.
Теория двойственности.
Геометрическая интерпретация двойственной по Лагранжу задачи.
Теоремы двойственности и седловые точки.
Критерий седловой точки.
Связь между критерием седловой точки и условием оптимальности Куна-Таккера.
Свойства двойственной функции Лагранжа.
Решение двойственной по Лагранжу задачи.
Задачи линейного и квадратичного программирования.
Список литературы.
Введение.
Исторический путь становления различных методов оптимизации. Связь с теорией автоматического управления.
Основные понятия и определения.
Анализ экстремальных задач.
Постановка и классификация задач оптимизации.
Необходимые и достаточные условия существования экстремума.
Характеристики алгоритмов оптимизации.
Методы поиска нулей функции.
Критерии останова.
Численная аппроксимация градиентов.
Классы алгоритмов оптимизации.
Методы минимизации функций.
Одномерный поиск.
Методы исключения интервалов.
Полиномиальная аппроксимация и методы точечного оценивания.
Квадратичная аппроксимация.
Методы с использованием производных.
Метод поиска с использованием кубичной аппроксимации.
Сравнение методов.
Функции нескольких переменных (нелинейная оптимизация без ограничений).
Методы прямого поиска.
Симплексный метод.
Метод Хука-Дживса.
Метод сопряженных направлений Пауэла.
Градиентные методы.
Метод наискорейшего спуска (метод Коши).
Метод Ньютона.
Модифицированный метод Ньютона.
Метод Марквардта.
Метод сопряженных градиентов.
Квазиньютоновские методы (методы с переменной метрикой).
Численная аппроксимация градиентов.
Сравнение методов безусловной оптимизации.
Условная оптимизация.
Линейное программирование.
Разработка моделей линейного программирования.
Формы записи задач линейного программирования.
Графическое решение задач линейного программирования с двумя переменными.
Основы симплекс-метода.
Двойственность (в задачах линейного программирования).
Нелинейное программирование.
Прямые методы.
Задачи с ограничениями в виде равенств.
Необходимые и достаточные условия оптимальности задач с ограничениями.
Методы штрафов.
Понятие штрафных функций. Основные типы штрафов.
Алгоритмы.
Методы линеаризации для задач условной оптимизации.
Методы выбора направления, основанные на линеаризации.
Случай линейных ограничений. Алгоритм Франка-Вульфа.
Случай нелинейных ограничений. Метод допустимых направлений Зойтендейка.
Метод условного градиента.
Метод проекции градиента.
Сепарабельное программирование.
Квадратичное программирование.
Условие Куна-Таккера для задач квадратичного программирования.
Задача о дополнительности.
Алгоритм решения задачи квадратичного программирования Мицеля-Хващевского.
Методы квадратичной аппроксимации.
Теория двойственности.
Геометрическая интерпретация двойственной по Лагранжу задачи.
Теоремы двойственности и седловые точки.
Критерий седловой точки.
Связь между критерием седловой точки и условием оптимальности Куна-Таккера.
Свойства двойственной функции Лагранжа.
Решение двойственной по Лагранжу задачи.
Задачи линейного и квадратичного программирования.
Список литературы.