- •Глава 6. Постановки задачи нелинейного программирования (знп) и основные определения…………………………...3
- •Глава 7. Задача одномерной оптимизации…………………………………….13
- •Глава 8. Графический метод решения знп…………………………………...33
- •Глава 10. Выпуклое программирование……………………………………....62
- •Глава 11. Квадратичное программирование…………………………………74
- •Глава 12. Задача безусловной оптимизации (збо)…………………………………………………………………..81
- •Глава 13. Задача условной оптимизации (зуо)……………………….……127
- •Глава 6.
- •6.1. Задача нелинейного программирования (знп) и ее постановки.
- •6.2. Основные определения.
- •6.3. Классификация знп.
- •6.4. Классическая оптимизация.
- •Глава 7. Методы одномерной оптимизации
- •Постановка задачи. Основные понятия
- •7.2. Поиск отрезка, содержащего точку максимума Алгоритм Свенна
- •Методы нулевого порядка.
- •Дихотомический поиск (метод деления отрезка пополам)
- •Метод золотого сечения
- •Метод дск-Пауэлла
- •7.4. Методы первого порядка.
- •Метод средней точки
- •Метод хорд (секущих)
- •Метод кубической аппроксимации
- •7.5. Методы второго порядка. Метод Ньютона-Рафсона
- •Итерация 1
- •Глава 8. Графический метод решения знп.
- •8.1. Алгоритм графического метода решения знп
- •8.2. Решение примеров.
- •Выпуклые и вогнутые функции
- •9.1. Определения
- •9.2. Свойства вогнутых (выпуклых) функций
- •9.3. Критерии вогнутости (выпуклости) гладких функций
- •9.4. Экстремальные свойства вогнутых (выпуклых) функций
- •9.5. Сильно вогнутые (выпуклые) функции
- •9.5.1. Определение. Примеры
- •9.5.2. Свойства сильно вогнутых (выпуклых) функций
- •9.5.3. Критерии сильной вогнутости (выпуклости)
- •9.5.4. Экстремальные свойства сильно вогнутых (выпуклых) функций
- •Глава 10. Выпуклое программирование
- •10.1. Постановка задачи
- •10.2. Функция Лагранжа. Седловая точка функции Лагранжа, условия ее существования Определение 10.1. Функция , (10.10)
- •10.3. Достаточные условия оптимальности
- •10.4. Условия регулярности выпуклого множества
- •10.5. Теорема Куна-Таккера. Общий случай
- •10.6. Теорема Куна-Таккера. Случай линейных ограничений
- •Глава 11. Квадратичное програмирование.
- •11.1. Постановка задачи квадратичного программирования (зкп)
- •11.2. Применение теории Куна-Таккера к решению зкп.
- •11.3. Решение задач.
- •Глава 12. Методы безусловной оптимизации
- •12.1. Постановка задачи
- •Алгоритм метода спуска
- •. Методы нулевого порядка (прямого поиска)
- •Метод Хука-Дживса
- •Алгоритм метода Хука-Дживса, использующий одномерный поиск
- •Метод покоординатного спуска
- •Первый вариант
- •Второй вариант
- •Методы первого и второго порядков
- •Градиентные методы. Метод скорейшего спуска – метод Коши
- •Метод Ньютона
- •Модифицированный метод Ньютона
- •Методы, использующие сопряженные направления
- •Определение сопряженных направлений
- •Оптимизация квадратичной функции. Конечная сходимость алгоритмов, использующих сопряженные направления
- •12.4.4. Метод Дэвидона-Флетчера-Пауэлла Шаг 1.Метод Дэвидона-Флетчера-Пауэлла (дфп) принадлежит к классу квазиньютоновских методов, в которых направление поиска задаётся в виде
- •Алгоритм метода дфп
- •Итерация 1
- •Шаг 2. Вычислим , тогда .
- •Шаг 2. Вычислим , тогда .
- •12.4.5. Метод сопряжённых градиентов Флетчера-Ривса
- •Алгоритм метода Флетчера-Ривса
- •Глава 13. Методы условной оптимизации
- •13.1. Постановка задачи. Классификация методов
- •Общая схема методов условной оптимизации
- •Шаг 2.Шаг 1. Выбрать ( -я итерация) – возможное направление подъёма функции в точке . Если такого направления нет, то - решение задачи. В противном случае перейти к шагу 2.
- •13.2. Методы возможных направлений
- •13.2.1. Метод Зойтендейка
- •Пример 13.2
- •Итерация 3
- •Шаг 4.Рисунок 13.6
- •13.2.2. Метод Топкиса-Вейнотта
- •Пример 13.3
- •Итерация 1
- •Шаг 5.Рисунок 13.7
- •Алгоритм метода Топкиса-Вейнотта
- •13.2.3. Метод Франка-Вульфа
- •Алгоритм метода Франка-Вульфа
- •Шаг 5. Находим шаг в направлении новой точки . Решение этой задачи (одномерной): .
- •Шаг 3. Так как , переходим к шагу 4.
- •Шаг 5. Решаем задачу: .
- •Литература
12.4.4. Метод Дэвидона-Флетчера-Пауэлла Шаг 1.Метод Дэвидона-Флетчера-Пауэлла (дфп) принадлежит к классу квазиньютоновских методов, в которых направление поиска задаётся в виде
,
где - положительно определённая симметрическая матрица. Метод ДФП основан на использовании идей метода Ньютона и методов, использующих сопряжённые направления. В методе ДФП матрицы рекуррентно определяются так, чтобы последовательные приближения
минимизировали квадратичную функцию за конечное число шагов.
В отличие от метода Ньютона в методе ДФП используется только первые производные и не требуется на каждом шаге обращать матрицу . Кроме того, рекуррентные соотношения для матрицы строятся таким образом, чтобы последовательность матриц сходилась к .
Алгоритм метода дфп
Начальный этап. Задать начальную точку и симметрическую положительно определённую матрицу . Положить , . Задать - параметр окончания счёта.
Основной этап.
Шаг 1. Вычислить .
Шаг 2. Вычислить , положить .
Шаг 3. Если , то перейти к шагу 5.
Шаг 4. Вычислить , , ; , положить и перейти к шагу 1.
Шаг 5. Положить . Если , то положить и остановиться, иначе положить , , и перейти к шагу 1.
В условиях алгоритма ДФП справедлива теорема.
Теорема 12.4. Направления ( ), генерируемые алгоритмом ДФП, являются направлениями спуска, а матрицы ( )- симметрическими и положительно определёнными.
Теперь рассмотрим задачу безусловной оптимизации квадратичной функции:
, , (12.18)
где - симметрическая положительно определённая матрица.
Теорема 12.5. Пусть задача (12.18) решается методом ДФП. Тогда, если для всех , то
направления являются - сопряжёнными;
-является решением задачи (2.18);
.
Из теоремы 12.5. следует, что задача (12.18) с помощью алгоритма ДФП решается за одну итерацию .
Пример 12.11. Найти минимум функции
.
Начальный этап. Пусть , , положим , , вычислим .
Основной этап.
Итерация 1
.
Шаг 1. Вычислим .
Шаг 2. Вычислим , тогда .
Шаг 3. Так как , то переходим к шагу 4.
Шаг 4. Вычислим , , .
.
Положим и перейдём к шагу 1.
Шаг 1. Вычислим .
Шаг 2. Вычислим , тогда .
Шаг 3. Так как , то переходим к шагу 5.
Шаг 5. Положим . Так как , то - решение задачи.
Покажем, что матрица , которая была бы получена на шаге 4, равна . Действительно, так как , то .
С другой стороны, по формулам шага 4 имеем ; .
,
,
12.4.5. Метод сопряжённых градиентов Флетчера-Ривса
Метод Флетчера-Ривса основан на теореме 12.1, т. е. поиск решения осуществляется вдоль сопряжённых направлений. В отличие от метода ДФП, в котором направление поиска отклоняется от направления наискорейшего спуска в результате умножения на матрицу , в методе Флетчера-Ривса отклонение от направления наискорейшего спуска происходит в результате добавления к нему с некоторым коэффициентом направления, используемого на предыдущем шаге.
Алгоритм метода Флетчера-Ривса
Начальный этап. Задать начальную точку , - параметр окончания счёта, положить , , .
Основной этап.
Шаг 1. Если , то положить и остановиться.
Шаг 2. Вычислить , положить .
Шаг 3. Если , то перейти к шагу 5.
Шаг 4. Вычислить и , положить и перейти к шагу 1.
Шаг 5. Положить , , , и прейти к шагу 1.
Рассмотрим применение метода Флетчера-Ривса к задаче (12.18).
Теорема 12.6. Пусть задача (12.18) решается методом Флетчера-Ривса. Тогда, если для всех , то справедливы следующие утверждения:
направления являются - сопряжёнными;
направления являются направлениями спуска;
- решение задачи (12.18).
Из теоремы 12.6 следует что методом Флетчера-Ривса задача (12.18) решается за одну итерацию , т. е. не более чем за одномерных поисков. При оптимизации неквадратичных функций согласно алгоритму Флетчера-Ривса после реализации каждой - ой итерации ( одномерных поисков) происходит корректировка начального направления, полагается равным , т. е. направлению наискорейшего спуска. Такое периодическое обновление направления поиска, с одной стороны, позволяет уменьшить вероятность построения линейно-зависимых направлений, уменьшает нарастающую погрешность действий, но, с другой стороны, может повлечь за собой замедление сходимости.
Пример 12.12. Найти минимум функции методом Флетчера-Ривса.
.
Начальный этап. Пусть , , ; положим .
Основной этап.
Шаг 1. Вычислим , поэтому переходим к шагу 2.
Шаг 2. Вычислим , положим .
Шаг 3. Так как , то переходим к шагу 4.
Шаг 4. Вычислим , ; , положим и перейдём к шагу 1.
Шаг 1. Так как , то переходим к шагу 2.
Шаг 2. Вычислим , положим .
Шаг 3. Так как , то переходим к шагу 5.
Шаг 5. Положим , , , , и перейдём к шагу 1.
Шаг 1. Так как , то - решение задачи.