Основні твердження та теореми

Означення 6.1. Множина W називається опуклою, якщо для довільних точок x, yW, та t [ 0,1 ] виконується tx +(1 – t) yW.

Означення 6.2. Функцiя H (x), xWEn, де W – опукла множина, називається опуклою, якщо для довільних точок x, yW та t [ 0,1 ] виконується нерівність H (tx+ (1 – t) y) tH (x) + (1 – t) H (y).

Теорема 6.1. Множина { x: H (x) 0 }, де H (x) опукла, є опуклою.

Теорема 6.2. Розріз опуклих множин є опуклою множиною.

Теорема 6.3. Квадратична функція F (x)= xDxТ+cxТ опукла, якщо матриця D – невід’ємно визначена.

Теорема 6.4. Матриця D – невід’ємно визначена, якщо всі її діагональ-ні мінори невід’ємні:

det (D (k)) 0, D (k)=|| d_ij ||, i,j=1,...k.

Теорема Куна-Таккера-1. Нехай допустима область

D ={ xEⁿ: G_i (x) 0,i=1,...,m, x0 }

задачі опуклого програмування задовольняють умову Слейтера: існує xD таке, що для всіх i=1,...,m G_i (x)< 0, тобто множина D має внутрішні точки. Тоді для того, щоб вектор x* був оптимальним розв’язком задачі опуклого програмування, необхідно i достатньо, щоб існував вектор u*0 такий, що пара (x*, u*) є сiдловою точкою функції Лагранжа:

L (x, u)= F (x)+(u₁G₁ (x) +...+ u_mG_m (x)),

x =(x₁,..., x_n) 0, u =(u₁,..., u_m) 0.

Кажуть, що точка (x*, u*) є сiдловою точкою функції L (x, u), якщо для всіх x0, u0 мають місце нерівності

L (x*, u) L (x*, u*) L (x, u*).

Теорема Куна-Таккера-2. Для неперервно диференцiйовних функцій F (x), G_i (x), i=1,...,m, теорема Куна-Таккера може бути переформульована таким чином. Вектор x* є оптимальним розв’язком задачі опуклого програмування тоді i лише тоді, коли існує вектор u* 0 такий, що для пари (x*, u*) виконуються умови:

xL (x*, u*) 0, xL (x*, u*)(x*) Т = 0, j=1,...,n,

uL (x*, u*) 0, uL (x*, u*)(u*) Т = 0, i=1,...,m.

Для задачі опуклого квадратичного програмування останні співвідношення набувають вигляду

c + 2xD + uA 0;

(c + 2xD + uA) xТ = 0;

xAТ – 0;

(xAТ – b) uТ = 0;

x 0, u 0.

Допомiжна ЗЛП для ЗОКП. Якщо ввести вектори y =(y1,..., yn) 0 та v =(v1,..., vm) 0, то вищенаведені співвідношення матимуть вигляд:

с + 2xD + uA – y = 0;

xAТ – b + v = 0;

y xТ = 0;

v uТ = 0;

x 0, u 0, y 0, v 0.

Зауважимо, що для випадку n= 2, m= 1 матимемо

2 d₁₁x₁+ 2 d₁₂x₂+ a₁₁u – y₁= – c₁,

2 d₁₂x₁+ 2 d₂₂x₂+ a₁₂u – y₂= – c₂,

a₁₁x₁+ a₁₂x₂+ v = a₁₀,

x₁y₁ = 0, x₂y₂ = y₂, u v = 0,

x₁, x₂, u, y₁, y₂, v 0.

Наведена вище система складається з n+m лінійних рівнянь щодо 2 (m+n) невідомих x_j, y_j (j=1,...,n), u_i, v_i (i=1,...,m). Крiм того повинні виконуватись такі умови: якщо x_j > 0, то y_j = 0, якщо y_j > 0, то x_j = 0, якщо u_i > 0, то v_i = 0, якщо v_i > 0, то u_i = 0.

Отже, шуканим розв’язком системи може бути довільний невід’ємний базисний її розв’язок, але такий, що змінні xj та yj (а також ui та vi) з однаковими індексами не можуть бути водночас базисними. Для відшукання такого розв’язку можна застосувати будь-який із відомих методів ЛП, зокрема, метод штучного базису. З цією метою запишемо досліджувану систему у вигляді

2xD + uA – y = – c;

xAТ + v = b.

Будемо вважати, що праві частини цієї системи невід’ємні: – c0, b0 (оскільки, в іншому випадку відповідні рівняння, їх праву i ліву частину досить помножити на – 1). Згiдно з методом штучного базису у кожне рівняння отриманої системи, яке не містить базисної змінної, вводимо штучну змінну. Оскiльки змінні v_i (i=1,...,m) можна вважати базисними, то штучні змінні z =(z₁,..., z_n) 0 вводимо тільки в перше рівняння вищенаведеної системи i розглядаємо допоміжну КЗЛП

ZiТmin,

2 xD + uAy + z = c;

xAТ + v = b;

x 0, u 0, y 0, v 0, z 0,

де i =(1,1,...,1) – n -вимірний одиничний вектор.

Квадратичний симплекс-метод. Описана вище задача розв’язується симплекс-методом. Якщо знайдений допустимий розв’язок цієї задачі задовольняє умови доповнювальної нежорсткостi, то він визначає оптимальний розв’язок вихідної ЗОКП. Iнакше треба перейти до нового розв’язку. При цьому до базисних включається нова змінна з нульовою оцінкою.

Симплекс-метод з умовами для розв’язування допоміжної КЗЛП, побудованої на основі вихідної задачі опуклого квадратичного програмування, i називають квадратичним симплекс-методом (алгоритм звичайного симплекс-методу. Якщо в оптимальному розв’язку допоміжної КЗЛП всі штучні змінні zj (j=1,...,n) приймають нульові значення, то, відкидаючи їх, отримаємо розв’язок, частина якого відповідає змінним початкової задачі опуклого квадратичного програмування, i буде її оптимальним розв’язком. Якщо ж в оптимальному розв’язку допоміжної КЗЛП значення хоча б однієї із штучних змінних відмінне від нуля, то система не має розв’язкiв, а, отже, множина сiдлових точок функції Лагранжа початкової задачі опуклого квадратичного програмування порожня.