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

Примеры выпуклых множеств

1. E n .

2. Пустое множество.

3. Множество, состоящее из одной точки

,

где
.

4. Гиперплоскость

где
, a ≠ 0, иb – число. Приn = 3 это множество совпадает с обычной плоскостью, а приn = 2 – с прямой.

5. Полупространство

где
, a ≠ 0, иb – число.

6. Конус

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

7. Выпуклая комбинация (оболочка) конечного числа точек

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

8. Пересечение конечного числа полупространств

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

9. Шар радиуса r ≥0 с центром в

.

В качестве примеров невыпуклых множеств можно назвать множество целых чисел или множество рациональных чисел.

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

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

Объединение двух выпуклых множеств не обязательно выпукло.

Пример: объединение двух точек не есть выпуклое множество.

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

Эти утверждения следуют из определения выпуклого множества. Докажем, например, первое утверждение для пересечения двух множеств
и
. Пусть. Рассмотрим

Из выпуклости A иB получаем, что
и
при всех
. Отсюда
. Утверждение доказано.

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

В качестве примера приведем выпуклый многогранник. Его крайними точками являются его вершины.

Определение . МножествоSE n называетсястрого выпуклым , если оно выпукло и все его граничные точки являются крайними.

Примером строго выпуклого множества является замкнутый шар.

2.1.3. Опорная гиперплоскость

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

Гиперплоскость является пересечением этих полупространств и одновременно границей каждого из них.

Пусть имеется некоторое выпуклое множество S и его граничная точкаy .

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

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

Рис. 3.1. Опорная гиперплоскость H к выпуклому множеству S в точке y .

Отметим, что опорная гиперплоскость может быть не единственна (см. рис. 3.2).

Рис. 3.2. Две опорных гиперплоскости H 1 и H 2 к выпуклому множеству S в точке y .

Пусть теперь задано два непустых множества A иB . ГиперплоскостьH называетсяразделяющей гиперплоскостью, если все точки множестваA лежат в одном из замкнутых полупространств, определяемых гиперплоскостьюH , а все точки множестваB лежат в другом из определяемых ею замкнутых полупространств. Можно доказать несколько теорем о разделяющих гиперплоскостях. Рассмотрим простейшую из них. Пусть
– совокупность внутренних точек множестваA .

Теорема 3.1. ПустьA иB – два непустых выпуклых множества, причем
Ø. Тогда существует гиперплоскостьH , разделяющая множестваA иB. 1

Примеры разделяющих гиперплоскостей приведены на рис. 3.3 и 3.4.

Рис. 3.3. Гиперплоскость H разделяет множества S 1 и S 2 , не имеющие общую точку

Рис. 3.4. Гиперплоскость H разделяет множества S 1 и S 2 , имеющие общую точку

Выпуклые и вогнутые функции

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Классификация и специфика задач математического программирования.

Введение в математическое программирование.

Математическое программирование является одним из способов исследования операций в экономике. Содержание математического программирования составляют теория и методы решения задач о нахождении экстремума функции на некотором множестве. Множества могут определяться как линœейными так и не линœейными ограничениями. Главная цель задач математического программирования – выбор программ действий, приводящих к наилучшему результату, с точки зрения лица, принимающего решения (ЛПР). Проблема принятия решения в последовательности операции неразрывно связано с проблемами моделирования.

Определœение модели.

Модель - ϶ᴛᴏ образ изучаемого явления или объекта.

Этапы моделирования.

1. Построение качественной модели, ᴛ.ᴇ. выделœение факторов, которые представляются наиболее важными в установлении закономерности, которым они подчиняются.

2. Построение математической модели. Запись качественной модели в математических терминах.

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

Реальное решение может и не существовать .

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

3 этап. Исследование влияния переменных на значения целœевой функции, нахождение решения, поставленной задачей.

4 этап. Сопоставление результатов вычисления, полученных на 3 этапе с моделированным объектом, ᴛ.ᴇ. критерий практики.

Здесь устанавливается степень адекватности модели и моделируемого объекта.

В математическом программировании можно выделить два направления:

· Собственно математическое программирование – детерминированные задачи, когда вся исходная информация полностью определœена;

· Стохастическое программирование. К нему относятся задачи, в которых исходная информация содержит неопределённость, либо когда некоторые параметры носят случайный характер с известными вероятностными характеристиками.

В математическом программировании выделяют следующие разделы:

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

2) Нелинœейное программирование. Данная задача и целœевая функция и ограничения носят нелинœейный характер.
Размещено на реф.рф
Задачи нелинœейного программирования обычно классифицируют на:

a) Выпуклое программирование, когда целœевая функция выпукла и выпукло множество, на котором решается задача.

b) Квадратичное программирование, когда целœевая функция квадратична, а ограничения линœейное равенство или неравенство.

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

3) Целочисленное программирование, когда на значения переменных или на значения целœевой функции накладывается условие целочисленности.

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

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

Элементы выпускного анализа.

Множество Х принято называть замкнутым если оно содержит всœе свои предельные точки

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

Множество Х принято называть выпуклым множеством если на ряду с каждыми точками Х1, Х2 є этому множеству всœе точки Х равны (1-α)· , где 0≤α≤1 так же принадлежат этому множеству Х. Т.е. если множеству Х, то и отрезок, соединяющий эти точки, тоже множеству Х.

Пример:

Дано множество Ө ={х, у такие, что х+у≤1. Доказать, что данное множество является выпуклым.

Пусть взяли две точки () и () Ө (ᴛ.ᴇ. + ≤1 и + ≤1).

Доказать, что точка

1. Теорема 1

Пересечение выпуклых множеств является выпуклым множеством.

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

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

Докажем, что Х выпуклое множество.

Пусть точки и Х. Докажем, что отрезок, соединяющий эти точки, тоже принадлежит множеству Х.

т.к. и Х => и Х1

Х1 выпуклое множество => отрезок [ , ] Х1

т.к. , Х => они Х2

Х2 выпуклое множество.

Отсюда следует, что отрезок [ , ] Х1∩Х2=Х

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

2. Теорема 2.

Объединœение выпуклых множеств не всœегда является выпуклым.

3. Свойство определённости.

Рассмотрим двухмерное пространство, в котором имеется неĸᴏᴛᴏᴩᴏᴇ замкнутое и выпуклое множество Х и некая точка d (,), где d Х, тогда найдётся прямая

С такая, что будут выполняться неравенства

Гиперплоскостью в пространстве R принято называть множество точек x (которая удовлетворяет равенству

Свойства выпуклого множества - понятие и виды. Классификация и особенности категории "Свойства выпуклого множества" 2017, 2018.

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

Определения

Примеры

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

• Вектор $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 . .

Ссылки

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

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