т < N. Условие (10.6) будем записывать также в виде

Ах - В,

где А - матрица размера N х т. Во-вторых, координаты векторов ж неотрицательны:

1 > 0, х2 > 0,...,жлг > 0. (10.7)

Для решения задач квадратичного программирования разработано много различных методов (см., например, [27], [32], [36]). Вольф42 предложил метод, в котором задача квадратичного программирования сводится к задаче, похожей на задачу линейного программирования, но содержащей нелинейное ограничение. (Это ограничение приведено ниже как условие (10.9).) Для решения данной задачи используется симплексный метод. Ниже приведено описание этого подхода.

Через А обозначим матрицу, полученную транспонированием матрицы А. Скалярное произведение d-мерных векторов х = (жх, х2,..., xd) и у = (yi, у2, , уа) будем обозначать (ж,у) :

Теорема. Пусть координаты N-мерного вектора ж удовлетворяют условиям (10.6) и (10.7) и пусть существуют m-мерный вектор и = (щ, и2, , ит) и iV-мерный вектор v = (vi,v2,... ,vn), для которого

vi > 0, v2 > 0,...,vN > 0, (10.8)

42Wolfe P. The Simplex Method for Quadratic Programming Econometrica. V. 27. 1959. P. 382 - 398.

такие, что выполняются соотношения

(v,x) = О

(10.9)

2 С х - v + А-

и + Р = 0.

(10.10)

Тогда х является решением задачи квадратичного программирования (10.5) - (Ю.7), т. е. значение функции F в данной точке х не больше, чем в любой другой точке, удовлетворяющей условиям (10.6) и (10.7).

Доказательство. Пусть у - некоторый iV-мерный вектор, удовлетворяющей условиям (10.6) и (10.7). Мы покажем, что F(y) > F(x). Из неотрицательной определенности матрицы С следует, что

(у-х,С(у-х)) > 0.

Отсюда следует, что

(у, Су) + (х, Сх) > (х, Су) + (у, Сх) = 2 (х, Су).

Получаем

(У,Су)

(х, Сх) > 2 (х, С(у - х)) = 2 (Сх, у - х).

Поэтому

F(x) = (Р,у-х) + (у,Су) - (х, Сх) >

> (Р + 2Сх,у-х).

В силу (10.10)

Р + 2 Сх = v - Аи

F(y) - F(x) > {v - Ащу - х) =

= ( , У) ~ (w, ж) - (Аи, у) + (Аи, х) =

= (v, у) - (и, ж) - (и, Ау) + (и, Ах) = (v, у) > 0.

Последнее неравенство следует из того, что координаты векторов v ъ у неотрицательны. При предпоследнем переходе использовалось (10.9) и то, что

Ах = Ау = В.

Теорема доказана.

В силу доказанной теоремы для решения задачи квадратичного программирования (10.5) - (10.7) достаточно найти какие-нибудь вектора и, г; и ж, удовлетворяющие условиям (10.7) - (10.9) и системе линейных алгебраических уравнений

Ах = В,

(10.11)

2 Сх - v + Аи = -Р.

При найденном ж будет достигаться самое меньшее значение функции F, какое только возможно при соблюдении условий (10.6) и (10.7).

Для определения векторов и, г; и ж, удовлетворяющих условиям (Ю.7) - (10.9) и системе линейных алгебраических уравнений (10.11), необходимо решить еще одну задачу линейного программирования, к описанию которой мы переходим.

В этой задаче р = N + то, = 3 AT -f- 2 га. g-мерный вектор имеет вид

(x,v,ux,u2,z),