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.
