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

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

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

при условиях

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

x_j ³0 (j =1,..., n). (2.12)

Характерной особенностью этой задачи является то, что ее система ограничений содержит только линейные неравенства.

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

Процесс нахождения решения задач начинается с определения точки, принадлежащей ОДР задачи.

Пусть эта точка X^(k), тогда в этой точке вычисляют градиент функции (2.10)

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

F = (2.13)

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

X^(k+1)=X^(k)+ l_k (Z^(k)–X^(k)), (2.14)

где l_k — некоторое число, называемое шагом вычислений и заключенное между нулем и единицей (0£ l_k £1).

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

Если его значение больше единицы, то следует положить l_k=1.

После определения числа l_k находят координаты точки X^(k+1), вычисляют значение целевой функции в ней и выясняют необходимость перехода к новой точке X^(k+2).

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

После конечного числа шагов получают с необходимой точностью решение исходной задачи.

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

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

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

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

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

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

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

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

(2.15)

при условиях

(2.16)

x₁, x₂ ³0. (2.17)

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

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

где e =0.01.

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

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

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

(2.19)

x₁, x₂ ³0. (2.20)

Задача (2.18)—(2.20) имеет оптимальный план Z⁽⁰⁾ =(0;4).

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

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

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

Определим теперь число l₁.

Подставив в равенство (2.15) вместо x₁ и x₂ их значения в соответствии с соотношениями (2.16)

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

Решая это уравнение, получим l₁ =1/4=0.25.

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

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

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

Метод штрафных функций. Рассмотрим задачу определения максимального значения вогнутой функции f(x₁,x₂,...,x_n)

при условиях

g_i(x₁,x₂,...,x_n) £ b_i (i=1,..., m), x_j ³0 (j =1,..., n), где g_i(x₁, x₂,..., x_n) — выпуклые функции.

Вместо того, чтобы непосредственно решать эту задачу, находят максимальное значение функции F(x₁,x₂,...,x_n)=f_i(x₁,x₂,...,x_n)+H(x₁,x₂,...,x_n), являющейся суммой целевой функции задачи, и некоторой функции H(x₁,x₂,..., x_n), определяемой системой ограничений и называемой штрафной функцией.

Штрафную функцию можно построить различными способами.

Наиболее часто она имеет вид

где

а a_i>0 — некоторые постоянные числа, представляющие

собой весовые коэффициенты.

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

(2.21)

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

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

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

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

2. Выбирают шаг вычислений.

6. Находят по всем переменным частные производные от целевой функции и функций, определяющих ОДР задачи.

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

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

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

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

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

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

(2.22)

при условиях

(2.23)

(2.24)

Р е ш е н и е. Целевая функция данной задачи представляет собой отрицательно-определенную квадратич-ную форму и, значит, вогнута.

В то же время ОДР задачи, определяемая ограничениями (2.23)—(2.24), — выпуклая.

Следовательно, задача (2.22)—(2.24) является задачей выпуклого программирования.

Для нахождения ее решения применим метод штрафных функций.

Прежде чем это сделать, построим ОДР задачи и линии уровня, определяемые целевой функцией (2.22).

Этими линиями служат окружности с центром в точке (0;0).

Точка касания одной из этих окружностей ОДР и является искомой точкой максимального значения целевой функции.

Положим X₀ =(6, 7).

Возьмем l=0, 1,

обозначим через

g (x₁, x₂) =18–(x₁ –7)²–(x₂ –7)²

и определим частные производные от функций f (x₁, x₂) и g (x₁, x₂) по переменным x₁ и x₂:

Теперь, используя формулу (2.21), приступаем к построению последовательности точек, одна из которых определит приемлемое решение.

1 итерация. Так как точка X₀ =(6,7) принадлежит ОДР задачи, то второе слагаемое в квадратных скобках формулы (2.21) равно нулю. Значит, координаты следующей точки X₁ вычисляем по формулам

Проверим теперь, принадлежит ли эта точка ОДР задачи. Для этого найдем g (X₁)=18–4,84–1,96=11,2. Так как g (X₁) >0, то X₁ принадлежит ОДР. В этой точке f (X₁)=–54,4.

2 итерация. Находим

f (X²)=– 34,816.

Проверяя таким образом остальные точки, на 12 итерации имеем:

Сравнивая значения целевой функции, найденные в точках, полученных после 10 и 12 итераций, видно, что они с точностью до 10^-1 совпадают. Это говорит о близости точки, найденной на последней итерации, к точке максимального значения целевой функции. Такой же вывод можно сделать, если исследовать векторы-градиенты функций f (X) и g (X) в точке X⁽¹²⁾.

В этой точке

Вычислим отношения одноименных координат векторов:

–8,01/5,99»–1,337;

–8,016/5,984»–1,339.

Как видно, они почти равны между собой.

Это означает, что векторы и практически коллинеарны.

Так как к тому же точка X⁽¹²⁾ находится вблизи границы ОДР (поскольку , то и можно считать приемлемым решением задачи.

Это решение при необходимости можно уточнить дальнейшими шагами до полной коллинеарности градиентов целевой и ограничительной функций.

Последовательность точек, получаемых во время нахождения решения задачи, наглядно иллюстрируется рис.(3.2).