6.6. МЕТОД проекции ГРАДИЕНТА Розена
Как указывалось выше, направлением наискорейшего спуска является антиградиент целевой функции. Однако при наличии ограничений движение вдоль направления наискорейшего спуска может привести в недопустимые точки. В методе проекции градиента, предложенном Розеном, антиградиент проектируется таким образом, что значение целевой функции улучшается и в то же время обеспечивается допустимость точек траектории движения. Прежде чем изложить метод, рассмотрим некоторые необходимые понятия из проективной геометрии [2].
Определение 6.2. Матрица
порядка
называется матрицей проектирования, если
и
.
Справедливы следующие утверждения, определяющие свойства матрицы проектирования,
1. Если
- матрица проектирования, то она положительно полуопределена.
2. Для того чтобы
была матрицей проектирования, необходимо и достаточно, чтобы
была матрицей проектирования.
3. Пусть
- матрица проектирования, а
. Тогда подпространства
и
являются ортогональными. Кроме того, любая точка
может быть представлена однозначно в виде
, где
.
Доказательство.
1. Пусть
- матрица проектирования, а
- произвольная точка из
. Тогда
и, следовательно
- положительно полуопределена.
2. Справедливость второго утверждения следует из определения матрицы проектирования.
3. Ясно, что
и
- линейные подпространства. Заметим, что
, и, следовательно,
и
- ортогональны.
Пусть теперь
- произвольная точка из
. Тогда
, где
(6.6.1)
Покажем единственность этого представления . Предположим, что
, где
(6.6.2)
Сравнивая выражения (6.6.1) и (6.6.2), получим
. Следовательно,
; так как единственной точкой пересечения
и
является начало координат, то
. Таким образом, представление
единственное.
Задачи с линейными ограничениями
Рассмотрим задачу НП:
минимизировать
(6.6.3)
при условиях
, (6.6.4)
где
- матрица порядка
;
-
-мерный вектор;
-
-мерный вектор; функция
дифференцируема. В заданной допустимой точке
направлением наискорейшего спуска является вектор
. Однако движение вдоль направления
может нарушить допустимость. Чтобы ее сохранить, спроектируем
так, чтобы двигаться вдоль направления
, где
- соответствующая матрица проектирования.
В следующей лемме приводится вид соответствующей матрицы проектирования
и доказывается, что
является возможным направлением спуска.
Лемма 6.3. Рассмотрим задачу (6.6.3), (6.6.4). Пусть
- допустимая точка, для которой
, где
, а
. Кроме того, предположим, что функция
дифференцируема в
. Если
- матрица проектирования такая, что
, то вектор
является направлением спуска для функции
в точке
. Кроме того, если
имеет полный ранг и если
, (6.6.5)
то
- возможное направление спуска.
Доказательство. Заметим, что
. (6.6.6)
Таким образом, согласно лемме 6.1 вектор
является направлением спуска. Кроме того, если
, то
, так что
и
. И по лемме 6.1 направление
будет в таком случае возможным.
Заметим, что матрица
, определяемая выражением (6.6.5), является действительно матрицей проектирования, удовлетворяющей равенствам
и
. Кроме того,
, т.е.
. Таким образом, матрица
проектирует каждую вектор-строку матриц
в нулевой вектор. А так как строками матриц
являются градиенты функций активных ограничений, то
- это матрица, проектирующая градиенты функций активных ограничений в нулевой вектор.
На рис. 6.16 показан процесс проектирования градиента для задачи с ограничениями-неравенствами. На нем обозначено: 1 - линии уровня целевой функции; 2 - оптимальное решение.
В точке
активным является только одно ограничение, градиент которого равен
. Заметим, что
- возможное направление спуска.
Если
, то, как мы только что показали, вектор
является возможным направлением спуска. Рассмотрим теперь случай, когда
. Тогда

(6.6.7)
где
.
Если
, то точка
удовлетворяет условиям Куна-Таккера. Если же
, то как показано ниже, можно определить новую матрицу проектирования
такую, что вектор
будет возможным направлением спуска.
Теорема 6.4. Рассмотрим задачу НП (6.6.3), (6.6.4). Пусть
- допустимая точка, для которой
, где
, а
. Предположим, что
- матрица полного ранга и
. Далее предположим, что
,
. Если
, то
является точкой Куна-Таккера. В противном случае пусть некоторая компонента
вектора
отрицательна, а
. Здесь
получили из матрицы
вычеркиванием строки, соответствующей
. Обозначим
, и пусть
. Тогда вектор
является возможным направлением спуска.
Доказательство. Рассмотрим соотношение (6.6.7), справедливое для случая, когда
. Если
, то точка
- это точка Куна-Таккера (т.е. оптимальное решение).
Предположим, что
, и пусть
. Покажем, что
. Предположим противное, т.е., что
. Положим
. По определению
имеем
(6.6.8)
Заметим, что вектор
может быть представлен в виде
, где
является
-й строкой матрицы
.Таким образом, из (6.6.7) имеем
(6.6.9)
Вычитая (6.6.9) из (6.6.8), получим
. Так как
, то это противоречит предположению о том, что матрица
имеет полный ранг. Следовательно,
и по лемме 6.3 вектор
является направлением спуска.
Покажем теперь, что
- возможное направление (спуска). Заметим, что
, следовательно
(6.6.10)
По лемме 6.3 вектор
является возможным направлением, если
и
. Чтобы убедиться в том, что
- возможное направление, достаточно, учитывая (6.6.10), показать, что
. Умножим (6.6.9) на
. Учитывая, что
, получим
(6.6.11)
По свойству 2 матрица
положительно полуопределена, так что
. Так как
, то из (6.6.11) следует, что
.
Алгоритм метода проекции градиента
(случай линейных ограничений)
Итак, пусть задана задача НП вида
минимизировать 
при условиях
.
Предварительный этап. Выбрать точку
, для которой
и
. Представим
и
в виде
и
соответственно
. Положить
и перейти к основному этапу.
Основной этап. Первый шаг. Положить
. Если
Æ, т.е. не содержит ни одного столбца, то положить
. В противном случае положить
. Положить
. Если
, то перейти ко второму шагу. Если
и
Æ, то остановиться. Если же
Æ, то положить
. Пусть
. Если
, то остановиться;
- точка Куна-Таккера. Иначе, выбрать отрицательную компоненту
этого вектора и переопределить матрицу
, вычеркивая строку, соответствующую
, и повторить первый шаг.
Второй шаг. Взять в качестве
оптимальное решение следующей задачи линейного поиска:
минимизировать 
при условии
,
где
определяется в соответствии с соотношением
(6.6.12)

Положить
, заменить
на
и перейти к первому шагу.
Пример 6.6. Решить методом проекции градиента задачу
минимизировать 
при условиях

Выберем в качестве начальной точку 
Первая итерация. Первый шаг. В точке
имеем
. Кроме того, в точке
активными являются только ограничения неотрицательности, так что

Тогда
и
. Учитывая, что ограничения-равенства в задаче отсутствуют, вычислим
.
Выберем
и удалим строку, отвечающую четвертому ограничению из
. Матрица
преобразуется к виду
. Преобразованная матрица проектирования принимает вид
- направление движения
определяется вектором 
Второй шаг. Линейный поиск. Любая точка,полученная движением из точки
по направлению
, может быть представлена в виде
. Соответствующее ей значение ц.ф. равно
. Максимальное значение
, для которого точка
допустима, получается в соответствии с (6.6.12) и равно
,
следовательно,
является оптимальным решением следующей задачи:
минимизировать 
при условии 
и равно
, так что
.
Вторая итерация. Первый шаг. В точке
имеем
. Кроме того, в этой точке активными являются второе и третье ограничение, поэтому получим
.
Далее вычисляем
и, следовательно,
. Вычисляем
.
Так как
, то соответствующая строка
вычеркивается из
, и получаем матрицу
. Матрица проектирования и соответствующее направление определяются следующим образом:

Так как для выбора направления
длина вектора
не имеет значения, то вектор
эквивалентен вектору 
Второй шаг. Линейный поиск. Итак, рассмотрим точку x2+λS2=[5λ;1-λ]T , в которой значение ц.ф. равно f(x2+λS2)=62λ2-28λ-4.
Максимальное значение
, для которого точка x2+λS2 допустима, в соответствии с (6.6.12) равно 
Таким образом,
определяется из решения следующей задачи:
минимизировать 
при условии
.
Оптимальным решением ее является
, так что
.
Третья
итерация.
Первый шаг. В точке

вычисляем

.
Кроме того, в этой точке активным является второе ограничение, т.е.

. Находим матрицу проектирования

и направление поиска

. Далее вычисляем

.
Следовательно точка
оптимальна.
Заметим, что градиент функции активного ограничения в этой точке противоположен по знаку

и

для

. Поэтому

- точка Куна-Таккера. Так как

выпукла, то точка

является точкой глобального оптимума.
Процесс решения задачи приведен на рис. 6.17.