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

Рассмотрим данный метод применительно к задаче оптимизации с ограничениями-неравенствами. В качестве начальной выбирается некоторая точка допустимой области 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] при условии соблюдения ограничений задачи с установленной точностью. Последняя задается введением некоторого положительного числа e. Считают, что точка х удовлетворяет условиям задачи с заданной точностью, если h_i(х) e, j 1, ..., m. Величина шага а_k определяется решением задачи вида:

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

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

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

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

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