Разделяющая гиперплоскость: § 13. Приложение к главе XIV

§ 13. Приложение к главе XIV

1. Рассмотрим в евклидовом пространстве конечную систему векторов .

Множество векторов , представимых в виде

образует минимальный выпуклый конус, содержащий систему векторов , или, иначе, выпуклый конус, порожденный системой векторов .

Определение 1. Система векторов не развернута, если порожденный ею выпуклый конус не содержит нуля.

Определение 2. Система векторов сильно развернута, если порожденный ею выпуклый конус содержит все пространство .

Определения 1 и 2 эквивалентны следующим двум определениям.

Определение 1'. Система векторов не развернута, если существует такой вектор , что для всех

Определение 2'. Система векторов сильно развернута, если для всякого найдется такой вектор , что

Докажем, что определения 1 и 2 эквивалентны 1' и 2'.

Теорема П.1. Определение 1' эквивалентно 1.

Доказательство. Пусть система векторов не развернута в смысле 1'. Значит, существует такое , что

для всех .

Рассмотрим произвольный элемент выпуклого конуса, порожденного системой :

. (П.1)

Умножим скалярно (П. 1) слева и справа на :

Так как и по крайней мере одно , то

т.е. .

Таким образом, из 1' следует 1.

Пусть теперь система векторов выпукла в смысле определения 1. Рассмотрим выпуклую оболочку системы , т. е. множество векторов , представимых в виде

Согласно определению 1, это множество не содержит нуля. Кроме того, оно замкнуто и ограничено. Поэтому вектор , на котором достигается , не равен нулю и принадлежит множеству .

Покажем теперь, что для любого

Рассмотрим отрезок

Легко видеть, что этот отрезок принадлежит . Найдем модуль произвольного вектора , конец которого лежит на отрезке :

где – величина второго порядка малости по .

Так как , то коэффициент при линейном члене должен быть неположительным, т. е.

откуда следует

Последнее неравенство справедливо для любого , а следовательно, и для . Значит, условие определения 1 выполнено.

Таким образом, эквивалентность 1 и 1' показана.

Теорема П.2. Определения 2' и 2 эквивалентны.

Доказательство. Пусть справедливо 2. Это значит, что произвольный вектор может быть представлен в виде

где

, , .

Умножим скалярно последнее равенство на :

. (П.2)

Учитывая, что , из равенства (П.2) имеем, что по крайней мере для одного

т. е. система строго невыпукла в определении 2'.

Покажем теперь, что из 2' следует 2. Допустим, что не существует вектора такого, что для всех

Отсюда следует, что нуль принадлежит выпуклому конусу, порожденному , так как в противном случае в силу эквивалентности 1 и 1' найдется вектор такой, что для всех

в противоречии с 2' .

Назовем вектор базовым, если существует представление нуля вида

в которое вектор входит с ненулевым весом (т. е. ).

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

следует, что

. (П.3)

Произвольный вектор пространства , порожденного базовыми векторами из , представим в виде

где – базовые векторы; здесь некоторые могут быть отрицательными.

Представим все члены суммы с отрицательными коэффициентами в виде , a в соответствии с (П.3) разложим по базовым векторам с неотрицательными коэффициентами.

Таким образом, получим представление

, ,

для произвольного .

Далее рассмотрим следующие возможности.

А. Пространство , порожденное базовыми векторами, совпадает со всем пространством . В этом случае, как только что показано, выпуклый конус, порожденный , совпадает с , т. е. выполняются условия определения 2.

Б. Пространство имеет размерность меньшую, чем , и при этом все векторы из базовые. В этом случае рассмотрим произвольный вектор из , ортогональный . Очевидно, что при этом для всех выполняется равенство

в противоречии с определением 2'.

В. Пространство имеет размерность меньшую, чем , и не все векторы базовые.

Тогда пространство представим в виде произведения двух ортогональных подпространств

Рассмотрим множество проекций небазовых векторов в пространстве .

Утверждается, что множество образует неразвернутую систему векторов. Действительно, если это не так, то, как уже было показано, выпуклый конус, порожденный , содержит 0, т. е. существуют такие , , что

где – проекции небазовых векторов в .

Рассмотрим вектор

, (П.4)

где – небазовые векторы, проекции которых равны соответственно .

Тогда

Следовательно, вектор принадлежит пространству . Поэтому вектор может быть представлен как линейная комбинация базовых векторов с неотрицательными коэффициентами

. (П.5)

Суммируя (П.4) и (П.5), имеем

. (П.6)

Легко видеть, что в разложении нуля (П.6) хотя бы один небазовый вектор участвует с ненулевым весом.

Полученное противоречие доказывает, что множество проекций не развернуто.

Покажем теперь, что это утверждение находится в противоречии с тем, что множество векторов сильно развернуто в смысле определения 2'.

Поскольку множество не пусто и не развернуто, то, согласно определению 1', в существует такой вектор , что

, (П.7)

а следовательно,

, (П.8)

для базовых векторов и

для небазовых векторов, в противоречии с определением 2'. Эквивалентность определений 2 и 2' доказана.

Фактически попутно доказана следующая теорема.

Теорема П.3. Если минимальный выпуклый конус, порожденный конечной системой векторов , не совпадает со всем пространством , то существует вектор такой, что для всех

, (П.9)

причем для небазовых векторов неравенство переходит в строгое . Если же система векторов сильно развернута, то всякий ее вектор является базовым.

Замечание. Если – произвольный вектор такой, что для всех выполняется (П.9), то для всякого базового вектора неравенство переходит в равенство, т. е.

Действительно, пусть – базовый вектор. В силу (П.9)

. (П.10)

В то же время, как показано выше ((П.3)), вектор разложим по базовым векторам с неотрицательными коэффициентами

Следовательно,

. (П.11)

Из (П.10) и (П.11) получаем

2. Из теоремы П.3 легко следует известная теорема Куна – Таккера.

Теорема П.4. (Куна – Таккера). Пусть заданы дифференцируемая функция и линейные функции при . Пусть доставляет условный минимум при ограничениях

Тогда существуют такие числа , что выполняются условия

(П.12)

Доказательство. Если равен нулю, то утверждение леммы тривиально, так как можно положить все равными нулю.

Занумеруем от 1 до те ограничения, для которых

Допустим, что и утверждение теоремы неверно. Это значит, что система векторов

такова, что не является базовым вектором системы.

Действительно, если бы вектор был базовым, то существовало бы представление

а значит, и представление (П. 12).

Следовательно, в соответствии с теоремой П.3, существует вектор такой, что

для всех и

. (П.13)

Рассмотрим точку . При достаточно малом ограничения не нарушатся, так как при

а при

и, следовательно, по непрерывности

при достаточно малых .

В то же время

и, следовательно, в силу (П. 13) при достаточно малых положительных

в противоречии с условиями теоремы. Теорема доказана.

Замечание. Теорема обобщается и на случай, когда среди ограничений есть ограничения вида равенств

. (П. 14)

Действительно, ограничение (П.14) равносильно двум ограничениям:

и .

Поэтому условия (П. 12) сохраняются, но , соответствующие ограничениям вида равенств, могут быть отрицательными.

В случае, когда функция дифференцируема и выпукла, условия (П. 12) становятся не только необходимыми, но и достаточными условиями минимума.

Теорема П.5. Пусть функция дифференцируема и выпукла. Если в точке , удовлетворяющей неравенствам

выполняются условия (П. 12), т. е. существуют такие , что

то точка доставляет условный минимум функции при ограничениях

. (П. 15)

Доказательство. Пусть – точка, о которой говорится в условии теоремы. Если теорема неверна, то найдется точка , удовлетворяющая (П. 15), такая, что

. (П. 16)

Рассмотрим отрезок

при .

В силу выпуклости допустимой области этот отрезок целиком лежит в пределах ограничений. Кроме того, из выпуклости следует (см. § 2 главы IX), что

и, следовательно,

. (П.17)

Как и раньше, будем считать, что от 1 до занумерованы те ограничения, которые достигаются в точке , т. е.

Тогда, поскольку отрезок целиком лежит в пределах ограничений, имеем

. (П.18)

Из (П.17) и (П.18), учитывая замечание к теореме П.3, получаем, что вектор не является базовым в системе

и, следовательно, не существует представления в противоречии с условием теоремы. Теорема доказана.

3. Пусть точка удовлетворяет системе ограничений :

т. е. первые ограничений достигаются в точке .

Назовем единичный вектор допустимым направлением в точке , если существует такое, что при . Нетрудно убедиться, что допустимыми в являются те и только те направления , для которых выполняются неравенства

Условный градиент в точке определяется так. Прежде всего, находится направление наибольшего возрастания функции среди допустимых, т. е.

где максимум берется по допустимым направлениям. При этом может оказаться, что

Это означает, что по всякому допустимому направлению функция не возрастает. В этом случае условный градиент считается равным нулю.

Если же

то в качестве условного градиента берется вектор, по направлению совпадающий с , а по модулю равный .

Таким образом,

Справедлива теорема.

Теорема П.6 Условный градиент, в точке представим в виде

, (П.19)

причем

, (П.20)

и обратно, всякий вектор, удовлетворяющий (П.19), (П.20), является условным градиентом.

Доказательство. Допустим, что ; тогда по теореме Куна – Таккера существует представление

и, следовательно,

, (П.21)

что и требуется.

Обратно, пусть справедливо (П. 21); в этом случае разложение (П. 19) может задавать только нулевой вектор. Действительно, пусть

Тогда

Если при этом

то есть допустимое направление, по которому функция возрастает в противоречии с допущением. Таким образом, .

Допустим теперь, что . Тогда, как нетрудно убедиться, направление совпадает с направлением обобщенного портрета класса , состоящего из одного вектора , относительно класса , состоящего из векторов для .