Представляет усовершенствование метода покоординатного спуска.
Понятие сопряжённости векторов
В методе сопряженных градиентов используется понятие сопряжённости векторов.
< A, Q, B > = 0
Q – квадратная матрица того же порядка, что и вектора.
В этом случае вектора А и В будут Q сопряжёнными.
Q = [1]
< A*B> = 0
Сходимость метода сопряжённых градиентов строго обоснована для квадратичных целевых функций.
F(X) = A*X + XTЮХ/2,
где Ю – матрица Гессе.
Минимизация такой функции осуществляется не более чем за n одномерных минимизаций вдоль определённым образом выбираемых сопряжённых направлений.
Метод сопряжённых градиентов ( Флетчера – Ривса)
1) Задается начальная точка поиска Х: = Х0
2) Рассчитывается grad F(X)
3) Определяется первое направление для поиска P: = -grad F(X)
4) Производится одномерная минимизация на направлении P
F (X`) = min F(X +hP)
Получаем новую отображающую точку - X: = X`
5) Рассчитывается градиент в этой точке - grad F(X`)
6) Вычисляется коэффициент β, определяющий новое направление поиска.
7) Определяется новое сопряжённое направление
P: = - grad F(X) +βP
8) Проверяется условие прекращения поиска, например, на близость grad F(X) к 0 - grad F(X) ≤ δ. Если они не выполнены, то переход к оператору 4)
9) Через n шагов поиска по сопряжённым направлениям осуществляется обновление метода, т.е. переход к оператору 2).
Предложены различные формулы для вычисления β. приведем одну из них:
grad F(Xi)* grad F(Xi)
βi-1 =
grad F(Xi-1)* grad F(Xi-1)
Этот метод базируется на методе Ньютона, в котором минимизация квадратичной целевой функции происходит за один шаг.
Метод Ньютона неудобен тем, что в нем должна вычисляться матрица Гессе [Ю].
Метод переменной метрики является итерационным методом, в котором поиск ведется по формуле:
Xk+1 = Xk –hkHkgrad F(Xk),
в качестве матрицы Hk выбирается приближенно вычисляемая матрица Гессе. Величина шага hk определяется одномерной минимизацией целевой функции F(X) на луче - -Hkgrad F(X).
Матрица Hk вычисляется по формуле:
;
где hk-1Hk-1grad F(Xk-1) – приращение вектора управляемых параметров на предыдущем «k-1» шаге; - транспонированный вектор; - вектор строка.
В начале вычисления задаются матрицей H0 , которая должна отвечать единственному требованию – быть положительно определенной. Такой матрицей, например, может быть единичная матрица.
Метод переменной метрики – один из наиболее эффективных методов решения задач параметрической оптимизации.
Метод разработан для решения задач с ограничениями типа равенств:
где .
Поиск условного минимума происходит парами шагов. Первый шаг в каждой паре производится в том случае, если нарушены ограничения ψj (X)=0.Точного выполнения ограничений практически добиться нельзя, поэтому считают, что они нарушены. Если ψj (X) ≥ Δψj, где Δψj – предельно допустимое отклонение ограничений от нуля.
Первый шаг заключается в перемещении отображающей точки на гиперповерхность ограничений, т.е. в спуске на гиперповерхность ограничений. Такое перемещение производится из текущей точки Xk по направлению нормали к гиперповерхности ограничений. Вектор приращений управляемых параметров определяется по формуле:
,
где Dk – матрица размера m x n, строками которой являются градиенты функции ограничений ψj (X) в точке Xk :
∂ψ1/∂x1 ∂ψ1/∂x2…∂ψ1/∂xn
D = ∂ψ2/∂x1 ∂ψ2/∂x2…∂ψ2∂xn
..……………………..
∂ψm∂x1 ∂ψ1/∂x2…∂ψm/∂xn
ψ(Xk )- вектор- функция ограничений в точке Xk.
После попадания в малую окрестность гиперповерхности ограничений выполняется второй шаг, имеющий целью продвижение в сторону уменьшения целевой функции без нарушения ограничений, поэтому перемещение происходит в гиперплоскости, касательной гиперповерхности ограничений. Направление шага противоположно направлению проекции вектор-градиента F(X) на эту поверхность. Проекция задается с помощью проецирующей матрицы:
,
где I – единичная матрица порядка «n».
Шаг заключается в изменении управляемых параметров по формуле:
Xk - hkHkgrad F(Xk).
Этот шаг приводит к нарушению ограничений, поэтому следующий шаг будет шагом спуска на гиперповерхность ограничений и т.д.
Метод проекции вектор-градиента применим и к решению задач с ограничениями типа неравенств.
Пример.
Можно использовать для нахождения условного экстремума метод, похожий на метод градиентного поиска. В этом методе в области XP осуществляется градиентный поиск, а вне области XP движение происходит в направлении суммы градиентов нарушенных ограничений. Траектория поиска имеет зигзагообразный характер: движение к экстремуму замедленное.