§ 13. Приложение к главе XIV
1. Рассмотрим в евклидовом пространстве
конечную систему векторов
.
Множество
векторов
, представимых в виде
,
,
,
образует минимальный выпуклый конус, содержащий систему векторов
, или, иначе, выпуклый конус, порожденный системой векторов
.
Определение 1. Система векторов
не развернута, если порожденный ею выпуклый конус не содержит нуля.
Определение 2. Система векторов
сильно развернута, если порожденный ею выпуклый конус
содержит все пространство
.
Определения 1 и 2 эквивалентны следующим двум определениям.
Определение 1'. Система векторов
не развернута, если существует такой вектор
, что для всех ![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image010.gif)
.
Определение 2'. Система векторов
сильно развернута, если для всякого
найдется такой вектор
, что
.
Докажем, что определения 1 и 2 эквивалентны 1' и 2'.
Теорема П.1. Определение 1' эквивалентно 1.
Доказательство. Пусть система векторов не развернута в смысле 1'. Значит, существует такое
, что
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image011.gif)
для всех
.
Рассмотрим произвольный элемент
выпуклого конуса, порожденного системой
:
,
,
. (П.1)
Умножим скалярно (П. 1) слева и справа на
:
.
Так как
и по крайней мере одно
, то
,
т.е.
.
Таким образом, из 1' следует 1.
Пусть теперь система векторов
выпукла в смысле определения 1. Рассмотрим выпуклую оболочку
системы
, т. е. множество векторов
, представимых в виде
,
,
.
Согласно определению 1, это множество не содержит нуля. Кроме того, оно замкнуто и ограничено. Поэтому вектор
, на котором достигается
, не равен нулю и принадлежит множеству
.
Покажем теперь, что для любого ![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image025.gif)
.
Рассмотрим отрезок
.
Легко видеть, что этот отрезок принадлежит
. Найдем модуль произвольного вектора
, конец которого лежит на отрезке
:
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image029.gif)
,
где
– величина второго порядка малости по
.
Так как
, то коэффициент при линейном члене должен быть неположительным, т. е.
,
откуда следует
.
Последнее неравенство справедливо для любого
, а следовательно, и для
. Значит, условие определения 1 выполнено.
Таким образом, эквивалентность 1 и 1' показана.
Теорема П.2. Определения 2' и 2 эквивалентны.
Доказательство. Пусть справедливо 2. Это значит, что произвольный вектор
может быть представлен в виде
,
где
,
,
.
Умножим скалярно последнее равенство на
:
. (П.2)
Учитывая, что
, из равенства (П.2) имеем, что по крайней мере для одного ![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image040.gif)
,
т. е. система строго невыпукла в определении 2'.
Покажем теперь, что из 2' следует 2. Допустим, что не существует вектора
такого, что для всех ![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image043.gif)
.
Отсюда следует, что нуль принадлежит выпуклому конусу, порожденному
, так как в противном случае в силу эквивалентности 1 и 1' найдется вектор
такой, что для всех ![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image043.gif)
,
в противоречии с 2' .
Назовем вектор
базовым, если существует представление нуля вида
,
в которое вектор
входит с ненулевым весом (т. е.
).
Выпуклый конус, порожденный всеми базовыми векторами из
, совпадает с гиперпространством
, порожденным этими векторами. Действительно, если вектор
базовый, то вектор
принадлежит конусу, порожденному базовыми векторами из
, так как из соотношения
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image054.gif)
следует, что
. (П.3)
Произвольный вектор
пространства
, порожденного базовыми векторами из
, представим в виде
,
где
– базовые векторы; здесь некоторые
могут быть отрицательными.
Представим все члены суммы с отрицательными коэффициентами
в виде
, a
в соответствии с (П.3) разложим по базовым векторам с неотрицательными коэффициентами.
Таким образом, получим представление
,
, ![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image063.gif)
для произвольного
.
Далее рассмотрим следующие возможности.
А. Пространство
, порожденное базовыми векторами, совпадает со всем пространством
. В этом случае, как только что показано, выпуклый конус, порожденный
, совпадает с
, т. е. выполняются условия определения 2.
Б. Пространство
имеет размерность меньшую, чем
, и при этом все векторы из
базовые. В этом случае рассмотрим произвольный вектор
из
, ортогональный
. Очевидно, что при этом для всех
выполняется равенство
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image065.gif)
в противоречии с определением 2'.
В. Пространство
имеет размерность меньшую, чем
, и не все векторы
базовые.
Тогда пространство
представим в виде произведения двух ортогональных подпространств
.
Рассмотрим множество проекций
небазовых векторов в пространстве
.
Утверждается, что множество
образует неразвернутую систему векторов. Действительно, если это не так, то, как уже было показано, выпуклый конус, порожденный
, содержит 0, т. е. существуют такие
,
, что
,
где
– проекции небазовых векторов в
.
Рассмотрим вектор
, (П.4)
где
– небазовые векторы, проекции которых равны соответственно
.
Тогда
.
Следовательно, вектор
принадлежит пространству
. Поэтому вектор
может быть представлен как линейная комбинация базовых векторов
с неотрицательными коэффициентами
. (П.5)
Суммируя (П.4) и (П.5), имеем
. (П.6)
Легко видеть, что в разложении нуля (П.6) хотя бы один небазовый вектор
участвует с ненулевым весом.
Полученное противоречие доказывает, что множество проекций
не развернуто.
Покажем теперь, что это утверждение находится в противоречии с тем, что множество векторов
сильно развернуто в смысле определения 2'.
Поскольку множество
не пусто и не развернуто, то, согласно определению 1', в
существует такой вектор
, что
, (П.7)
а следовательно,
, (П.8)
для базовых векторов и
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image081.gif)
для небазовых векторов, в противоречии с определением 2'. Эквивалентность определений 2 и 2' доказана.
Фактически попутно доказана следующая теорема.
Теорема П.3. Если минимальный выпуклый конус, порожденный конечной системой векторов
, не совпадает со всем пространством
, то существует вектор
такой, что для всех ![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image043.gif)
, (П.9)
причем для небазовых векторов неравенство переходит в строгое
. Если же система векторов
сильно развернута, то всякий ее вектор является базовым.
Замечание. Если
– произвольный вектор такой, что для всех
выполняется (П.9), то для всякого базового вектора
неравенство переходит в равенство, т. е.
.
Действительно, пусть
– базовый вектор. В силу (П.9)
. (П.10)
В то же время, как показано выше ((П.3)), вектор
разложим по базовым векторам с неотрицательными коэффициентами
.
Следовательно,
. (П.11)
Из (П.10) и (П.11) получаем
.
2. Из теоремы П.3 легко следует известная теорема Куна – Таккера.
Теорема П.4. (Куна – Таккера). Пусть заданы дифференцируемая функция
и линейные функции
при
. Пусть
доставляет условный минимум
при ограничениях
.
Тогда существуют такие числа
, что выполняются условия
(П.12)
Доказательство. Если
равен нулю, то утверждение леммы тривиально, так как можно положить все
равными нулю.
Занумеруем от 1 до
те ограничения, для которых
.
Допустим, что
и утверждение теоремы неверно. Это значит, что система векторов
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image101.gif)
такова, что
не является базовым вектором системы.
Действительно, если бы вектор
был базовым, то существовало бы представление
,
а значит, и представление (П. 12).
Следовательно, в соответствии с теоремой П.3, существует вектор
такой, что
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image104.gif)
для всех
и
. (П.13)
Рассмотрим точку
. При достаточно малом
ограничения не нарушатся, так как при ![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image109.gif)
,
а при ![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image111.gif)
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image112.gif)
и, следовательно, по непрерывности
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image113.gif)
при достаточно малых
.
В то же время
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image114.gif)
и, следовательно, в силу (П. 13) при достаточно малых положительных ![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image032.gif)
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image115.gif)
в противоречии с условиями теоремы. Теорема доказана.
Замечание. Теорема обобщается и на случай, когда среди ограничений есть ограничения вида равенств
. (П. 14)
Действительно, ограничение (П.14) равносильно двум ограничениям:
и
.
Поэтому условия (П. 12) сохраняются, но
, соответствующие ограничениям вида равенств, могут быть отрицательными.
В случае, когда функция
дифференцируема и выпукла, условия (П. 12) становятся не только необходимыми, но и достаточными условиями минимума.
Теорема П.5. Пусть функция
дифференцируема и выпукла. Если в точке
, удовлетворяющей неравенствам
,
выполняются условия (П. 12), т. е. существуют такие
, что
,
,
то точка
доставляет условный минимум функции
при ограничениях
. (П. 15)
Доказательство. Пусть
– точка, о которой говорится в условии теоремы. Если теорема неверна, то найдется точка
, удовлетворяющая (П. 15), такая, что
. (П. 16)
Рассмотрим отрезок
при
.
В силу выпуклости допустимой области этот отрезок целиком лежит в пределах ограничений. Кроме того, из выпуклости
следует (см. § 2 главы IX), что
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image125.gif)
и, следовательно,
. (П.17)
Как и раньше, будем считать, что от 1 до
занумерованы те ограничения, которые достигаются в точке
, т. е.
,
.
Тогда, поскольку отрезок
целиком лежит в пределах ограничений, имеем
. (П.18)
Из (П.17) и (П.18), учитывая замечание к теореме П.3, получаем, что вектор
не является базовым в системе
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image132.gif)
и, следовательно, не существует представления
в противоречии с условием теоремы. Теорема доказана.
3. Пусть точка
удовлетворяет системе ограничений
:
,
,
т. е. первые
ограничений достигаются в точке
.
Назовем единичный вектор
допустимым направлением в точке
, если существует
такое, что
при
. Нетрудно убедиться, что допустимыми в
являются те и только те направления
, для которых выполняются неравенства
.
Условный градиент в точке
определяется так. Прежде всего, находится направление
наибольшего возрастания функции среди допустимых, т. е.
,
где максимум берется по допустимым направлениям. При этом может оказаться, что
.
Это означает, что по всякому допустимому направлению функция не возрастает. В этом случае условный градиент считается равным нулю.
Если же
,
то в качестве условного градиента берется вектор, по направлению совпадающий с
, а по модулю равный
.
Таким образом,
.
Справедлива теорема.
Теорема П.6 Условный градиент, в точке
представим в виде
, (П.19)
причем
, (П.20)
и обратно, всякий вектор, удовлетворяющий (П.19), (П.20), является условным градиентом.
Доказательство. Допустим, что
; тогда по теореме Куна – Таккера существует представление
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image149.gif)
и, следовательно,
, (П.21)
что и требуется.
Обратно, пусть справедливо (П. 21); в этом случае разложение (П. 19) может задавать только нулевой вектор. Действительно, пусть
,
,
,
.
Тогда
.
Если при этом
,
то
есть допустимое направление, по которому функция
возрастает в противоречии с допущением. Таким образом,
.
Допустим теперь, что
. Тогда, как нетрудно убедиться, направление
совпадает с направлением обобщенного портрета класса
, состоящего из одного вектора
, относительно класса
, состоящего из векторов
для
.
Действительно, при этом
есть единичный вектор, на котором достигается максимум
![](/archive/arch.php?path=../htm/book_vap/files.book&file=vap_108.files/image163.gif)
при ограничениях
,
причем заведомо известно, что
.
Поэтому в силу теорем, доказанных выше, вектор
однозначно задается разложением
, (П.22)
,
,
,
.
Умножим равенство скалярно на
:
,
откуда
.
Поэтому
.
Полагая
, получим разложение (П. 19). Теорема доказана.