Тема 2.2 градиентные методы.
Используя градиентные методы можно найти решения любой задачи нелинейного программирования. Однако в общем случае применение этих методов позволяет найти точку локального экстремума. Поэтому более целесообразно использовать градиентные методы для нахождения решения задач выпуклого программирования, в которых всякий локальный экстремум является одновременно глобальным. Процесс нахождения решения задачи с помощью с помощью градиентных методов состоит в том, что начиная с некоторой точки Х(k) осуществляется последовательный переход к некоторым другим точкам до тех пор, пока не выявляется приемлемое решение исходной задачи. При этом градиентные методы могут быть подразделены на две группы.
К первой группе относятся методы, при использовании которых исследуемые точки не выходят за пределы области допустимых решений задачи. Наиболее распространенным из таких методов является метод Франка-Вулфа.
Ко второй группе относятся методы, при использовании которых исследуемые точки могут как принадлежать, так и не принадлежать области допустимых решений. Однако в результате реализации итерационного процесса находится точка области допустимых решений, определяющая приемлемое решение. Из таких методов наиболее часто используется метод штрафных функции или метод Эрроу-Гурвица.
При
нахождении решения задач градиентными
методами, в том числе и названными
итерационный процесс осуществляется
до того момента, пока градиент функции
в очередной точке Х(k+1)
не
станет равным нулю или же пока
,
где
- достаточно малое положительное число,
характеризующее точность полученного
решения.
Остановимся более подробно на методах Франка-Вулфа, штрафных функций и Эрроу-Гурвица.
Метод Франка-Вулфа. Пусть требуется найти максимальное значение вогнутой функции.
(11)
при условиях
.
(13)
Характерной особенностью этой задачи является то, что ее система ограничений содержит только линейные неравенства. Эта способность является основой для замены в окрестности исследуемой точки нелинейной целевой функции линейной, благодаря чему решение исходной задачи сводится к последовательному решению задач линейного программирования.
Процесс нахождения решения задачи начинают с определения точки, принадлежащей области допустимых решений задачи. Пусть эта точка x(k), тогда в этой точке вычисляют градиент функции (11)
и строят линейную функцию
(14)
Затем находят максимальное значение этой функции при ограничениях (58) и (59). Пусть решение данной задачи определяется точкой Z(k). Тогда за новое допустимое решение исходной задачи принимают координаты точки x(k+1) :
(15)
где
λk
–некоторое число, называемое шагом
вычислений и заключенное между нулем
и единицей (0≤λk≤1).
Это число λk
берут произвольно или определяют таким
образом, чтобы значение функции в точке
f(
,
зависящее
от λk,
было
максимально. Для этого необходимо найти
решение уравнения
и выбрать его наименьший корень. Если
его значение больше единицы, то следует
положить λk=1.
После определения числа λk
находят координаты точки
,
вычисляют значение целевой функции в
ней и выясняют необходимость перехода
к новой точке
.
Если такая необходимость имеется, то
вычисляют в точке
градиент целевой функции, переходит к
соответствующей задаче линейного
программирования и находит ее решение.
Определяет координаты точки
и исследуют необходимость проведения
дальнейших вычислений. После конечного
числа шагов получают с необходимой
точностью решение исходной задачи.
Итак, процесс нахождения решения задачи (11) – (13) методом Франка-Вулфа включает следующие этапы:
10. Определяют исходное допустимое решение задачи.
20. Находят градиент функции (11) в точке допустимого решения.
30. Строят функцию (14) и находят ее максимальное значение при условиях (12) и (13).
40. Определяют шаг вычислений.
50. По формулам (15) находят компоненты нового допустимого решения.
60. Проверяют необходимость перехода к последующему допустимому решению. В случае необходимости переходят к этапу 20, в противном случае найдено приемлемое решение исходной задачи.
Пример. Методом Франка-Вулфа найти решение задачи, состоящее в определении максимального значения функции
(16)
при условиях
(17)
(18)
Р е ш е н и е. Найдем градиент функции
и
в качестве исходного допустимого решения
задачи возьмем точку
,
а в качестве критерия оценки качества
получаемого решения – неравенство
,
где
=0,01.
I
и т е р а ц и я . В точке
градиент
.
Находим максимум функций
(18)
при условиях (17) и (18)
(20)
(21)
Задача
(19) – (21) имеет оптимальный план
(рис. 3.8).
Найдем новое допустимое решение исходной задачи по формуле (15):
,
где
(22)
подставив
их вместо
и
их значения, получим
(23)
определим
теперь число λ1.
Подставив в равенство (16) вместо
их значения в соответствии с соотношениями
(23)
,
найдем
производную этой функции по λ1
и приравняем её нулю:
Решая это уравнение, получим
Поскольку найденное значение
заключено между 0 и 1, принимаем его за
величину шага. Таким образом,
.
II
и т е р а ц и я. Градиент целевой функции
исходной задачи в точке
есть
Находим максимум функции
при условиях (63) и (64). Решением является
.
Определяем
теперь
.
Последнее равенство перепишем следующим
образом:
(24)
Подставляя теперь в функцию (16) вместо их значения в соответствии с соотношениями (24), получаем
откуда
.
Приравнивая
нулю и решая полученное уравнение,
находим
.
Таким образом,
т.е.
.
III
и т е р а ц и я. Градиент функции f
в точке
есть
.
Находим максимум функции
при условиях (17) и (18). Решением является
.
Определяем
.
Имеем
.
Решая
уравнение
находим
.
Следовательно,
.
Таким
образом,
является искомым решением исходной
задачи.