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

В общем случае под градиентными методами понимают методы, в которых направления движения к точке оптимума функции совпадают с направлением градиента этой функции. Используя градиентные методы, можно найти решение любой ЗНЛП. Однако в общем случае применение этих методов позволяет найти точку локального экстремума. Поэтому более целесообразно использовать градиентные методы для нахождения решения задач выпуклого программирования, в которых всякий локальный экстремум является одновременно и глобальным. Процесс нахождения решения задачи с помощью градиентных методов состоит в том, что начиная с некоторой точки X^(k) осуществляется последовательный переход к некоторым точкам до тех пор, пока не выявляется приемлемое решение исходной задачи. При этом градиентные методы могут быть подразделены на две группы.

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

При нахождении решения задач градиентными методами, в том числе и названными, итерационный процесс осуществляется до того момента, пока градиент функции f(x₁, x₂,..., x_n) в очередной точке X^(k+1) не станет равным нулю или же пока где  — достаточно малое положительное число, характеризующее точность полученного решения.

Метод Франка-Вулфа.

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

f (x₁, x₂, ..., x_n) (3.10)

при условиях

(i=1, ..., m), (3.11)

x_j0 (j=1, ..., n). (3.12)

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

Процесс нахождения решения задач начинается с определения точки, принадлежащей ОДР задачи. Пусть эта точка X^(k), тогда в этой точке вычисляют градиент функции (3.10)

и строят линейную функцию

F= (3.13)

Затем находят максимальное значение этой функции при ограничениях (3.10 — 3.11). Пусть решение данной задачи определяется точкой Z^(k) . Тогда за новое допустимое решение исходной задачи принимают координаты точки X^(k+1) :

X^(k+1)=X^(k)+ _k (Z^(k)–X^(k)), (3.14)

где _k — некоторое число, называемое шагом вычислений и заключенное между нулем и единицей (0 _k1). Это число _k берут произвольно или определяют таким образом, чтобы значение функции в точке X^(k+1) f(X^(k+1)), зависящее от _k, было максимальным. Для этого необходимо найти решение уравнения

и выбрать его наименьший корень. Если его значение больше единицы, то следует положить _k=1. После определения числа _k находят координаты точки X^(k+1), вычисляют значение целевой функции в ней и выясняют необходимость перехода к новой точке X^(k+2). Если такая необходимость имеется, то вычисляют в точке X^(k+1) градиент целевой функции, переходят к соответствующей ЗЛП и находят ее решение. Определяют координаты точки X^(k+2) и исследуют необходимость проведения дальнейших вычислений. После конечного числа шагов получают с необходимой точностью решение исходной задачи.

Итак, процесс нахождения решения задачи методом Франка-Вулфа включает следующие этапы:

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

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

3. Строят функцию (3.13) и находят ее максимальное значение при условиях (3.11 — 3.12).

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

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

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

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

(3.15)

при условиях

(3.16)

x₁, x₂0. (3.17)

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

и в качестве исходного допустимого решения задачи возьмем точку X⁽⁰⁾=(0; 0), а в качестве критерия оценки качества получаемого решения — неравенство

где =0.01.

1итерация. В точке X⁽⁰⁾ градиент f(X⁽⁰⁾)=(2; 4). Находим максимум функции

F₁=2x₁+4x₂ (3.18)

при условиях (2) и (3)

(3.19)

x₁, x₂0. (3.20)

Задача (3.18) — (3.20) имеет оптимальный план Z⁽⁰⁾=(0; 4). Найдем новое допустимое решение исходной задачи по формуле (3.14):

X⁽¹⁾=X⁽⁰⁾+₁(Z⁽⁰⁾-X⁽⁰⁾),

где 0₁1. Подставив вместо X⁽⁰⁾ и Z⁽⁰⁾ их значения, получим

Определим теперь число ₁. Подставив в равенство (3.15) вместо x₁ и x₂ их значения в соответствии с соотношениями (3.16)

найдем производную этой функции по ₁ и приравняем ее к нулю:

Решая это уравнение, получим ₁=1/4=0.25. Поскольку найденное значение ₁ заключено между 0 и 1, принимаем его за величину шага. Таким образом, X⁽¹⁾=(0; 1), f (X⁽¹⁾)=2, f (X⁽¹⁾)-f (X⁽⁰⁾)=2>=0,01.

Повторяя описанные выше действия, через две итерации приходим к тому, что ₃  0,007, X⁽³⁾=(0,99528; 0,96321), f (X⁽³⁾)=2,99957, f (X⁽³⁾)–f (X⁽²⁾)=2,99957–2,9966=0,00297<=0,01.

Таким образом, X⁽³⁾=(0,99528; 0,96321) является искомым решением исходной задачи.