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 – оптимальное решение.

В точке  активным является только одно ограничение, градиент которого равен . Заметим, что  – возможное направление спуска.

Text Box: Рис. 6.16 Если , то, как мы только что показали, вектор  является возможным направлением спуска. Рассмотрим теперь случай, когда . Тогда

(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) равно

Таким образом,  определяется из решения следующей задачи:

минимизировать

при условии                                            .

 Оптимальным решением ее является , так что .

x3
 
 Третья итерация. Первый шаг. В точке  вычисляем .

x3
 
Кроме того, в этой точке активным является второе ограничение, т.е. . Находим матрицу проектирования  и направление поиска . Далее вычисляем .

 Следовательно точка  оптимальна.

x1
 
 Заметим, что градиент функции активного ограничения в этой точке противоположен по знаку и  для . Поэтому  – точка Куна-Таккера. Так как выпукла, то точка  является точкой глобального оптимума.

Процесс решения задачи приведен на рис. 6.17.