6.7. МЕТОД приВЕДЕННОГО ГРАДИЕНТА

Метод приведенного градиента (МПГ) основан на сокращении размерности задачи с помощью представления всех переменных через множество независимых переменных. Впервые его предложил Вульф в (1963) для задач линейного программирования с линейными ограничениями. Позднее этот метод был обобщен на случай нелинейных ограничений. Итак, рассмотрим следующую задачу:

минимизировать (6.7.1)

при условиях

, (6.7.2)

, (6.7.3)

где матрица – матрица порядка ранга ; - -мерный вектор, а функция непрерывно дифференируема. Сделаем следующее предположение о невырожденности матрицы . Любые столбцов линейно независимы, и каждая крайняя точка допустимой области имеет ровно положительных переменных и не более чем нулевых компонент.

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

Вспомним, что направление является возможным направлением спуска для функции в точке , если и , если .

Определим возможное направление спуска в данной задаче.

Представим вектор в виде . Заметим, что равенство автоматически выполняется, если для любого положить

Обозначим через

(6.7.4)

приведенный градиент.

Исследуем:

. (6.7.5)

Необходимо выбрать так, чтобы и если . Введем следующее правило. Для каждой небазисной компоненты положим , если и возьмем , если . Это обеспечивает выполнение неравенства , если . Кроме того, и строгое неравенство имеет место при .

Если , то – возможное направление спуска. Кроме того, тогда и только тогда, когда – точка Куна-Таккера. Доказательство этого утверждения можно найти в [2].

Алгоритм метода приведенного градиента

Рассмотрим алгоритм приведенного градиента (ПГ) для решения задачи (6.7.1)-(6.7.3).

Предполагается, что любые столбцов линейно независимы.

Начальный этап. Выбрать точку , удовлетворяющую условиям . Положить и перейти к основному этапу.

Основной этап. Первый шаг. Положить , где и получены по формулам (6.7.4) и (6.7.5) соответственно. Если , то остановиться, – точка Куна-Таккера. В противном случае перейти ко второму шагу. Здесь – множество индексов наибольших компонент вектора ,

(6.7.6)

(6.7.7)

(6.7.8)-(6.7.9)

. (6.7.10)

Второй шаг. Решить следующую задачу одномерной оптимизации:

минимизировать (6.7.11)

при условии ,

где (6.7.12)

Здесь - -е компоненты векторов соответственно. Положить равным оптимальному решению и . Заменить на и перейти к первому шагу.

Метод обобщенного приведенного градиента

Метод обобщенного приведенного градиента (ОПГ) является развитием метода ПГ и его можно использовать для решения задач НП при нелинейных функциях-ограничениях.

Итак, пусть задача НП задана в виде

минимизировать (6.7.13)

при условиях

, (6.7.15)

В методе ОПГ также различают две группы переменных: а) подмножество базисных переменных ; б) подмножество небазисных, или независимых переменных . Примем для простоты обозначений . При этом зависимые (т.е. базисные) переменные неявным образом определяются через независимые (небазисные) переменные, следовательно, – функция независимых переменных. Введем следующие обозначения:

(6.7.16)

Основная идея метода ОПГ состоит в том, чтобы сократить размерность задачи путем исключения зависимых (базисных) переменных и применить метод ПГ для определения направления спуска и в качестве критерия при установлении оптимальности.

Укажем способ вычисления обобщенного ПГ. Для этого рассмотрим задачу (6.7.13)-(6.7.15) и выразим обобщенный ПГ через компоненты градиента и якобиан для ограничений-равенств (6.7.14)

. (6.7.17)

Исключим из (6.7.17) матрицу . Для этого воспользуемся соотношением

, (6.7.18)

откуда

. (6.7.19)

Подставляя (6.7.19) в (6.7.17), получим выражение для ОПГ

; (6.7.20)

где ; .

Нетрудно увидеть аналогию между выражением (6.7.20) и соотношением (6.7.4) для ПГ в линейном случае. Действительно, если учесть, что , то . Подставив их в (6.7.20), получим полное совпадение выражений (6.7.20) и (6.7.4).

Алгоритм метода ОПГ начинает работать с допустимой точки . Если же относительно условий задачи не является допустимым, то необходимо ввести искусственные переменные, значения которых постепенно сводят к нулю путем введения в целевую функцию штрафного члена.

Если ОПГ ни на одном из этапов вычислительной процедуры не становится равным нулю, то заменяем текущий вектор на по общей формуле