достигает своего минимального значения. Координаты вектора х должны удовлетворять условиям

а;,ж; = 6j, j = 1,2,...,то, *=i

(9.2)

xi > 0, ж2 > 0,... хм > 0.

Т. е. функция (9.1) минимизируется на множестве векторов, удовлетворяющих условиям (9.2).

Коэффициенты линейной формы из (9.1) Е\, Е2, , Ец могут быть произвольными, а квадратичная форма является неотрицательно определенной. Это означает, что для любого ЛГ-мерного вектора х - (хх, ж2,..., х)

N N

J2 Е Сц > о.

=1 j=l

Задачи такого типа называются задачами квадратичного программирования.

Чтобы связать эту задачу с задачей (3.3), (3.2) из §3, можно считать, что при п < N выполняются условия Е{ = 0, если i > п, и Cij = 0, если г > п или j > п.

На первый взгляд условие (9.2) кажется менее общим, чем аналогичное условие (3.2) из §3, так как здесь нижними границами для всех переменных являются нули, а в §3 нижними границами, по крайней мере, для части переменных, могли быть произвольные числа. Но сделанное упрощение не является существенным. Мы могли и в условии (9.2) в качестве нижних границ взять произвольные числа, а затем сделать преобразования типа сдвигов, положив, например,

х\ - Xi - li, i = 1,2,..., п; х\ = Xi, i = п + 1,..., N.

При этом изменились бы коэффициенты линейной формы из (9.1) и правые части в уравнениях (9.2), но это не имеет принципиального значения. Мы не стали делать этих преобразований, чтобы не вводить новых обозначений.

Пусть и - m-мерный вектор. Определим функцию

Ф(ж,и) = -А£xi Ei+J2 xi хз Сч+Л Uk[h-J2aikXi j .

i=l i=l j=l fc=l V i=l /

Основным инструментом исследования в этом параграфе является следующая теорема, принадлежащая Куну и Так-керу.

Теорема. ЛГ-мерный вектор ж, удовлетворяющий условиям (9.2), тогда и только тогда является решением задачи квадратичного программирования (9.1) - (9.2), когда существует m-мерный вектор й такой, что

- (ж,й)>0, г = 1,2,...,АГ; (9.3) дФ

Xi--{x,u) = Q, г = 1,2,...,ЛГ. (9.4)

Доказательство теоремы Куна - Таккера можно найти, например, в [27], [36]37.

При А > 0 решение задачи квадратичного программирования (9.1), (9.2) обозначим через х(Х). Сделаем следующее предположение.

Условие 1. При любом А > 0 решение ж (А) задачи квадратичного программирования (9.1), (9.2) существует и единственно.

37На самом деле теоремой Куна - Таккера называется существенно более общее утверждение. Но мы сформулировали эту теорему в той общности, в какой она нам будет нужна.

На основании теоремы Куна - Таккера при любом А > О существует вектор и(Х) такой, что условия (9.3) и (9.4) выполняются при х - ж(Л), й = и(Х). Сделаем еще одно предположение.

Условие 2. При любом А > О вектор и(\) единственен.

Зафиксируем Л > 0; ж(Л) = (жх(Л),..., ж#(А)) - решение задачи квадратичного программирования (9.1), (9.2). Индексы г, для которых жДА) > 0, назовем внутренними. Индексы г, для которых Xi(X) = 0, назовем внешними3*.

а) внутренний индекс г б) внешний индекс г

Рис. 9.1. Графики функции Ф(г,и), как функции от xj, вблизи точки (г(А),и(А))

Ha рис. 9.1 приведены графики функций Ф(х,и), когда все переменные, кроме Х{, фиксированны и равны соответствующим координатам векторов ж(А) и и(Х). Ветви пара-

38Разумеется, тот индекс г, который при одном А является внутренним, при другом А может быть внешним.