Методы оптимизации. Азарнова Т.В - 59 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

61
0,
,342
,8054
min32)1
2
1
21
21
2
1
2
1
≥
≤+
≤+
→+−
xx
xx
xx
xxx
ix
xxx
xxx
xxx
i
∀≥
=++
=++
→++
,0
,342
,8054
min2)2
421
321
2
221
§ 7. Задача квадратичного программирования
Задачей квадратичного программирования называется задача
выпуклого программирования минимизации квадратичной функции на
допустимом множестве
Ω
, заданном линейными ограничениями
mincbxQxx
TT
→++
,
Ω
∈
x
,
где
)q(Q
ij
=
- симметричная положительно определенная матрица размера
n
n
×
,
b
- фиксированный вектор размера
n
,
c
- заданное число.
В данном параграфе рассмотрим задачу квадратичного
программирования вида
mincxbxq
2
1
)x(f
n
1j
jj
n
1i
n
1j
jij
→+
∑
+
∑∑
=
===
mixxg
i
n
j
jiji
,1,0)(
1
=≤β−α=
∑
=
njx
j
,1,0 =≤− .
Для данной задачи условной оптимизации можно рассмотреть
функцию Лагранжа вида
∑∑
==
=−µ+λ+=µλ
n
j
jj
m
i
ii
xxgxfxL
11
)()()(),,(
∑∑∑∑∑∑
======
−+
−+++=
n
j
jj
m
i
i
n
j
jiji
n
j
jj
n
i
n
j
jij
)x(xcxbxq
111111
2
1
µβαλ .
При этом условия Куна - Таккера запишутся в виде следующей
системы равенств и неравенств :
n,1j,0bxq
x
L
j
n
1i
ijij
n
1i
iij
j
==µ−
∑
αλ++
∑
=
∂
==
mix
L
i
n
j
jij
i
,1,0
1
=≤−
∑
=
∂
=
βα
λ
njx
L
j
j
,1,0 =≤−=
∂
µ
                                                  61
     1)   x12   −2 x1 +3 x 2 → min                     2) x1 +2 x 2 +x 22 → min
          4 x1 +5 x 2 ≤80,                               4 x1 +5 x 2 +x3 =80,
          2 x1 +x 2 ≤34,                                 2 x1 +x 2 + x 4 =34,
          x1 , x 2 ≥0                                    xi ≥0, ∀i

   § 7. Задача квадратичного программирования
      Задачей квадратичного программирования называется                   задача
выпуклого программирования минимизации квадратичной функции на
допустимом множестве Ω , заданном линейными ограничениями
                               x T Qx +bx T +c → min ,
                                          x ∈Ω ,
где Q =( q ij ) - симметричная положительно определенная матрица размера
n ×n , b - фиксированный вектор размера n , c - заданное число.
      В     данном        параграфе        рассмотрим       задачу квадратичного
программирования вида
                               1 n n           n
                      f ( x ) = ∑ ∑ q ij x j +∑ b j x j +c → min
                               2 i=1 j=1      j=1
                                        n
                              g i ( x) = ∑ αij x j −βi ≤0, i =1, m
                                       j =1

                       −x j ≤0, j =1, n .
     Для данной задачи условной оптимизации можно рассмотреть
функцию Лагранжа вида
                                              m                n
                        L( x, λ, µ) = f ( x) +∑ λi g i ( x) + ∑ µ j (−x j ) =
                                              i =1            j =1
         1 n n                 n             m
                                                  � n           �    n
       = ∑ ∑ q ij x j +∑ b j x j +c +∑ λi � ∑ α ij x j −βi � +∑ µ j ( −x j ) .
          2 i =1 j =1         j =1          i =1   � j =1         � j =1

     При этом условия Куна - Таккера запишутся в виде следующей
системы равенств и неравенств:
                      ∂L     n                 n
                          =∑ q ij x i +b j +∑ λ i α ij −µ j =0, j =1, n
                      ∂x j i =1              i =1




                              ∂L    n
                                 = ∑ α ij x j −βi ≤0, i =1, m
                              ∂λi j =1
                                  ∂L
                                       =−x j ≤0, j =1, n
                                 ∂µ j

Страницы