Методы оптимизации. Харчистов Б.Ф. - 26 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

26
3. КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ
Задачей квадратичного программирования (КП) называет-
ся задача оптимизации с квадратичной целевой функцией и ли-
нейными ограничениями. Задача КП, в которой целевая функция
подлежит минимизации, имеет вид
.,1,0
,,1 ,
min,)(
1
111
njx
mibxa
xxdxcxf
j
ij
n
j
ij
n
j
n
k
kjjk
n
j
jj
=≥
=≤
→+=
∑
∑∑∑
=
===
Допустимое множество
X
является выпуклым, матрица
][
jk
dD =
предполагается симметричной неотрицательно опреде-
ленной. При этом )(
xf
является выпуклой на
X
и задача КП явля-
ется частным случаем задачи выпуклого программирования.
Для решения задачи КП используются необходимые усло-
вия Куна
−
Таккера, которые в силу выпуклости задачи КП ока-
зываются также достаточными для установления наличия реше-
ния.
Предварительно составляется функция Лагранжа
,)()(),(
1
∑
=
+=
m
i
ii
xgxfxL
λλ
где .)(
1
i
n
j
jijj
bxaxg −≡
∑
=
Условия Куна
−
Таккера имеют следующий вид:
;,1,0
),(
nj
x
xL
j
=≥
∂
∂
λ
(3.1)
;,1,0
njx
j
=≥
(3.2)
;,1,0
),(
nj
x
xL
x
j
j
==
∂
∂
λ
(3.3)

Страницы