Градиентные методы решения задач нелинейного программирования

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

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

Наиболее распространенными из градиентных методов являются методы приведенного градиента Вулфа, штрафных функций и Эрроу−Гурвица.

5.4.1 Метод приведенного градиента Вулфа

Пусть требуется минимизировать целевую функцию

                                          (5.25)

при условиях                              

                          (5.26)

где матрица А − матрица порядка m×n и ранга m, b − вектор из Е_m, функция f непрерывно дифференцируема в Е_n.

 Заметим, что ограничения (5.26) линейные. Предположим, что А невырожденная матрица, а x - допустимая точка. Матрицу А можно представить в виде , а вектор  − в виде , где В – неособенная матрица порядка m×m. Вектор x_B называется базисным, и его компоненты строго положительны. Компоненты внебазисного вектора  могут быть либо положительными, либо нулевыми.

Пусть , где  − градиент функции f по переменным базисного вектора , а  − градиент f по внебазисным переменным . Направление  является направлением спуска и возможным для функции f в точке , если  и , если . Определим вектор , обладающий этими свойствами. Представим вектор  в виде . Равенство =0 выполняется, если для любого  положить .

Пусть  − приведенный градиент. Исследуем .

=

                            = .

Мы должны выбрать вектор  так, чтобы  и , если . Для этого принимается следующее правило. Для каждой внебазисной компоненты j положим , если , и положим , если r_j>0. Из этого следует выполнение неравенства , если . Кроме того,  и строгое неравенство имеет место, если .

Здесь вектор  в том и только том случае, если  седловая точка Куна−Таккера.

В целях сокращения записей символ, означающий транспонирование опущен.

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

Пусть имеем задачу (5.26). Предположим, что любые m столбцов матрицы А линейно независимы и что каждая экстремальная точка допустимой области (5.26) имеет m строго положительных компонент. Указанный алгоритм сходится к точке Куна−Таккера при условии, что в качестве базисных переменных выбраны m наибольших положительных переменных.

Начальный этап.

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

Основной этап.

Шаг 1. Положить , где  и  получаются из формул (5.30) и (5.31) соответственно. Если , то остановиться; − оптимальная точка (точка Куна − Таккера). В противном случае перейти к шагу 2.

I_k − множество индексов m наибольших компонент вектора ,                                                             (5.27)

, ,                   (5.28)

,                 (5.29)

         (5.30)

.                            (5.31)

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

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

при условии

                          ,

где       (5.32)

Здесь – j-е компоненты векторов и .

Положим λ_k равным оптимальному и . Заменить k на k+1 и перейти к шагу 1.

Пример 5.4.

Рассмотрим задачу:

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

при условиях

.

В качестве начальной точки выберем .

Градиент функции .

Информацию по каждой итерации будем представлять в виде таблицы, подобной симплекс-таблице.

Итерация 1.

Поиск направления.

В точке  имеем . В соответствии с (5.27) множество I₁={3,4}, так что B=[a₃,a₄] и D=[a₁,a₂] (согласно (5.28)). Согласно (5.29) приведенный градиент

.

Результаты вычислений будем помещать в таблицу 5.2.

В соответствии с (5.30) имеем . По формуле (5.31) . Получим

, , . Тогда . Вектор направления, таким образом, равен .

Линейный поиск.

При начальной точке  минимизируем целевую функцию по направлению . Максимальное значение λ, для которого точка  допустима, вычисляется в соответствии с (5.32) и равно

.

Значение целевой функции в точке

,

так что задача линейного поиска имеет вид:

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

при условии

.

Отсюда

 и .

Итерация 2.

Поиск направления. В точке  в соответствии с (5.27) имеем

 и

.

В соответствии с (5.29) имеем

Тогда, согласно (5.30) имеем, что

  и , так что .

Вектор  равен

.

Таким образом, вектор направления равен

.

Линейный поиск.

Начиная процедуру из точки , минимизируем целевую функцию по направлению . Максимальное значение λ, для которого точка  допустима, равно

                        .

Значение целевой функции в точке , так что находится из решения задачи.

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

при условии

                            .

Отсюда , .

Итерация 3.

Поиск направления.

Теперь I₃={1,2}, то есть B=[a₁,a₂] и D=[a₃,a₄]. Имеем

                          .

Вектор

Отсюда , . Следовательно,  и решение  оптимально.

Таблица 5.2 – Результаты вычислений методом градиента  Вулфа

Решение	0	0	2	5	0,0
	-4	-6	0	0
	1 1	1 5	1 0	0 1
	-4	-6	0	0
Решение				0	-6,436
			0	0
	1   0	0   1
	0	0
Решение				0	-7,16
			0	0
	1 0	0 1
	0	0	0	1

5.4.2 Метод штрафных функций

Для определенности рассмотрим задачу нахождения максимального значения вогнутой функции  при условиях , где g_i – выпуклые функции. Заметим, что здесь функции g_i могут быть как линейными, так и нелинейными. Однако в первом случае удобнее использовать метод приведенного градиента Вулфа, что существенно сокращает вычисления.

Вместо непосредственного решения вышеприведенной задачи, находят максимальное значение функции

= + , являющейся суммой целевой функции задачи, и некоторой функции Н, определяемой системой ограничений и называемой штрафной функцией. Штрафную функцию записываем в виде:

     = ,

где  , (5.33)

а  − некоторые постоянные числа, называемые весомыми коэффициентами.

Используя штрафную функцию, последовательно переходят от одной точки к другой до тех пор, пока не получат приемлемое решение. При этом координаты последующей точки находят по формуле

   .    (5.34)

Из соотношения (5.34) следует, что если предыдущая точка находится в области допустимых решений исходной задачи, то второе слагаемое в квадратных скобках равно нулю и переход к последующей точке определяется только градиентом целевой функции.

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

Алгоритм метода штрафных функций.

Процесс нахождения решения задачи выпуклого программирования включает следующие этапы:

1. Определяют исходное допустимое решение.

2. Задают точность вычислений (штрафной параметр λ).

3. Находят по всем переменным частные производные от целевой функции и функций, определяющих область допустимых решений задачи.

4. По формулам (5.34) находят координаты точки, определяющей возможное новое решение задачи.

5. Проверяют, удовлетворяют ли координаты найденной точки системе ограничений задачи. Если нет, то переходят к следующему этапу. Если координаты найденной точки удовлетворяют системе ограничений, то исследуют необходимость перехода к последующему допустимому решению. В случае такой необходимости переходят к этапу 2, в противном случае найдено решение задачи с заданной точностью.

6. Устанавливают значение весовых коэффициентов и переходят к этапу 4.

Пример 5.5.

Найти максимальное значение функции

при условиях

Целевая функция данной задачи представляет собой отрицательно−определенную квадратичную форму, а ограничения – выпуклую область. Следовательно, имеем задачу выпуклого программирования. Построим область допустимых решений задачи и линии уровня (рисунок 5.5). Точка касания одной из этих окружностей с областью допустимых решений и является искомой точкой максимума целевой функции.

Рисунок 5.5 – Область допустимых значений

и линии уровня

В качестве начальной точки возьмем x⁽⁰⁾=(6,7) и положим λ=0,1. Определим частные производные:

Далее, используя формулу (5.34), построим последовательность точек для определения приемлемого решения.

Итерация 1.

Так как точка x⁽⁰⁾=(6,7) принадлежит области допустимых решений, то

,

.

Найдем . Так как , то точка  принадлежит допустимой области. В этой точке значение целевой функции .

Итерация 2.

; .

Итерация 3.

.

Итерация 4.

Точка не принадлежит допустимой области. Следовательно

=

= .

Аналогично получим:

.

Здесь возникает вопрос о выборе весового коэффициента a. Выберем его так, чтобы точка  не слишком далеко удалилась от границы допустимой области и вместе с тем принадлежала этой области. Этим требованиям удовлетворяет . Тогда ; ; ; .

Результаты вычислений приведены в таблице 5.3.

Таблица 5.3 – Результаты вычислений методом штрафных функций

K
1	(4,8; 5,6)	11,2	-54,4
2	(3,84; 4,48)	1,664	-34,816
3	(3,072; 3,584)	-9,0981
4	(3,950; 4,165)	0,660	-32,950
5	(3,16; 3,332)	-10,2
6	(3,987; 4,059)	0,272	-32,372
7	(3,189; 3,247)	-2,715
8	(3,999; 4,027)	-0,137	-32,185
9	(3,199; 3,219)	-10,744
10	(4,004; 4,012)	0,096	-32,128
11	(3,203; 3,210)	-10,781
12	(4,005; 4,008)	0,078	-32,104

Сравнивая значения целевой функции, полученные в 10-й и 12-й итерациях, видим, что они совпадают с точностью до 10^-1. Это говорит о близости точки  к точке максимума целевой функции. Исследуем теперь градиенты функций  и  в точке :

, .

  Вычислим отношения одноименных координат векторов: . Следовательно, векторы  и  практически коллинеарны. Полученное решение  при необходимости можно уточнить дальнейшими шагами до полной коллинеарности градиентов целевой и ограничительной функций.

В заключении заметим, что на практике используются несколько вариантов штрафных функций, а также то, что решение сложных задач нелинейного программирования градиентными методами связано с большим объемом вычислений и целесообразно только с использованием ЭВМ.