Тема 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) методом Франка-Вулфа включает следующие этапы:

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

2⁰. Находят градиент функции (11) в точке допустимого решения.

3⁰. Строят функцию (14) и находят ее максимальное значение при условиях (12) и (13).

4⁰. Определяют шаг вычислений.

5⁰. По формулам (15) находят компоненты нового допустимого решения.

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

Пример. Методом Франка-Вулфа найти решение задачи, состоящее в определении максимального значения функции

(16)

при условиях

(17)

(18)

Р е ш е н и е. Найдем градиент функции

и в качестве исходного допустимого решения задачи возьмем точку, а в качестве критерия оценки качества получаемого решения – неравенство, где =0,01.

I и т е р а ц и я. В точке градиент. Находим максимум функций

(18)

при условиях (17) и (18)

(20)

(21)

Задача (19) – (21) имеет оптимальный план (рис. 3.8).

Найдем новое допустимое решение исходной задачи по формуле (15):

, где (22)

подставив их вместо и их значения, получим

(23)

определим теперь число λ₁. Подставив в равенство (16) вместо их значения в соответствии с соотношениями (23)

,

найдем производную этой функции по λ₁ и приравняем её нулю:. Приравнивая находим. Следовательно,.

Таким образом, является искомым решением исходной задачи.

РАЗДЕЛ 3. СЕТЕВОЕ ПРОГРАММИРОВАНИЕ.

Дата добавления: 2014-01-15