Свойства выпуклых множеств. Выпуклые множества и функции

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

Определения

Примеры

• Выпуклые подмножества множества $\backslash R$ (множество вещественных чисел) представляют собой интервалы из $\backslash R$.
• Примерами выпуклых подмножеств в двумерном евклидовом пространстве ($\backslash R^2$) являются правильные многоугольники .
• Примерами выпуклых подмножеств в трёхмерном евклидовом пространстве ($\backslash R^3$) являются архимедовы тела и правильные многогранники .
• Тела Кепплера - Пуансо (правильные звездообразные многогранники) являются примерами невыпуклых множеств.

Свойства

• Выпуклое множество в топологическом линейном пространстве является связным и линейно связным , гомотопически эквивалентным точке.
• В терминах связности, выпуклое множество можно определить так: множество выпукло, если его пересечение с любой (вещественной) прямой связно.
• Пусть $K$ - выпуклое множество в линейном пространстве. Тогда для любых элементов $u\_1,\backslash ;u\_2,\backslash ;\backslash ldots,\backslash ;u\_r$ принадлежащих $K$ и для всех неотрицательных $\backslash lambda\_1,\backslash ;\backslash lambda\_2,\backslash ;\backslash ldots,\backslash ;\backslash lambda\_r$, таких что $\backslash lambda\_1+\backslash lambda\_2+\backslash ldots+\backslash lambda\_r=1$, вектор $w=\backslash sum\_\{k=1\}^r\backslash lambda\_k\; u\_k$

принадлежит $K$.

• Вектор $w$ называется выпуклой комбинацией элементов $u\_1,\backslash ;u\_2,\backslash ;\backslash ldots,\backslash ;u\_r$.

Вариации и обобщения

• Без каких-либо изменений определение работает для аффинных пространств над произвольным расширением поля вещественных чисел.

См. также

Напишите отзыв о статье "Выпуклое множество"

Литература

• Половинкин Е. С., Балашов М. В. Элементы выпуклого и сильно выпуклого анализа. - М .: ФИЗМАТЛИТ, 2004. - 416 с. - ISBN 5-9221-0499-3 . .
• Тиморин В. А. . - М .: МЦНМО , 2002. - 16 с. - ISBN 5-94057-024-0 . .

Ссылки

Отрывок, характеризующий Выпуклое множество

И Наташа встала на цыпочках и прошлась из комнаты так, как делают танцовщицы, но улыбаясь так, как только улыбаются счастливые 15 летние девочки. Встретившись в гостиной с Соней, Ростов покраснел. Он не знал, как обойтись с ней. Вчера они поцеловались в первую минуту радости свидания, но нынче они чувствовали, что нельзя было этого сделать; он чувствовал, что все, и мать и сестры, смотрели на него вопросительно и от него ожидали, как он поведет себя с нею. Он поцеловал ее руку и назвал ее вы – Соня. Но глаза их, встретившись, сказали друг другу «ты» и нежно поцеловались. Она просила своим взглядом у него прощения за то, что в посольстве Наташи она смела напомнить ему о его обещании и благодарила его за его любовь. Он своим взглядом благодарил ее за предложение свободы и говорил, что так ли, иначе ли, он никогда не перестанет любить ее, потому что нельзя не любить ее.
– Как однако странно, – сказала Вера, выбрав общую минуту молчания, – что Соня с Николенькой теперь встретились на вы и как чужие. – Замечание Веры было справедливо, как и все ее замечания; но как и от большей части ее замечаний всем сделалось неловко, и не только Соня, Николай и Наташа, но и старая графиня, которая боялась этой любви сына к Соне, могущей лишить его блестящей партии, тоже покраснела, как девочка. Денисов, к удивлению Ростова, в новом мундире, напомаженный и надушенный, явился в гостиную таким же щеголем, каким он был в сражениях, и таким любезным с дамами и кавалерами, каким Ростов никак не ожидал его видеть.

Вернувшись в Москву из армии, Николай Ростов был принят домашними как лучший сын, герой и ненаглядный Николушка; родными – как милый, приятный и почтительный молодой человек; знакомыми – как красивый гусарский поручик, ловкий танцор и один из лучших женихов Москвы.
Знакомство у Ростовых была вся Москва; денег в нынешний год у старого графа было достаточно, потому что были перезаложены все имения, и потому Николушка, заведя своего собственного рысака и самые модные рейтузы, особенные, каких ни у кого еще в Москве не было, и сапоги, самые модные, с самыми острыми носками и маленькими серебряными шпорами, проводил время очень весело. Ростов, вернувшись домой, испытал приятное чувство после некоторого промежутка времени примеривания себя к старым условиям жизни. Ему казалось, что он очень возмужал и вырос. Отчаяние за невыдержанный из закона Божьего экзамен, занимание денег у Гаврилы на извозчика, тайные поцелуи с Соней, он про всё это вспоминал, как про ребячество, от которого он неизмеримо был далек теперь. Теперь он – гусарский поручик в серебряном ментике, с солдатским Георгием, готовит своего рысака на бег, вместе с известными охотниками, пожилыми, почтенными. У него знакомая дама на бульваре, к которой он ездит вечером. Он дирижировал мазурку на бале у Архаровых, разговаривал о войне с фельдмаршалом Каменским, бывал в английском клубе, и был на ты с одним сорокалетним полковником, с которым познакомил его Денисов.
Страсть его к государю несколько ослабела в Москве, так как он за это время не видал его. Но он часто рассказывал о государе, о своей любви к нему, давая чувствовать, что он еще не всё рассказывает, что что то еще есть в его чувстве к государю, что не может быть всем понятно; и от всей души разделял общее в то время в Москве чувство обожания к императору Александру Павловичу, которому в Москве в то время было дано наименование ангела во плоти.
В это короткое пребывание Ростова в Москве, до отъезда в армию, он не сблизился, а напротив разошелся с Соней. Она была очень хороша, мила, и, очевидно, страстно влюблена в него; но он был в той поре молодости, когда кажется так много дела, что некогда этим заниматься, и молодой человек боится связываться – дорожит своей свободой, которая ему нужна на многое другое. Когда он думал о Соне в это новое пребывание в Москве, он говорил себе: Э! еще много, много таких будет и есть там, где то, мне еще неизвестных. Еще успею, когда захочу, заняться и любовью, а теперь некогда. Кроме того, ему казалось что то унизительное для своего мужества в женском обществе. Он ездил на балы и в женское общество, притворяясь, что делал это против воли. Бега, английский клуб, кутеж с Денисовым, поездка туда – это было другое дело: это было прилично молодцу гусару.
В начале марта, старый граф Илья Андреич Ростов был озабочен устройством обеда в английском клубе для приема князя Багратиона.
Граф в халате ходил по зале, отдавая приказания клубному эконому и знаменитому Феоктисту, старшему повару английского клуба, о спарже, свежих огурцах, землянике, теленке и рыбе для обеда князя Багратиона. Граф, со дня основания клуба, был его членом и старшиною. Ему было поручено от клуба устройство торжества для Багратиона, потому что редко кто умел так на широкую руку, хлебосольно устроить пир, особенно потому, что редко кто умел и хотел приложить свои деньги, если они понадобятся на устройство пира. Повар и эконом клуба с веселыми лицами слушали приказания графа, потому что они знали, что ни при ком, как при нем, нельзя было лучше поживиться на обеде, который стоил несколько тысяч.

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

С выпуклостью функций и множеств часто связано существование или единственность решения экономических задач: на этом же свойстве основаны многие вычислительные алгоритмы.

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

Выпуклые множества на плоскости .

Любая геометрическая фигура на плоскости может рассматриваться как множество точек, принадлежащих этой фигуре. Одни множества (например, круг, прямоугольник, полоса между параллельными прямыми) содержат и внутренние, и граничные точки; другие (например, отрезок, окружность) состоят только из граничных точек.

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

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

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

Пересечение, т. е. общая часть двух выпуклых множеств, всегда выпукло: взяв любые две точки пересечения (а они - общие, т. е. принадлежат каждому из пересекающихся множеств) и соединив их отрезком, мы легко убеждаемся в том, что все точки отрезка являются общими для обоих множеств, так как каждое из них выпукло. Выпуклым будет и пересечение любого числа выпуклых множеств.

Важным свойством выпуклых множеств является их отделимость: если два выпуклых множества не имеют общих внутренних точек, то плоскость можно разрезать по прямой таким образом, что одно из множеств будет целиком лежать в одной полуплоскости, а другое - в другой (на линии разреза могут располагаться точки обоих множеств). Отделяющая их прямая в одних случаях оказывается единственно возможной, в других - нет.

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

Введем на плоскости систему декартовых координат х, у. Теперь у нас появилась возможность рассматривать различные фигуры как множества таких точек, координаты которых удовлетворяют тем или иным уравнениям или неравенствам (если координаты точки удовлетворяют какому-либо условию, будем для краткости говорить, что сама точка удовлетворяет этому условию).

Множество X называется выпуклым, если для любых двух его точек A,B ∈ X все точки отрезка также принадлежат множеству X, то есть если для любых двух его точек A,B ∈ X и для любого значения α in точка M = αA + (1 − α)B также принадлежит множеству X: M ∈ X.

Пусть дано X1, ...Xn - выпуклые множества. Обозначим Y =Xi - пересечение выпуклых множеств. Покажем, что Y - выпуклое множество. Для этого покажем, что длялюбых точек A,B ∈ Y и для любого значения α in точка M = αA + (1 − α)B также принадлежит множеству Y: M ∈ Y . Так как Y - суть пересечение выпуклых множеств X1, ...Xn, то выбранные произвольным образом точки A,B принадлежат каждому из этих множеств Xi, i = 1..n. В силу выпуклости каждого из множеств Xi по определению следует, что для произвольно выбранного значения α ∈ точка M = αA+(1−α)B принадлежит каждому из множеств (все они выпуклы и содержат A,B). Так как все множества Xi содержат точку M, то и

пересечение этих множеств также содержит точку M: M ∈ Y . Из последнего включения в силу произвольности A,B ∈ Y и произвольности параметра α ∈ следует выпуклость множества Y , что и требовалось показать.

95. Является ли множество точек , удовлетворяющих условию , выпуклым? Ответ обоснуйте.

Да, очевидно, что это равенство задаёт линейную полуплоскость в R4.

Обоснуем это по оределению:

A = (a1, a2, a3, a4), B= (b1, b2, b3, b4) ∈ X,

удовлетворяющие вышеуказанному неравенству.

Рассмотрим произвольную точку M = αA + (1 − α)B, где α ∈ – произвольное значение параметра. ТогдаM(m1,m2,m3,m4) = αA + (1 − α)B

m1 = αa1 + (1 − αb1)

m2 = αa2 + (1 − αb2)

m3 = αa3 + (1 − αb3)

m4 = αa4 + (1 − αb4)

выполнимости заданного неравенства:

5 + 2m1 + 3m2 − m3 + 5m4 ≥ 0

5 + 2(αa1 + (1 − αb1)) + 3(αa2 + (1 − αb2)) − (αa3 + (1 − αb3)) + 5(αa4 + (1 − αb4)) ≥ 0

Представим 5 = α5+(1−α)5, раскроем и сгруппируем слагаемые для ai и bi. Получим:

α(5 + 2a1 + 3a2 − a3 + 5a4) + (1 − α)(5 + 2b1 + 3b2 − b3 + 5b4) ≥ 0

Так как точки A,B лежат в множестве X, то их координаты удовлетворяют неравенству,

задающему множество. Значит, оба слагаемых неотрицательны в силу неотрицательности

α и 1 − α. Поэтому последнее неравенство выполнено для любых A,B и любого значения

параметра α ∈ . По определению мы показали, что данное множество X является

выпуклым.

96. Является ли множество точек удовлетворяющих условию , выпуклым? Ответ обоснуйте.

Да, очевидно, что это равенство задаёт линейную гиперплоскость в R4.

Обоснуемэто по оределению:

Рассмотрим любые две точки этого пространства

A = (a1, a2, a3, a4), B= (b1, b2, b3, b4) ∈ X

удовлетворяющие вышеуказанному равенству.

Рассмотрим произвольную точку M = αA + (1 − α)B, где α ∈ – произвольное значение параметра. Тогда M(m1,m2,m3,m4) = αA + (1 − α)B

m1 = αa1 + (1 − αb1)

m2 = αa2 + (1 − αb2)

m3 = αa3 + (1 − αb3)

m4 = αa4 + (1 − αb4)

Проверим для точки M(m1,m2,m3,m4) принадлежность к множеству X с помощью

выполнимости заданного равенства:

m1 + 2m2 − 3m3 + 4m4 = 55

(αa1 + (1 − αb1)) + 2(αa2 + (1 − αb2)) − 3(αa3 + (1 − αb3)) + 4(αa4 + (1 − αb4)) = 55

Раскроем скобки и сгруппируем слагаемые для ai и bi. Получим:

α(a1 + 2a2 − 3a3 + 4a4) + (1 − α)(b1 + 2b2 − 3b3 + 4b4) = 55

Так как точки A,B лежат в множестве X, то их координаты удовлетворяют равенству,

задающему множество, то есть (a1 + 2a2 − 3a3 + 4a4) = 55 и (b1 + 2b2 − 3b3 + 4b4) = 55.

Подставив эти равенства в последнее выражение получим:

α55 + (1 − α)55 = 55

Последнее равенство выполнено для любых A,B и любого значения параметра α ∈ . По определению мы показали, что данное множество X является выпуклым.

97. Приведите примеры выпуклого множества: а) имеющего угловую точку; б) не имеющего угловой точки. Может ли не ограниченное выпуклое множество иметь угловую точку? Приведите пример.

а) квадрат имеет 4 угловые точки

б) окружность не имеет угловых точек

в) неограниченное множество может иметь угловые точки: имеет одну угловую точку (0;0)

98. Дайте определение выпуклой оболочки системы точек. Пусть - выпуклая оболочка точек , , , . Принадлежат ли множеству точки: , ? Ответ обоснуйте.

то есть выполнено условие того, что это выпуклая линейная комбинация, а значит X входит в состав выпуклой оболочки. Предположим, что Y входит также в выпуклую комбинацию, тогда все точки отрезка должны входить в линейную комбинацию, но по исходным точкам видно (все они находятся правей прямой x = -1), что вся выпуклая комбинация расположена справа от прямой x =-1, а точка Y - слева, что подтверждает, что ни весь отрезок ни точка Y - не принадлежат выпуклой оболочке.