Метод Франка-Вульфа розв’язання задач квадратичного

програмування (ЗКП)

У матричній формі ЗКП можна записати у вигляді

де D – симетрична, від’ємно визначена квадратна матриця коефіцієнтів квадратичної форми.

Як відомо, ізумов теореми Куна-Таккера випливає, що вектор X* буде розв’язком ЗКП тоді й тільки тоді, коли існують такі m -вимірні вектори l ³ 0 та W ³ 0 і n -вимірний вектор V =0, заяких виконуються умови:

C+DX–lA+V =0; b–AX–W =0; V^TX =0; W^T l=0.

Дві останні умови нелінійні (умови додаткової нежорсткості). Зних випливає, що меншою мірою n змінних з Х та V, а також m змінних з l та W мають перетворюватися у нуль. Звідси випливає, що для знаходження розв’язку ЗКП з від’ємно визначеною квадратичною формою досить розв’язати систему рівнянь і задовольнити умови додаткової нежорсткості.

Використовуючи метод штучного базису, формулюємо задачу:

Якщо у результаті її розв’язання вдалось вивести з базису усі штучні змінні і виконати умови додоткової нежорсткості, то знайде­ний базис­ний розв’язок буде розв’язком ЗКП. Розглянемо метод Франка-Вульфа.

Переформулюємо задачу: серед довільних базисних розв’язків системи знайти такий, який перетворює у нуль V^TX+l^TW. Розглянемо вектор

Z =(x₁,…,x_n, l₁,…,l_m, v₁,…,v_n, w₁,…,w_m)

тавектор

=(v₁,…,v_n, w₁,…,w_m, x₁,…,x_n, l₁,…,l_m).

Тоді:

V^TX+W^Tl = Z^T ® min,

BZ=d, Z ³ 0.

де

Виконаємо ряд ітерацій так, щоб опукла функція T (Z) = Z^TZ мінімізувалася за таким рекурентним правилом: у результаті к -го кроку маємо довільний розв’язок Z^k, що відповідає системі обмежень задачі, а також довільний розв’язок w^k, який задовольняє ті самі обмеження, але не обов’язково буде базисним. Йому відповідає до­датне значення T(Z) ( на першому кроці w⁰ = Z ^). Починаючи з базисного розв’язку Z^k, мінімізуємо лінійну відносно Z форму (Z^k)^Tw^k. Маємо послідовність базисних розв’яз-ківZ⁰=Z^k, Z¹, Z²,..., причому (Z⁰)^Tw^k > (Z¹)^Tw^k. Обчислення закінчується, якщо

а) (Z^h)^{T h} =0;

б) (Z^h)^Tw^k £ (w^k)^{T k}.

У випадку а) Z^k – розв’язок ЗКП, а у випадку б) знаходимо

Z^k+1=Z^k; w^k+1=w^k+m (Z^k+1–w^k),

m=min

На кожному кроці маємо або а), або б), однак через певну кількість кроків будемо мати тільки а).

Приклад 6.3. Розв’язати ЗКП методом Франка - Вульфа:

10 x₁ +20 x₂ –2 x₁² –2 x₂² + x₁x₂ ® max,

x₁+x₂ £ 10,

x₂ £ 4,

x₁ ³ 0, x₂ ³ 0.

Матриця D має вигляд

D =

Оскільки знаки її мінорів змінюються спочатку «–» потім «+» то відповідно критерію Сільвестра цільова функція буде вгнутою.

Запишемо функцію Лагранжа квадратичної задачі

L (X,l)=10 x₁ +20 x₂ –2 x₁² –2 x₂ ²+ x₁x₂ + l₁ (10 –x₁–x₂)+ l₂ (4– x₂).

Умови теореми Куна-Таккера мають вигляд:

1. = 10– 4 x₁+ x₂– l ₁ £ 0; 2. x₁ = x₁ (10– 4 x₁+ x₂– l ₁) = 0;

= 20– 4 x₂– l ₁– l₂ £ 0; x₂ = x₂ (20– 4 x₂– l ₁– l₂) = 0;

= 10 – x₁– x₂ ³ 0; l₁ = l₁ (10– x₁– x₂) = 0;

= 4 – x₂ ³ 0; l₂ = l₂ (4– x₂ ) = 0.

Треба знайти такий розв’язок системи умови 1, який одночасно задовольнив би і систему 2. Перепишемо систему 1 у вигляді:

4 x₁–x₂+l₁ ³ 10,

–x₁ +4 x₂+l₁+l₂ ³ 20,

x₁+x₂ £ 10,

x₂ £ 4.

Вводячи у цю систему обмежень невід’ємні додаткові змінні V₁, V₂, W₁, W₂ дістаємо

4 x₁– x₂+ l₁– V₁ = 10,

– x₁ + 4 x₂+l₁+ l₂– V₂ = 20,

x₁+ x₂ + W₁ = 10,

x₂ + W₂ = 4.

При цьому мають виконуватись умови додаткової нежорстокості

x₁V₁ = 0, x₂V₂ = 0, l₁W₁ = 0, l₂W₂ = 0.

Запишемо вектор Z = (z₁ , z₂ , z₃ , z₄ , z_­5 , z₆ , z₇ , z₈) у вигляді:

Z=(x₁,x₂, l₁, l₂, v₁, v₂, W₁, W₂),

та вектор , у вигляді

.

Далі запишемо V^TX+W^Tl=Z^T /2.

Тепер задачу можна зобразити у вигляді:

Z^T ® min; BZ = d; Z ³ 0,

де

4 –1 1 0 –1 0 0 0 10

B = –1 4 1 1 0 –1 0 0, d = 20.

1 1 0 0 0 0 1 0 10

0 1 0 0 0 0 0 1 4

Для знаходження довільного базисного розв’язку використаємо метод штучних змінних. Введемо в систему обмежень штучну змінну U₁ = Z_g і запишемо цільову функцію = Mz_g ® min і початкову симплекс-таблицю у вигляді табл. 6.1.

Таблиця 6.1

i	Б	С	Z1
z1	z2	z3	z4	z5	z6	Z7	z8
	z9	M			-1			-1
	z4			-1					-1
	z7
	z8
m+2					-1			-1

Зробимо крок симплексних перетворень і дістанемо табл. 6.2.

Таблиця 6.2

i	Б	С	Z2
z1	z2	z3	z4	z5	z6	z7	z8
	z1		5/2		-1/4	1/4		-1/4
	z4		45/2		15/4	5/4		-1/4	-1
	z7		15/2		5/4			1/4
	z8
m+ 2

Для перeвірки умов додаткової нежорстокості розглянемо вектори

Z² = =

Оскільки (Z²)^TZ² ¹ 0˜ то разом з табл. 6.2 знайшли довільний розв’язок w⁰=Z⁰=Z⁰. Починаючи з нього мінімізуємо лінійну щодо Z функцію:

Табл. 6.3 випливає безпосередньо з табл. 6.2.

Таблиця 6.3

I	Б	С	Z 1			15/2		5/2			45/2
z1	z2	z3	z4	z5	z6	z7	z8
	z1		5/2		-1/4	1/4		-1/4
	z4		45/2		15/4	5/4		-1/4	-1
	z7		15/2		5/4			1/4
	z8	45/2
m +1			i	Б	С	Z0		-7/2	-4

Вибравши другий стовпець і четвертий рядок ведучими, робимо крок симплексного виключення і переходимо до нової таблиці 6.4

Таблиця 6.4

I	Б	С	Z 1			15/2		5/2			45/2
z1	z2	z3	z4	z5	Z6	Z7	z8
	z1		7/2
	z4		15/2
	z7		5/2
	z2
m +1

Оскільки то перевіряємо умови додаткової нежорстокості

= ;

=

Вони виконуються оскільки (Z¹)^TZ¹ = 0. Таким чином знайдемо оптимальний розв’язок ЗКП:

X^* = ; F (X^*) = 62,5.