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).
Алгоритм метода ОПГ начинает работать с допустимой точки . Если же относительно условий задачи не является допустимым, то необходимо ввести искусственные переменные, значения которых постепенно сводят к нулю путем введения в целевую функцию штрафного члена.
Если ОПГ ни на одном из этапов вычислительной процедуры не становится равным нулю, то заменяем текущий вектор на 
по общей формуле
, (6.7.21)
- определяется путем решения задачи
минимизировать 
при условиях 
.
где 
- направление оптимизационного поиска на -й итерации.
Рассмотрим способ определения величин для независимых переменных 
. Направления поиска 
для них определяют следующим способом:
, если 
; (6.7.22)
, если 
; (6.7.23)
или 
,
где 
- вектор ОПГ.
Если ограничения 
линейны, то метод совпадает с методом Вульфа.
Пример 6.7. Минимизировать 
при условии 
.
Пусть 
- независимая (небазисная) переменная, а 
- зависимая. Найдем величины
Согласно формуле (6.7.20) получим следующее выражение для ОПГ:
Итак, двигаясь из любой допустимой точки вдоль ограничения 
до тех пор, пока 
не станет равным нулю, выполняем минимизацию 
(рис. 6.18).
