Метод сопряжённых направлений Пауэлла
4.1 Описание алгоритма
Метод ориентирован на решение задач с квадратичными целевыми функциями. Основная идея алгоритма заключается в том, что если квадратичная функция:
приводится к виду сумма полных квадратов
то процедура нахождения оптимального решения сводится к одномерным поискам по преобразованным координатным направлениям.
В методе Пауэлла поиск реализуется в виде:
вдоль направлений ,
, называемых
-сопряженными при линейной независимости этих направлений.
Сопряженные направления определяются алгоритмически. Для нахождения экстремума квадратичной функции переменных необходимо выполнить
одномерных поисков.
4.2 Алгоритм метода
Шаг 1. Задать исходные точки ,
и направление
. В частности, направление
может совпадать с направлением координатной оси;
Шаг 2. Произвести одномерный поиск из точки в направлении
получить точку
, являющуюся точкой экстремума на заданном направлении;
Шаг 3. Произвести одномерный поиск из точки в направлении
получить точку
;
Шаг 4. Вычислить направление ;
Шаг 5. Провести одномерный поиск из точки (либо
) в направлении
c выводом в точку
.
4.3 Нахождение минимума целевой функции методом сопряжённых направлений Пауэлла.
Исходные данные:
- начальная точка
1. ,
.
2.
а) Найдем значение , при котором
минимизируется в направлении
:
Откуда ;
.
Значение функции в этой точке: ;
Продифференцируем полученное выражение по , получим:
. Приравняв его к нулю, находим
;
Получили
б) Аналогично находим значение минимизирующее функцию в направлении
:
Откуда ;
.
Значение функции в этой точке: ;
Продифференцируем полученное выражение по , получим:
. Приравняв его к нулю, находим
;
Получили
в) Найдем значение минимизирующее
:
Откуда ;
.
Значение функции в этой точке: ;
Продифференцируем полученное выражение по , получим:
. Приравняв его к нулю, находим
;
Получили
3.
4. Найдем такое значение , при котором
минимизируется в направлении
.
Откуда ;
.
Значение функции в этой точке: ;
Продифференцируем полученное выражение по , получим:
. Приравняв его к нулю, находим
;
Получили
Таким образом, получили точку , значение функции в которой равно
, что совпадает со стационарной точкой
Рисунок 4. Графическое пояснение метода сопряженных направлений Пауэлла
Метод Коши
5.1 Описание алгоритма
В методе Коши или методе наискорейшего спуска в качестве направления поиска выбирается направление антиградиента.
- градиент функции
Алгоритм метода выглядит следующим образом:
, где
- градиент.
Значение на каждой итерации вычисляется путем решения задачи одномерного поиска экстремума
вдоль направления градиента
. Если в качестве
взять некоторое положительное число, то получится простейший градиентный алгоритм:
Одно из главных достоинств метода Коши является его устойчивость, так как всегда выполняется условие:
Однако вблизи экстремума скорость сходимости алгоритма становится недопустимо низкой, так как вблизи экстремума значение градиента стремится к нулю.
5.2 Нахождение минимума целевой функции методом Коши.
Исходные данные:
- начальная точка (начальное приближение)
Вычислим компоненты градиента:
Начальное приближение
1. Новое приближение определим по формуле:
Выбираем такое, чтобы минимизировать функцию
2. Далее найдем точку:
3. Далее найдем точку:
4. Далее найдем точку:
После 4 итераций найдено достаточно точное значение минимума, при котором значение целевой функции в точке ,
.
Рисунок 5. Графическое пояснение метода Коши
Метод Ньютона
6.1Описание алгоритма
Этот метод использует информацию о вторых производных целевой функции. Эта информация появляется при квадратичной аппроксимации целевой функции, когда при её разложении в ряд Тейлора учитываются члены ряда до второго порядка включительно. Алгоритм метода выглядит следующим образом:
, где:
- гессиан (матрица Гессе)
В случае, когда гессиан положительно определён, направление по методу Ньютона оказывается направлением спуска.
6.2 Нахождение минимума целевой функции методом Ньютона.
Исходные данные:
- начальная точка;
;
Таким образом, точка минимума , значение функции в которой
найдена за одну итерацию.
Рисунок 6. Графическое пояснение метода Ньютона