- •Решение задач оптимизации
- •2013 Г. Введение
- •Нахождение стационарной точки
- •Рис 1. Линии уровня функции и стационарная точка
- •2.Нахождение безусловного экстремума методами прямого поиска.
- •2.1.Метод поиска по симплексу
- •Рис 2. Графическое пояснение метода равномерного симплекса
- •2.2 Метод поиска Хука-Дживса
- •Рис 3. Графическое пояснение метода Хука-Дживса
- •2.3Метод сопряженных направлений Пауэлла
- •Рис 4. Графическое пояснение метода сопряженных направлений Пауэлла
- •3.Нахождение безусловного экстремума градиентными методами
- •3.1 Метод Коши
- •Рис 5. Графическое пояснение метода Коши
- •Рис 6. Графическое пояснение метода Ньютона
- •Метод сопряженных градиентов
- •Рис 7. Графическое пояснение метода сопряженных градиентов
- •Рис 8. Графическое пояснение квазиньютоновского метода Заключение
Рис 3. Графическое пояснение метода Хука-Дживса
2.3Метод сопряженных направлений Пауэлла
Описание алгоритма:
Метод ориентирован на решение задач с квадратичными целевыми функциями. Основная идея алгоритма заключается в том, что если квадратичная функция:
приводится к виду сумма полных квадратов
то процедура нахождения оптимального решения сводится к одномерным поискам по преобразованным координатным направлениям.
В методе Пауэлла поиск реализуется в виде:
вдоль направлений ,, называемых-сопряженными при линейной независимости этих направлений.
Сопряженные направления определяются алгоритмически. Для нахождения экстремума квадратичной функции переменных необходимо выполнитьодномерных поисков.
Алгоритм метода:
Шаг 1. Задать исходные точки ,и направление. В частности, направлениеможет совпадать с направлением координатной оси;
Шаг 2. Произвести одномерный поиск из точки в направленииполучить точку, являющуюся точкой экстремума на заданном направлении;
Шаг 3. Произвести одномерный поиск из точки в направленииполучить точку;
Шаг 4. Вычислить направление ;
Шаг 5. Провести одномерный поиск из точки (либо ) в направлениис выводом в точку .
Ход решения:
Исходные данные:
Шаг 1.
- начальная точка
, .
Шаг 2.
а) Найдем значение , при которомминимизируется в направлении:
Откуда ;.
Значение функции в этой точке: ;
Продифференцируем полученное выражение по , получим:
. Приравняв его к нулю, находим ;
Получили
б) Аналогично находим значение минимизирующее функцию
в направлении :
Откуда ;.
Значение функции в этой точке: ;
Продифференцируем полученное выражение по , получим:
. Приравняв его к нулю, находим ;
Получили
в) Найдем значение минимизирующее:
Откуда ;.
Значение функции в этой точке: ;
Продифференцируем полученное выражение по , получим:
. Приравняв его к нулю, находим ;
Получили
Шаг 3.
Шаг4. Найдем такое значение , при которомминимизируется в направлении.
Откуда ;.
Значение функции в этой точке: ;
Продифференцируем полученное выражение по , получим:
. Приравняв его к нулю, находим ;
Получили
Таким образом, получили точку , значение функции в которой равно, что совпадает со стационарной точкой.
Рис 4. Графическое пояснение метода сопряженных направлений Пауэлла
3.Нахождение безусловного экстремума градиентными методами
В отличии от методов прямого поиска градиентные методы поиска используют информацию о производных функции. Это позволяет уменьшить
количество необходимых вычислений значений функции. Эти методы делятся на две группы: методы, использующие информацию только о первых производных , и методы, учитывающие информацию и первых, и вторых производных.
3.1 Метод Коши
Описание алгоритма:
В методе Коши или методе наискорейшего спуска в качестве направления поиска выбирается направление антиградиента.
- градиент функции
Алгоритм метода выглядит следующим образом:
, где - градиент.
Значение на каждой итерации вычисляется путем решения задачи одномерного поиска экстремумавдоль направления градиента. Если в качествевзять некоторое положительное число, то получится простейший градиентный алгоритм:
Одно из главных достоинств метода Коши является его устойчивость, так как всегда выполняется условие:
Однако вблизи экстремума скорость сходимости алгоритма становится недопустимо низкой, так как вблизи экстремума значение градиента стремится к нулю.
Алгоритм метода:
Шаг 1. Задать: 1. Начальную точку х(0) ;
2. Условие окончания поиска. Перейти к шагу 2.
Шаг 2. Вычислить направление поиска в виде антиградиента функции
s(x(k) ) = - ∇f(x(k) );
. Перейти к шагу 3.
Шаг 3. Найти новое приближение
, где - величина шага относительно текущего приближения. Перейти к шагу4.
Шаг 4. Проверка условия окончания поиска.
Да: закончить поиск;
Нет: перейти к шагу 2.
Ход решения:
Исходные данные:
Шаг 1.
- начальная точка (начальное приближение);
Вычислим компоненты градиента:
Шаг 2.
Шаг 3. Начальное приближение
1. Новое приближение определим по формуле:
Шаг 2.
Выбираем такое, чтобы минимизировать функцию
Шаг 3.
Значение функции в этой точке: ;
Продифференцируем полученное выражение по , получим:
. Приравняв его к нулю, находим ;
2. Далее найдем точку:
Шаг 2.
Шаг 3.
Значение функции в этой точке: ;
Продифференцируем полученное выражение по , получим:
. Приравняв его к нулю, находим ;
3. Далее найдем точку: ;
Шаг 2.
Шаг 3.
;
Значение функции в этой точке: ;
Продифференцируем полученное выражение по , получим:
. Приравняв его к нулю, находим ;
;
;
После третьей итерации найдено достаточно точное значение минимума, при котором значение целевой функции в точке ,.