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

Рассмотрим данный метод применительно к задаче оптимизации с ограничениями-неравенствами. В качестве начальной выбирается некоторая точка допустимой области G.Еслих[0] -внутренняя точка множестваG(рис. 7.11), то рассматриваемый метод является обычным градиентным методом:

x[k+l] x[k] –a_kf’(x[k]), k 0, 1, 2, ..., (7.38)

где (7.39) ‑ градиент целевой функцииf(х)в точкеx[k].

После выхода на границу области Gв некоторой граничной точкех[k] , k 0, 1, 2,..., движение в направлении антиградиента-f’(х[k])может вывести за пределы допустимого множества (см. рис. 7.11). Поэтому антиградиент проецируется на линейное многообразиеМ,аппроксимирующее участок границы в окрестности точких[k].Двигаясь в направлении проекции вектора-f'(x[k]) на многообразиеМ,отыскивают новую точкух[k+1], в которойf(х[k+1]) f(x[k]), принимаютх[k+1] за исходное приближение и продолжают процесс. Проведем более подробный анализ данной процедуры.

Рис. ‑ 7.11 Геометрическая интерпретация метода проекции градиента

В точке х[k] часть ограничений-неравенств удовлетворяется как равенство:

h_i(x) 0,j 1, ...,l; l m.

Такие ограничения называют активными.

Обозначим через Jнабор индексов j(1 j l) этих ограничений. Их уравнения соответствуют гиперповерхностям, образующим границу областиGв окрестности точких[k] .В общем случае эта граница является нелинейной (см. рис. 3.1). Ограниченияh_j(x), j J,аппроксимируются гиперплоскостями, касательными к ним в точкех[k]:

(7.39)

Полученные гиперплоскости ограничивают некоторый многогранник М, аппроксимирующий допустимую областьGв окрестности точких[k] (см. рис. 7.11).

Проекция р[k] антиградиента ‑f'(x[k])на многогранник вычисляется по формуле

p[k] P[‑f’(x[k])]. (7.40)

Здесь Р ‑ оператор ортогонального проектирования, определяемый выражением

Р E – A^T(AA^T)^-1A, (7.41)

где Е‑ единичная матрица размеровп;А- матрица размеровlхn. Она образуется транспонированными векторами-градиентамиа_j, j 1, ...,l, активных ограничений. Далее осуществляется спуск в выбранном направлении:

x[k+1] x[k] +a_kp[k]. (7.42)

Можно показать, что точка х[k+1] является решением задачи минимизации функцииf(х)в областиGтогда и только тогда, когда

Р[‑f’(x[k])] 0, (7.43)

т. е, (7.44)

и u (u₁, ..., u_l) (A^TA)^-1A^T(-f’(х[k])) 0. (7.45)

Эти условия означают, что антиградиент (-f’(х[k]))целевой функции является линейной комбинацией с неотрицательными коэффициентами градиентов ограниченийh_j(x) 0.

В соответствии с изложенным алгоритм метода проекции градиента состоит из следующих операций.

1. В точке х[k] определяется направление спускар[k].

2.Находится величина шагаа_k.

3. Определяется новое приближение х[k+1].

Рассмотрим детально каждую из этих операций.

1. Определение направления спуска состоит в следующем. Пусть найдена некоторая точка х[k] Gи известен набор активных ограниченийh_i(х[k]) 0,j J. На основании данной информации вычисляют(-f’(х[k]))и определяют проекциюР[-f’(х[k])]. При этом возможны два случая:

а) Р[‑f’(х[k])] не равна 0. В качестве направления спускар[k] принимают полученную проекцию;

б) Р[-f’(х[k])] 0, т. е. . (7.46)

Данное выражение представляет собой систему из пуравнений для определения коэффициентови_j. Если всеи_j 0, j J, то в соответствии с вышеизложенным точках[k] является решением задачи. Если же некоторый компоненти_q 0, то соответствующий ему градиент выводится из матрицыАи порождается новая проецирующая матрицаР.Она определит новое направление спуска.

2. Для определения величины шага а_kцелевая функция минимизируется по направлениюр[k] при условии соблюдения ограничений задачи с установленной точностью. Последняя задается введением некоторого положительного числа. Считают, что точкахудовлетворяет условиям задачи с заданной точностью, еслиh_i(х) , j 1, ..., m. Величина шагаа_kопределяется решением задачи вида:

f(x[k] +ар[k])> min; (7.47)

h_j(x[k] +ар[k]) ,j 1, ...,m. (7.48)

3.Определение нового приближения состоит в следующем. Очередная точка вычисляется по формуле

x[k+1] x[k] + а_kр[k]. (7.49)

Признаком сходимости является стремление к нулю векторов р[k].Рассмотренный метод является в некотором смысле аналогом градиентных методов для решения задач на безусловный экстремум, и ему свойствен их недостаток - медленная сходимость.