Page 170 - 6197

До задач квадратичного програмування належать такі
задачі, які мають лінійні обмеження, а критерій оптимальності
є нелінійною функцією
n n n
k 
min : R   x   c x  d x x , (3.40)
k
r
kr k
k 1  k 1 r 1
n
 a x  b , i  1,m , (3.41)
ik
i
k
k 1
x  0, k  1,n . (3.42)
k
Критерій оптимальності (3.40) запишемо у матрично-
векторній формі
T
T
R   x  c x  x Dx ,
d  d  d 
11 12 1n
 d d  d 
T
де c  c ,c , ,c n  , D   21 22 2n  ,
1
2
    
 
 d 1 n d n 2  d nn 
T
x  x ,x , ,x n  .
1
2
T
Функція x Dx є квадратичною формою, в якій D -
симетрична матриця. У тому випадку, коли матриця D
R
додатно означена, тоді функція   x є опуклою, а для таких
функцій локальний мінімум є глобальним мінімумом задачі.
Оскільки обмеження задачі (3.41) і (3.42) лінійні, то це
гарантує опуклість області допустимих розв’язків. Тому для
розв’язування задачі (3.40) – (3.42) можна використати
необхідні умови теореми Куна-Таккера. З огляду на те, що
R
функція   x є опуклою, а обмеження задачі утворюють
опуклу допустиму область, то необхідні умови теореми Куна-
Таккера будуть також і достатніми для встановлення
наявності мінімуму задачі (3.40) – (3.42).
Утворимо узагальнену функцію Лагранжа

170