Выпуклый много и ее свойства. Дайте определение выпуклого множества

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

Определения

Примеры

• Выпуклые подмножества множества $\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 - не принадлежат выпуклой оболочке.

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

Определение

Другими словами, множество называется выпуклой, если:

То есть, если множество X вместе с любыми двумя точками, которые принадлежат этому множеству, содержит отрезок, их соединяющий:

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

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

• гиперплоскости H p? с нормалью p :

• полупространства на которые гиперплоскости разделяет пространство:

Все перечисленные множества (кроме пули) является частным случаем выпуклой множества полиэдры.

Свойства выпуклых множеств

• Пересечение выпуклых множеств является выпуклым.
• Линейная комбинация точек выпуклой множества выпуклая.
• Выпуклая множество содержит любую выпуклую комбинацию своих точек.
• Любую точку n -мерного евклидова пространства с выпуклой оболочки множества можно представить как выпуклую комбинацию не более n +1 точек этого множества

Рассмотрим n - мерное евклидово пространство и пусть  точка в этом пространстве.

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

(в координатах это записывается так:

отрезком , соединяющим точки и . Сами точки и называются концами отрезка . В случаях n =2 и n =3 это  отрезок в обычном понимании этого слова на плоскости или в пространстве (см. рис. 12). Заметим, что при  =0 , а при  =1 , т.е. при  =0 и  =1 получаются концы отрезка.

Пусть в

заданы k точек

. Точка

где все и называется выпуклой комбинацией точек .

Пусть есть некоторая область в пространстве (другими словами,

G есть некоторое множество точек из

).

Определение. Множество (область) называется выпуклым , если из того, что и следует, что для   . Другими словами, G  выпуклое множество, если оно, вместе с любыми двумя своими точками, содержит в себе отрезок, соединяющий эти точки.

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

Теорема 1. Пусть G  выпуклое множество. Тогда любая выпуклая комбинация точек, принадлежащих этому множеству, также принадлежит этому множеству.

Доказательство

Докажем теорему методом математической индукции. При k =2 теорема верна, так как она просто переходит в определение выпуклого множества.

Пусть теорема верна для некоторого k . Возьмём точку и рассмотрим выпуклую комбинацию

где все

и .

Представим

в виде

Теорема доказана.

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

Доказательство.

1. В стандартной форме в матричных обозначениях допустимая область G определяется условием

Т.е. x принадлежит G и, следовательно, выпукло.

2. В канонической форме область G определена условиями

Пусть и принадлежат G, т.е.

.

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

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

многогранникомв n - мерном пространстве

Теорема 3. Множество оптимальных планов задачи линейного программирования выпукло (если оно не пусто).

Доказательство

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

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

Теорема 4. Для того, чтобы задача линейного программирования имела решение, необходимо и достаточно, чтобы целевая функция на допустимом множестве была ограничена сверху (при решении задачи на максимум) или снизу (при решении задачи на минимум).

Эту теорему мы даем без доказательства.

Пусть х , у , z – элементы n -мерного действительного евклидова пространства Будем называть их также векторами или точками пространства

Определение . Отрезком, соединяющим точки x и y , называется множество точек вида

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

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

Теорема . Непустое пересечение любого числа выпуклых множеств является выпуклым множеством.

Доказательство . Пусть - выпуклые множества, и точки x , y принадлежат всем этим множествам одновременно поэтому Точка по определению выпуклого множества принадлежит всем множествам одновременно. Таким образом, для любых двух точек точки принадлежат множеству M . Поэтому по определению М – выпуклое множество.

Определение . Гиперплоскостью в называется множество точек

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

Замечания . 1) Гиперплоскость является выпуклым множеством. Действительно, пусть Тогда для любого точка принадлежит G , так как

2) Направляющий вектор a ортогонален гиперплоскости, то есть для любого вектора z = x – y , соединяющего две произвольные несовпадающие точки гиперплоскости (a , z ) = 0. Действительно,

(a , z ) = (a , x ) – (a , y ) = c – c = 0.

Определение . Множество точек вида

называется полупространством в

Направление неравенства в определении можно взять и противоположным.

Замечание . Полупространство является выпуклым множеством. Действительно, пусть Тогда для любого точка принадлежит S , так как

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

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

Определение . Множество вида

называется положительным ортантом .

Положительный ортант есть выпуклый многогранник. Действительно, неравенство можно интерпретировать как систему неравенств

Определение . Пусть выпуклый многогранник G задан системой неравенств

где - направляющие векторы, k > n . Если точка обращает в равенства не менее n неравенств, причем ранг соответствующей системы векторов равен n , то точка у называется угловой (или крайней) точкой многогранника.

Отметим, что число угловых точек выпуклого многогранника может быть (в зависимости от n и k ) очень большим. Так, при n = 10, k = 20 это число может быть сравнимо с 10 11 .

Замечание . Так как равенство вида

можно заменить системой двух неравенств

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

Напомним определение часто используемого выпуклого множества.

Определение . ε – окрестностью точки называется открытый шар

Очевидно, ε – окрестность точки есть выпуклое множество.

Определение . Точка x называется граничной точкой множества , если ε -окрестность содержит точки, принадлежащие множеству X и точки, не принадлежащие множеству X .

Определение . Точка x называется внутренней точкой множества , если найдется , что ε -окрестность целиком лежит внутри множества X .

Замечание . Граничная точка может и не принадлежать множеству X . Например, для множестваОпределение . Множество Х называется ограниченным , если его диаметр является конечным числом.

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

Замечание . Из определения следует, что конус содержит нулевую точку х = 0. Конус является неограниченным множеством (за исключением вырожденного случая, когда конус содержит всего лишь одну точку х = 0). Конус может быть как замкнутым, так и незамкнутым множеством.

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

Замечание . Замкнутые ограниченные множества представляют особый интерес в связи с теоремой Вейерштрасса, которая утверждает, что непрерывная функция на замкнутом ограниченном множестве (компакте) достигает своего наибольшего и наименьшего значений.

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

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

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

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

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

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

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

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

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

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

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

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