3.3. Метод сопряженных градиентов
Описание алгоритма:
Данный метод обладает положительными свойствами методов Коши и Ньютона. Кроме того, этот метод использует информацию только о первых производных исследуемой функции. Метод сопряженных градиентов позволяет получить решение за шагов в -мерном пространстве и обладает квадратичной сходимостью. В основе метода лежит организация поиска вдоль сопряженных направлений, причем для получения сопряженных направлений используется квадратичная аппроксимация целевой функции и значения компонент градиента.
Операции аргумента проводятся по формуле:
Направление поиска на каждой итерации определяется с помощью формулы:
В
этом случае направление
будет
-сопряжено
со всеми ранее построенными направлениями
поиска.
Если
функция
квадратичная, то для нахождения точки
экстремума требуется определить
таких направлений и провести поиски
вдоль каждой прямой. Если
не является квадратичной, то количество
поисков возрастёт.
Используемые в методе формулы:
Изменение градиента при переходе от точки к точке :
Изменения аргумента:
Направление поиска:
,
,
.
(рекуррентная формула Флетчера-Ривса).
Алгоритм метода:
Шаг 1. Задать: начальную точку х(0). Перейти к шагу 2.
Шаг 2. Вычислить направление поиска. Произвести поиск вдоль прямой .
Шаг 3. Вычислено ли N-1 направлений.
Да: закончить поиск;
Нет: перейти к шагу 2.
Ход решения:
Исходные данные:
Шаг 1:
.
.
Шаг 2: поиск вдоль прямой
.
.
.
.
.
.
Шаг 3: k = 1:
Шаг 4: поиск вдоль прямой
Таким образом, - искомая точка.
Решение поставленной задачи методом сопряжённых градиентов представлено на рисунке 6.
|
Рисунок 6 – решение задачи методом сопряжённых градиентов |
3.4 Квазиньютоновский метод
Описание алгоритма:
Данный метод обладает положительными чертами метода Ньютона, однако, использует информацию только о первых производных. В этом методе приближение к очередной точке в пространстве оптимизируемых параметров задается формулой:
Направление поиска определяется выражением:
,
где
- матрица порядка
(метрика).
Матрица
- вычисляется по формуле.
,
где:
Где
изменение градиента на предыдущем шаге.
Данный алгоритм отличается устойчивостью, так как обеспечивает убывание целевой функции от итерации к итерации.
Алгоритм метода:
Шаг 1. Задать: начальную точку х(0). Перейти к шагу 2.
Шаг 2. Вычислить направление поиска s(k). Перейти к шагу 3.
Шаг 3. Произвести поиск вдоль прямой . Перейти
к шагу 4.
Шаг 4. Проверка условия окончания поиска.
Да: закончить поиск;
Нет: перейти к шагу2.
Ход решения:
Шаг 1.
Положим .
Шаг 2. Поиск вдоль прямой приводит к результату, полученному в предыдущем методе:
.
Шаг 3.
,
Шаг 4. Поиск вдоль прямой.
Решение поставленной задачи квазиньтоновским методом представлено на рисунке 7.
|
Рисунок 7 – решение задачи квазиньтоновским методом |
