Метод проекции вектор-градиента

Метод разработан для решения задач с ограничениями типа равенств:

где .

Поиск условного минимума происходит парами шагов. Первый шаг в каждой паре производится в том случае, если нарушены ограничения ψ_j (X)=0.Точного выполнения ограничений практически добиться нельзя, поэтому считают, что они нарушены. Если ψ_j (X) ≥ Δψ_j, где Δψ_j – предельно допустимое отклонение ограничений от нуля.

Первый шаг заключается в перемещении отображающей точки на гиперповерхность ограничений, т.е. в спуске на гиперповерхность ограничений. Такое перемещение производится из текущей точки X_k по направлению нормали к гиперповерхности ограничений. Вектор приращений управляемых параметров определяется по формуле:

,

где D_k – матрица размера m x n, строками которой являются градиенты функции ограничений ψ_j (X) в точке X_k:

∂ψ₁/∂x₁ ∂ψ₁/∂x₂…∂ψ₁/∂x_n

D = ∂ψ₂/∂x₁ ∂ψ₂/∂x₂…∂ψ₂∂x_n

..……………………..

∂ψ_m∂x₁ ∂ψ_m/∂x₂…∂ψ_m/∂x_n

Ψ; (X_k)- вектор- функция ограничений в точке X_k.

После попадания в малую окрестность гиперповерхности ограничений выполняется второй шаг, имеющий целью продвижение в сторону уменьшения целевой функции без нарушения ограничений, поэтому перемещение происходит в гиперплоскости, касательной гиперповерхности ограничений. Направление шага противоположно направлению проекции вектор-градиента F(X) на эту поверхность. Проекция задается с помощью проецирующей матрицы:

,

где I – единичная матрица порядка «n».

Шаг заключается в изменении управляемых параметров по формуле:

X_k - h_kH_kgrad F(X_k).

Этот шаг приводит к нарушению ограничений, поэтому следующий шаг будет шагом спуска на гиперповерхность ограничений и т.д.

 

Метод проекции вектор-градиента применим и к решению задач с ограничениями типа неравенств.

Пример.

 

Можно использовать для нахождения условного экстремума метод, похожий на метод градиентного поиска. В этом методе в области XP осуществляется градиентный поиск, а вне области XP движение происходит в направлении суммы градиентов нарушенных ограничений. Траектория поиска имеет зигзагообразный характер: движение к экстремуму замедленное.