§ 13. Приложение к главе XIV1. Рассмотрим в евклидовом пространстве конечную систему векторов . Множество векторов , представимых в виде , , , образует минимальный выпуклый конус, содержащий систему векторов , или, иначе, выпуклый конус, порожденный системой векторов . Определение 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). Теорема доказана.
|