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

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

min Z = f(X) = f(x₁, x₂,...,x_n),

где f(X) – выпуклая функция.

I шаг. Считаем, что исходное допустимое решение X⁰(x⁰₁, x⁰₂,...,x⁰_n) найдено.

II шаг.

I. Направление спуска Y ищется в следующем виде

Y=(X - X⁰)=(x₁-x⁰₁, x₂-x⁰₂,...,x_n-x⁰_n), где X(x₁, x₂,...,x_n)  ,  - область допустимых решений (ОДР). Y = X - X⁰ . Необходимо найти координаты точки X(x₁, x₂,...,x_n) такой, чтобы: 1) grad Z  Y = grad Z  (X - X⁰ ) < 0, при этом Z убывает; 2) кроме того X(x₁, x₂,...,x_n)  .

II. Составим вспомогательную задачу.

Запишем min Z = grad Z(X⁰)  Y = grad Z(X⁰ )  (X - X⁰ ) =

= [Z(X⁰)/(x₁)] (x₁-x⁰₁) + [Z(X⁰)/(x₂)] (x₂-x⁰₂) + [Z(X⁰)/(x₃)] (x₃-x⁰₃) + ∙∙∙ +[Z(X⁰) (x_n)] (x_n-x⁰_n)

, i = 1  m.

X(x₁, x₂,...,x_n)  0.

3. Решаем вспомогательную задачу, являющуюся задачей линейного программирования постоянных размеров.

Так как ищется min Z = grad Z(X⁰)  Y = grad Z(X⁰ )  (X - X⁰ ), то при отрицательном значении Z во вспомогательной задаче в окрестности точки X⁰ целевая функция f(X) по направлению Y = X - X⁰ будет убывать. Этот минимум ищется с учетом системы ограничений. Система ограничений с условием неотрицательности переменных требует, чтобы точки X и X⁰ принадлежали области допустимых решений. Вспомогательная задача линейного программирования позволяет среди всех направлений спуска выбрать направление с максимально возможным спуском. Таким образом, определение направления спуска сводится к определению координат точки X(x₁, x₂,...,x_n). Эти решения можно получить, решая вспомогательную задачу любым известным методом (графическим, симплексным, двойственным и так далее).

III шаг. Движение по направлению спуска осуществляется шагами до тех пор, пока функция убывает. Точка X^* c минимальным значением направления спуска принимается за начальную (исходную) X⁰ для следующего приближения Х тек. = X⁰ +t ·Y = X⁰ +t · (X - X⁰ ), где t[0, 1].

IV шаг. Критерий оптимальности - признак оптимальности решения.

Первый признак. Градиент целевой функции равен нулю grad f(X⁰) = 0. Это условие является необходимым условием экстремума функции без ограничений. Более подробная и привычная запись - система дифференциальных уравнений:

f(X⁰)/(x₁) = 0;

f(X⁰)/(x₂) = 0;

f(X⁰)/(x₃) = 0;

……………….

f(X⁰)/ (x_n) = 0.

Так как в задаче выпуклого программирования любой локальный минимум совпадает с глобальным (абсолютным), то необходимое условие экстремума функции можно принять в качестве признака (критерия) оптимальности. Классические методы математики позволяют выявить, является ли седловая точка точкой минимума, точкой максимума или точкой перегиба. При решении на ПК получить точное равенство нулю очень трудно, поэтому при расчетах принимают |f(X⁰)/(x_j)| ≤ ε (j = 1  n), где ε – малая величина, заданная точность расчета.

Второй признак. Расстояние между двумя точками (между двумя последовательно полученными приближенными решениями) меньше либо равно заданного числа – точности расчета ε: |X⁰_t - X⁰_t+1 | ≤ ε.

Второй признак (критерий) может считаться основным, так как он включает в себя первый признак (критерий), как частный случай.

Укрупненная схема алгоритма

1. Определение исходного (начального) допустимого решения.

2. Формулировка и решение вспомогательной задачи линейного программирования постоянных размеров. Нахождение вектора Y. Y = X - X⁰ .

3. Определение величины шага по направлению Y, задача на поиск минимума функции от одной переменной.

4. Признак (критерий) оптимальности. Если решение не оптимально, то переход к пункту 2.

Пример 14. min Z = х₁²+х₂²

х₁+х₂ ≤ 2

х₁ ≤ 2

х₂ ≤ 1

х₁  0, х₂  0

Выполним решение по блокам схемы.

I шаг. Возьмем за начальную точку приближения исходное допустимое решение X⁰(1;1). Зададим точность расчета ε = 0,02.

II шаг.

1) Найдем grad Z(X) в общем виде: grad Z(X ) =

={ Z(X)/(x₁);  Z(X)/(x₂)} = {2x₁; 2x₂}.

Вычислим значение grad Z в точке X⁰ gradZ(X⁰)={2 · 1;2 · 1}={2; 2}.

2) Составим вспомогательную задачу линейного программирования. Определим целевую функцию

min Z_всп = grad Z(X⁰)  Y = grad Z(X⁰ )  (X - X⁰ ) = [Z(X⁰)/(x₁)] (x₁-x⁰₁) + +[Z(X⁰)/(x₂)] (x₂-x⁰₂) ={2; 2}· [(x₁-1); (x₂-1)] = 2x₁ –2+2x₂ –2 = 2x₁ +2x₂ –4.

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

min Z_всп = 2x₁ +2x₂ –4.

х₁+х₂ ≤ 2

х₁ ≤ 2

х₂ ≤ 1

х₁  0, х₂  0.

3) Решаем вспомогательную задачу, являющуюся задачей линейного программирования постоянных размеров.

Решим вспомогательную задачу графическим методом:

1) х₁+х₂ ≤ 2 – полуплоскость;

х₁+х₂ = 2 - граничная прямая. Строим ее по двум точкам.

хj	Первая точка	Вторая точка
х1	0	2
х2	2	0

Точка «начало координат» (0,0) принадлежит полуплоскости.

2) х₁ ≤ 2, точка (0,0) принадлежит полуплоскости.

3) х₂ ≤ 2, точка (0,0) принадлежит полуплоскости.

Рис. 8. Решение вспомогательной задачи графическим методом

4) х₁  0,

х₂  0 I четверть.

5) Область допустимых решений - четырехугольник ABCD.

6) Z _всп = 2x₁ +2x₂ –4 – целевая функция

antigrad Z _всп = - grad Z _всп ={(Z)/(x₁); (Z)/(x₂)} = {2; 2 }. Начало вектора антиградиента – начало координат, точка (0; 0). Конец вектора антиградиента – точка (2; 2). Вектор антиградиент показывает направление минимизации.

7) Строим линию уровня Z = 2x₁ + 2x₂ – 4 = const, перпендикулярную вектору антиградиенту. Таких линий уровня бесчисленное множество. Все они параллельны между собой. Перемещаем линию уровня в направлении вектора антиградиента до первого соприкосновения с областью допустимых решений ABCD. Первое соприкосновение - точка A(0;0) – оптимальное решение, в котором вспомогательная задача имеет минимальное значение: min Z_всп (A)= Z_всп (0;0)= 2  0 +2  0 – 4 = - 4. Следовательно, направление спуска есть, так как скалярное произведение grad Z(X)  Y = grad Z(X)  (X - X⁰ ) = {2; 2}· [(0 - 1); (0 - 1)] = -4 имеет отрицательное значение. Точка X^*(0,0) оптимальное решение вспомогательной задачи.

I

)

II шаг. Движение по направлению спуска осуществляется шагами до тех пор, пока функция убывает. Точка X^* c минимальным значением направления спуска принимается за начальную (исходную) для следующего приближения .

Находим координаты текущей точки приближения

Х тек. = X⁰ +t ·Y = X⁰ +t · (X - X⁰ ), где t[0, 1], а точка X⁰ = (1;1).

Общий вид приближения Х тек. = (1;1) +t ·[(x₁-1); (x₂-1)], где t[0, 1].

x_1тек = 1 + t · (x₁-1);

x_2тек = 1 + t · (x₂-1);

Х тек. = [x_1тек; x_2тек ] = [1 + t · (x₁-1); 1 + t · (x₂-1) ].

Однако из решения вспомогательной задачи мы нашли, что решение вектор X имеет значение Х (x₁; x₂), так как Х (0; 0) – оптимальное решение вспомогательной задачи. Подставим в Х тек. значение точек X⁰ (1;1) и Х (0; 0), получим x_1тек = 1 + t · (0 - 1);

x_2тек = 1 + t · (x₂ - 1);

Х тек. = [x_1тек; x_2тек ] = [1 + t · (0 - 1); 1 + t · (0 - 1) ] или

x_1тек = 1 - t; x_2тек = 1 - t;

имеем Х тек. = [x_1тек; x_2тек ] = [1 - t; 1 - t ].

Составим таблицу нахождения текущих точек, меняющихся в зависимости от значения t, t[0, 1].

Таблица 4

Нахождение текущих точек

Номер текущей точки	Значение t[0, 1].	Координаты текущей точки Х тек.		Значение целевой функции основной задачи Z = х12+х22
		x1тек = 1 - t;	x2тек = 1 - t;
1	0	1	1	2
2	0,5	0,5	0,5	0,5
3	0,7	0,3	0,3	0,18
4	1	0	0	0

Точка Х(0,0) при t=1 является начальной точкой для следующего приближения, то есть является X⁰ (0; 0). Проверяем эту точку на признак (критерий) оптимальности, для этого находим  Z(X)/(x₁);  Z(X)/(x₂) в точке X⁰ основной задачи.

 Z(X)/(x₁) =2· х₁;  Z(X⁰)/(x₁) = 2 · 0 = 0;

 Z(X)/(x₂) =2· х₂;  Z(X⁰)/(x₂) = 2 · 0 = 0;

По первому признаку (критерию) получено оптимальное решение X^* (0; 0). Проверим решение по второму признаку (критерию)

min Z_всп (X⁰) = grad Z(X⁰)  Y = grad Z(X⁰ )  (X - X⁰ ) = [ Z(X⁰)/(x₁)] (x₁-x⁰₁) + +[ Z(X⁰)/(x₂)] (x₂-x⁰₂) ={0; 0}· [(x₁-0); (x₂-0)] = 0

х₁+х₂ ≤ 2

х₁ ≤ 2

х₂ ≤ 1

х₁  0, х₂  0.

Получили, что Z_всп (X⁰) = 0, не зависит от Х, направления спуска нет. Поэтому любое допустимое решение является оптимальным. Например, возьмем за оптимальное решение X^опт = X^* (2; 0).

Переходим к отысканию координат текущей точки Х тек. = X⁰ +t ·Y = X⁰ +t · (X - X⁰ ), где t[0, 1], а точка X⁰ = (0;0),

получим x_1тек = 0 + t · (х₁ - 0); x_2тек = 0 + t · (x₂-0);

Х тек. = [x_1тек; x_2тек ] = [0 + t · (х₁ - 0); 0 + t · (х₂ -0) ] или

x_1тек = t · х₁; x_2тек = t · х₂;

имеем Х _тек. = [x_1тек; x_2тек ] = [ t · х₁; t · х₂ ].

Подставляем в Х _тек. = [x_1тек; x_2тек ] = [ t · х₁; t · х₂ ] координаты точки X^* (2; 0), которую мы приняли за X^опт . Получаем Х тек. (2·t ; 0· t).

Составим таблицу нахождения текущих точек, меняющихся в зависимости от значения t, t[0, 1] и X⁰ = (0;0).

Таблица 5

Нахождение текущих точек

Номер текущей точки	Значение t[0, 1].	Координаты текущей точки Х тек.		Значение целевой функции основной задачи Z = х12+х22
		x1тек = 2·t	x2тек = 0
1	0	0	0	0
2	0,01	0,02	0	0,0004
3	0,1	0,2	0	0,04
…	…	…	…	…

Проверим полученные решения Х _{тек. t} по второму признаку (критерию) оптимальности: |X⁰_t - X⁰_t+1 | ≤ ε, где ε = 0,02 ?

|X⁰_t - X⁰_t+1 | = |X⁰_t - X⁰ | = √[ (x_1t-x₁⁰)² + (x_2t-x₂⁰)² ].

|X⁰₁ - X⁰ | = √[ (0 - 0)² + (0 - 0)² ] = 0; 0 <0,02 = ε, испытание удачное.

|X⁰₂ - X⁰ | = √[ (0,02 - 0)² + (0 - 0)² ] = √ 0,0004 = 0,02; 0,02=0,02= ε, испытание удачное.

|X⁰₃ - X⁰ | = √[ (0,2 - 0)² + (0 - 0)² ] = √ 0,04 = 0,2; 0,2>0,02= ε, испытание неудачное.

Примем за оптимальное решение точку X^опт = X^* (0,02; 0). Но точка X⁰₁(0;0) тоже удовлетворяет второму признаку (критерию). Кроме того, она удовлетворяет первому признаку оптимальности (критерию), поэтому ее и необходимо принять за оптимальное решение.

Замечание. В отличие от алгоритма общей задачи выпуклого программирования алгоритм решения специальной задачи выпуклого программирования обладает следующей особенностью: вспомогательная задача линейного программирования имеет постоянную размерность и не надо решать нелинейные уравнения. Это существенно упрощает программирование алгоритма для реализации решения на ПК.

П ример 15

min Z =9х₁²+9х₂² +12х₁ - 6х₂

0 ≤ х₁ ≤ 4

1 ≤ х₂ ≤ 5

х₁  0, х₂  0

Выполним решение по блокам схемы.

I шаг. Возьмем за начальную точку приближения исходное допустимое решение X⁰(3;4). Зададим точность расчета ε = 0,02.

II шаг.

1) Найдем grad Z(X) в общем виде:

grad Z(X ) ={ Z(X)/(x₁);  Z(X)/(x₂)} = {18x₁+12; 18x₂ - 6}.

Вычислим значение grad Z в точке X⁰:

grad Z(X⁰) = {18 · 3+12+18 · 4 - 6}=132.

2) Составим вспомогательную задачу линейного программирования. Определим целевую функцию

min Z_всп = grad Z(X⁰)  Y = grad Z(X⁰ )  (X - X⁰ ) = [Z(X⁰)/(x₁)] (x₁-x⁰₁) + +[Z(X⁰)/(x₂)]  (x₂-x⁰₂) ={18·3+12; 18·4 - 6}· [(x₁-3); (x₂-4)] ={66; 66}· [(x₁ -

-3); (x₂-4)] = 66x₁ –198 + 66x₂ –264 = 66x₁ +66x₂ –462.

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

m in Z_всп = 66x₁ +66x₂ –462.

0 ≤ х₁ ≤ 4

1 ≤ х₂ ≤ 5

х₁  0, х₂  0

3) Решаем вспомогательную задачу, являющуюся задачей линейного программирования постоянных размеров.

Решим вспомогательную задачу графическим методом:

1. х₁ ≤ 4 – полуплоскость;

х₁ = 4 - граничная прямая, проходящая через точку (4;0), параллельно оси ОХ₂. Точка «начало координат» (0,0) принадлежит полуплоскости.

2. х₂ ≤ 5 – полуплоскость;

х₂ = 5 - граничная прямая, проходящая через точку (0;5), параллельно оси ОХ₁. Точка (0,0) принадлежит полуплоскости.

3. х₂  1 – полуплоскость;

х₂ = 1 - граничная прямая, проходящая через точку (0;1), параллельно оси ОХ₁. Точка (0,0) не принадлежит полуплоскости.

4 . х₁  0,

х₂  0, I четверть.

5. Область допустимых решений - четырехугольник ABCD.

6. Z_всп = 66x₁ +66x₂ –462 – целевая функция

antigrad Z _всп = - grad Z _всп ={(Z)/(x1); (Z)/(x2)} = {66; 66}. Начало вектора антиградиента – начало координат, точка (0; 0). Конец вектора антиградиента – точка (66; 66). Можно вектор антиградиент масштабировать в 11 раз, тогда конец вектора антиградиента – точка (6; 6). Вектор антиградиент показывает направление минимизации.

7. Строим линию уровня Z = 66x₁ +66x₂ – 462 = const, перпендикулярную вектору антиградиенту. Таких линий уровня бесчисленное множество. Все они параллельны между собой. Перемещаем линию уровня в направлении вектора антиградиента до первого соприкосновения с областью допустимых решений ABCD. Первое соприкосновение - точка A(0;1) – оптимальное решение, в котором вспомогательная задача имеет минимальное значение: min Z_всп (A)= Z_всп (0;1)= 66  0 +66  1 – 462 = - 396 < 0. Следовательно, направление спуска есть, так как скалярное произведение grad Z(X)  Y = grad Z(X)  (X - X⁰ ) ={18x₁+12; 18x₂ - 6}· [(x₁-3); (x₂-4)]= 66x₁ +66x₂ – 462 = 66  0 +66  1 –462 = - 396 имеет отрицательное значение. Точка X^*(0,1) - оптимальное решение вспомогательной задачи.

III шаг. Движение по направлению спуска осуществляется шагами до тех пор, пока функция убывает. Точка X^* c минимальным значением направления спуска принимается за начальную (исходную) для следующего приближения.

Находим координаты текущей точки приближения

Х тек. = X⁰ +t ·Y = X⁰ +t · (X - X⁰ ), где t[0, 1], а точка X⁰ = (3;4).

Общий вид приближения Х тек. = [(3;4) +t ·[(x₁-3); (x₂-4)], где t[0, 1].

Рис. 9. Решение графическим методом вспомогательной задачи

x_1тек = 3 + t · (x₁-3);

x_2тек = 4 + t · (x₂-4);

Х _тек. = [x_1тек; x_2тек ] = [3 + t · (x₁-3); 4 + t · (x₂-4) ].

Однако из решения вспомогательной задачи мы нашли, что решение X имеет значение Х (x₁; x₂), так как Х(0; 1) – оптимальное решение вспомогательной задачи. Подставим в Х _тек. значение точек X⁰ (3;4) и Х(0; 1), получим x_1тек = 3 + t · (0-3);

x_2тек = 4 + t · (1-4);

Х тек. = [x_1тек; x_2тек ] = [3 + t · (0-3); 4 + t · (1-4) ] или

x_1тек = 3 - 3t; x_2тек = 4 - 3t; имеем

Х тек. = [x_1тек; x_2тек ] = [3 - 3t; 4 - 3t].

Составим таблицу нахождения текущих точек, меняющихся в зависимости от значения t, t[0, 1].

Таблица 6

Нахождение текущих точек

Номер текущей точки	Значение t[0, 1].	Координаты текущей точки Х тек.		Значение целевой функции основной задачи Z = = 9х12+9х22+12 х1-6 х2
		x1тек = 3 - 3t;	x2тек = 4 -3t;
1	0	3	4	237
2	0,4	1,8	2,8	118,12
3	0,8	0,6	1,6	29,08
4	1	0	1	3

Точка Х(0,1) при t=1 является начальной точкой для следующего приближения, то есть является X⁰ (0; 1). Проверяем эту точку на критерий оптимальности, для этого находим Z(X)/(x₁); Z(X)/(x₂) в точке X⁰ основной задачи.

 Z(X)/(x₁) =18· х₁ + 12; Z(X⁰)/(x₁) = 18 · 0 + 12= 12;

Z(X⁰)/(x₂) =18· х₂ - 6; Z(X⁰)/(x₂) = 18 · 1 - 6 = 12.

По первому признаку (критерию) получено оптимальное решение X^* (0; 1). Проверим решение по второму признаку (критерию):

min Z_всп (X⁰) = grad Z(X⁰)  Y = grad Z(X⁰)  (X - X⁰) = [Z(X⁰)/(x₁)] (x₁-x⁰₁) + [Z(X⁰)/(x₂)] (x₂-x⁰₂) ={12; 12}· [(x₁-0); (x₂-1)] ={12 x₁; 12 x₂ -12}

min Z_всп = 12 x₁+ 12 x₂ -12

min Z_всп = 12· 0+ 12· 1 –12 =0

Получили , что Z_всп (X⁰) = 0, не зависит от Х, направления спуска нет. Поэтому любое допустимое решение является оптимальным. Например, возьмем за оптимальное решение X^опт = X^* (2; 0).

Переходим к отысканию координат текущей точки Х тек. = X⁰ +t ·Y = X⁰ +t · (X - X⁰ ), где t[0, 1], а точка X⁰ = (0;1),

получим x_1тек = 0 + t · (х₁ - 0); x_2тек = 1 + t · (x₂-1);

Х тек. = [x_1тек; x_2тек ] = [0 + t · (х₁ -0); 1 + t · (х₂ -1) ] или

x_1тек = t · х₁; x_2тек = 1 + t · (х₂ -1);

имеем Х _тек. = [x_1тек; x_2тек ] = [ t · х₁; 1 + t · (х₂ -1)].

Подставляем в Х _тек. = [x_1тек; x_2тек ] = [ t · х₁; 1 + t · (х₂ -1) ] координаты точки X^* (2; 0), которую мы приняли за X^опт . Получаем Х тек. (2·t ; 1 + t · (0 -1) ) =(2·t ; 1 - t).

Составим таблицу нахождения текущих точек, меняющихся в зависимости от значения t, t[0, 1] и X⁰ = (0;1).

Таблица 7

Нахождение текущих точек

Номер текущей точки	Значение t[0, 1]	Координаты текущей точки Х тек.		Значение целевой функции основной задачи Z = 9х12+9х22+ +12х1 - 6х2
		x1тек =2·t	x2тек = 1 - t ;
0	-	0	1	3
1	0	0	1	3
2	0,01	0,02	0,99	3,2055
3	0,1	0,2	0,9	4,65
4	1	2	0	12

Точка Х(0,1) при t=0 является начальной точкой для следующего приближения, то есть является X⁰ (0; 1).

Проверим полученные решения Х_тек.t и Х_тек.t+1 по второму признаку оптимальности: |X⁰_t - X⁰_t+1 | ≤ ε, ε = 0,02?

|X⁰_t - X⁰_t+1 | = |X⁰_t - X⁰ | = √[ (x_1t-x₁⁰)² + (x_2t-x₂⁰)² ].

|X⁰₁ - X⁰ | = √[ (0 - 0)² + (1 - 1)² ] = 0; 0 <0,02 = ε, испытание удачное.

|X⁰₂ - X⁰₁ | = √[ (0 – 0,02)² + (1 – 0,99)² ] =√ 0,0004+0,0001=√ 0,0005; √ 0,0005 > 0,02 = ε, испытание неудачное.

|X⁰₃ - X⁰₂ | = √[ (0,02 – 0,2)² + (0,99 – 0,9)² ] =√0,0324+0,0081= √ 0,0405 > 0,02= ε, испытание неудачное.

|X⁰₄ - X⁰₃| = √[ (2 - 0,2)² + (0 – 0,9)² ] = =√3,24+0,81= √ 4,05 > 0,02= ε, испытание неудачное.

Примем за оптимальное решение точку X^опт = X^* (0; 1). Но точка X⁰₁(0;1) тоже удовлетворяет второму признаку (критерию)оптимальности; кроме того, она удовлетворяет первому признаку оптимальности (критерию), поэтому ее и необходимо принять за оптимальное решение.

min Z = 3, оптимальное решение X*(0;1)