Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


§ 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) может задавать только нулевой вектор. Действительно, пусть

,

,

  ,

.

Тогда

.

Если при этом

,

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

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

Действительно, при этом  есть единичный вектор, на котором достигается максимум

при ограничениях

,

причем заведомо известно, что .

Поэтому в силу теорем, доказанных выше, вектор  однозначно задается разложением

,                        (П.22)

, , , .

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

,

откуда

.

Поэтому

.

Полагая , получим разложение (П. 19). Теорема доказана.

 



<< ПредыдущаяОглавлениеСледующая >>