Базис задачи квадратичногопрограммирования. Оптимальный и невырожденный базисы.
Поскольку ранг матрицы A
равен m
(см 3.1), система векторов
gif" alt="" />
являются линейно независимой системой векторов. В то же время, легко видно, что линейная оболочка, натянутая на систему векторов P
совпадает с пространством Em+n
, т.е L
(P)=En+m
.
Следовательно из системы векторов 3.2.4 можно образовать конечное число базисов N
евклидова пространства En+m
, содержащих в себе векторы P1, .. Pm
. Такие базисы пространства En+m
будем называть базисами задачи квадратичного программирования, и обозначать следующим образом:
|
|
(3.3.1)
|
Для упрощения схемы алгоритма, запишем базис (3.3.1) в следующем виде:
|
|
(3.3.2) |
Здесь Á
1
и Á
2
- наборы индексов. В случае, если Á
1
=
Á
2
будем считать базис UÁ1,Á2 порожденным одним множеством индексов Á
=
Á
1.
|
|
(3.3.3) |
Коэффициенты разложения вектора b
по базису UÁ1,Á2 будем называть базисными переменными, остальные коэффициенты - небазисными переменными.
Базис UÁ1,Á2 назовем оптимальным, если его базисные переменные удовлетворяют условиям Куна-Таккера (3.2.3).
Базис называется невырожденным, если все его базисные переменные, соответствующие компонентам вектора x
отличны от нуля, т.е.
|
|
(3.3.4) |
Задачу (3.1.2) будем называть невырожденной, если все ее базисы невырождены. В противном случае назовем задачу вырожденной.
