В геометрии подмножество евклидова пространства или, в более общем смысле, аффинного пространства над действительными числами , является выпуклым, если, учитывая любые две точки, оно содержит весь линейный сегмент , соединяющий их. Эквивалентно выпуклое множество или выпуклая область - это подмножество, которое пересекает каждую линию в один сегмент линии (возможно, пустой). [1] [2] Например, твердый куб представляет собой выпуклое множество, но все, что является полым или имеет выемку, например, в форме полумесяца , не является выпуклым.
Граница выпуклого множества всегда выпуклая кривая . Пересечение всех множеств выпуклых , которые содержат заданное подмножество А в евклидове пространства называется выпуклая оболочка из A . Это наименьшее выпуклое множество , содержащее А .
Выпуклая функция является вещественной функцией , определенной на интервал с тем свойством , что его эпиграф (множество точек на или выше график функции) представляет собой множество выпукло. Выпуклая минимизация - это подполе оптимизации , изучающая проблему минимизации выпуклых функций над выпуклыми множествами. Раздел математики, посвященный изучению свойств выпуклых множеств и выпуклых функций, называется выпуклым анализом .
Понятие выпуклого множества можно обобщить, как описано ниже.
Определения
Пусть S - векторное пространство или аффинное пространство над действительными числами или, в более общем смысле, над некоторым упорядоченным полем . Это включает евклидовы пространства, которые являются аффинными пространствами. Подмножество С из S является выпуклой , если для всех х и у в С , то отрезок соединяющий х и у входит в C . Это означает, что аффинная комбинация (1 - t ) x + ty принадлежит C для всех x и y в C и t в интервале [0, 1] . Отсюда следует, что выпуклость (свойство быть выпуклостью) инвариантна относительно аффинных преобразований . Это означает также , что выпуклое множество в реальном или комплексном топологическом векторном пространстве является связно , таким образом подключено .
Множество C естьстрого выпуклой , если каждая точка на отрезке линиисоединяющейхиу, отличных от конечных точек находится внутривнутреннейчастиC.
Множество C является абсолютно выпуклым, если оно выпукло и уравновешено .
Выпуклые подмножества из R (множество действительных чисел) являются интервалы и точки R . Некоторыми примерами выпуклых подмножеств евклидовой плоскости являются сплошные правильные многоугольники , сплошные треугольники и пересечения сплошных треугольников. Некоторыми примерами выпуклых подмножеств евклидова 3-мерного пространства являются тела Архимеда и Платоновы тела . В многогранники Kepler-Пуанси являются примерами невыпуклых множеств.
Невыпуклый набор
Невыпуклое множество называется невыпуклым множеством . Многоугольник , который не является выпуклым многоугольником иногда называется вогнутой многоугольник , [3] и некоторые источники в более общем случае используют термин набора вогнутого для обозначения не-выпуклое множества, [4] , но большинство власти запрещает это использование. [5] [6]
Дополнение множества выпуклого, такие как эпиграф о наличии вогнутой функции , иногда называют обратный набор выпуклого , особенно в контексте математической оптимизации . [7]
Характеристики
Для r точек u 1 , ..., u r в выпуклом множестве S и r неотрицательных чисел λ 1 , ..., λ r таких, что λ 1 + ... + λ r = 1 , аффинная комбинация
Такая аффинная комбинация называется выпуклой комбинацией из U 1 , ..., у г .
Перекрестки и союзы
Набор выпуклых подмножеств векторного пространства, аффинного пространства или евклидова пространства обладает следующими свойствами: [8] [9]
- Пустое множество и все пространство выпуклы.
- Пересечение любого набора выпуклых множеств выпукло.
- Объединение последовательности выпуклых множеств является выпуклым, если они образуют неубывающую цепь для включения. Для этого свойства важно ограничение цепями, так как объединение двух выпуклых множеств не обязательно должно быть выпуклым.
Замкнутые выпуклые множества
Замкнутые выпуклые множества - это выпуклые множества, содержащие все их предельные точки . Их можно охарактеризовать как пересечения замкнутых полупространств (множества точек в пространстве, лежащих на гиперплоскости и сбоку от нее ).
Из того, что только что было сказано, ясно, что такие пересечения выпуклые, и они также будут замкнутыми множествами. Чтобы доказать обратное, т. Е. Каждое замкнутое выпуклое множество может быть представлено как такое пересечение, нужна поддерживающая теорема о гиперплоскости в том виде, что для данного замкнутого выпуклого множества C и точки P вне его существует замкнутое полупространство H, которое содержит С , а не Р . Теорема опорная гиперплоскость является частным случаем теоремы Хана-Банаха из функционального анализа .
Выпуклые множества и прямоугольники
Пусть C - выпуклое тело на плоскости (выпуклое множество, внутренность которого не пуста). Мы можем вписать прямоугольник г в C таким образом, что гомотетичен копия R из R описан вокруг C . Положительный коэффициент гомотетии не превышает 2 и: [10]
Диаграммы Бляшке-Сантало
Набор всех плоских выпуклых тел можно параметризовать с помощью диаметра выпуклого тела D , его внутреннего радиуса r (наибольшего круга, содержащегося в выпуклом теле) и его описанного радиуса R (наименьшего круга, содержащего выпуклое тело). Фактически, это множество можно описать множеством неравенств, приведенных в [11] [12]
В качестве альтернативы набор также можно параметризовать по ширине (наименьшее расстояние между любыми двумя разными параллельными гиперплоскостями), периметру и площади. [11] [12]
Прочие свойства
Пусть X - топологическое векторное пространство и быть выпуклым.
- а также оба являются выпуклыми (т.е. закрытие и внутренность выпуклых множеств выпуклы).
- Если а также тогда (где ).
- Если тогда:
- , а также
- , где является алгебраическим внутренняя из C .
Выпуклые оболочки и суммы Минковского
Выпуклые корпуса
Каждое подмножество векторного пространства содержится в пределах наименьшего выпуклого множества (называемого выпуклой оболочкой из А ), а именно пересечение всех множеств выпуклых содержащих A . Оператор выпуклой оболочки Conv () обладает характеристическими свойствами оператора оболочки :
- обширный : S ⊆ Conv ( S ) ,
- неубывающая : из S ⊆ T следует, что Conv ( S ) ⊆ Conv ( T ) и
- идемпотент : Conv (Conv ( S )) = Conv ( S ) .
Операция выпуклой оболочки необходима для того, чтобы множество выпуклых множеств образовало решетку , в которой операция « соединения » представляет собой выпуклую оболочку объединения двух выпуклых множеств.
Сложение Минковского
В реальном векторном пространстве сумма Минковского двух (непустых) множеств, S 1 и S 2 , определяется как множество S 1 + S 2, образованное поэлементным сложением векторов из наборов слагаемых
Для сложения Минковского нулевое множество {0}, содержащее только нулевой вектор 0, имеет особое значение : для каждого непустого подмножества S векторного пространства
Выпуклые оболочки сумм Минковского
Сложение Минковского хорошо себя ведет по отношению к операции взятия выпуклой оболочки, как показано следующим утверждением:
Пусть S 1 , S 2 - подмножества реального векторного пространства, выпуклая оболочка их суммы Минковского - это сумма Минковского их выпуклых оболочек.
Этот результат верен в более общем случае для каждого конечного набора непустых множеств:
В математической терминологии операции суммирования Минковского и формирования выпуклой оболочки являются коммутирующими операциями. [14] [15]
Суммы Минковского выпуклых множеств
Сумма Минковского двух компактных выпуклых множеств компактна. Сумма компактного выпуклого множества и замкнутого выпуклого множества замкнута. [16]
Следующая знаменитая теорема, доказанная Дьедонне в 1966 году, дает достаточное условие замкнутости разности двух замкнутых выпуклых подмножеств. [17] Он использует концепцию конуса рецессии непустого выпуклого подмножества S , определяемого как:
Теорема (Дьедонне). Пусть A и B - непустые, замкнутые и выпуклые подмножества локально выпуклого топологического векторного пространства такие, что- линейное подпространство. Если или B является локально компактным , то - B закрыт.
Обобщения и расширения для выпуклости
Понятие выпуклости в евклидовом пространстве можно обобщить, изменив определение в тех или иных аспектах. Используется общее название «обобщенная выпуклость», потому что полученные объекты сохраняют определенные свойства выпуклых множеств.
Звездно-выпуклые (звездчатые) наборы
Пусть C - множество в вещественном или комплексном векторном пространстве. С является звезда выпуклым (звезда-образным) , если существует й 0 в C таким образом, что отрезок линии от й 0 до любой точки у в С содержатся в С . Следовательно, непустое выпуклое множество всегда звездно-выпуклое, но звездно-выпуклое множество не всегда выпукло.
Ортогональная выпуклость
Примером обобщенной выпуклости является ортогональная выпуклость . [18]
Множество S в евклидовом пространстве называется ортогонально выпуклой или орто-выпуклым , если любой отрезок , параллельный любому из координатных осей , соединяющих две точки S лежит полностью в пределах S . Легко доказать, что пересечение любого набора ортовыпуклых множеств ортовыпукло. Верны и некоторые другие свойства выпуклых множеств.
Неевклидова геометрия
Определение выпуклого множества и выпуклой оболочки естественным образом распространяется на геометрии, не являющиеся евклидовыми, путем определения геодезически выпуклого множества как такого, которое содержит геодезические, соединяющие любые две точки в множестве.
Топология заказа
Выпуклость может быть расширена для полностью упорядоченного множества X, наделенного порядковой топологией . [19]
Пусть Y ⊆ X . Подпространство Y является выпуклым множеством, если для каждой пары точек a , b в Y такой, что a ≤ b , интервал [ a , b ] = { x ∈ X | ≤ х ≤ б } содержится в Y . То есть, Y выпукло , если и только если для всех а , Ь в Y , ≤ B означает [ а , Ь ] ⊆ Y .
Выпуклое множество, вообще говоря, не связно: контрпример дается подпространством {1,2,3} в Z , которое одновременно является выпуклым и несвязным.
Выпуклые пространства
Понятие выпуклости может быть обобщено на другие объекты, если определенные свойства выпуклости выбраны в качестве аксиом .
Принимая во внимание множество Х , А выпуклость над X представляет собой набор 𝒞 подмножеств X , удовлетворяющих следующим аксиомам: [8] [9] [20]
- Пустое множество и X находятся в 𝒞
- Пересечение любого набора из 𝒞 в 𝒞 .
- Объединение цепи (по отношению к отношению включения ) элементов 𝒞 в 𝒞 .
Элементы 𝒞 называются множества выпуклых и пары ( X , 𝒞 ) , называется выпуклость пространство . Для обычной выпуклости верны первые две аксиомы, а третья тривиальна.
Для альтернативного определения абстрактной выпуклости, более подходящего для дискретной геометрии , см. Выпуклые геометрии, связанные с антиматроидами .
Смотрите также
- Поглощающий набор
- Ограниченное множество (топологическое векторное пространство)
- Теорема Брауэра о неподвижной точке
- Сложная выпуклость
- Выпуклый корпус
- Выпуклый ряд
- Выпуклое метрическое пространство
- Теорема Каратеодори (выпуклая оболочка)
- Теория Шоке
- Теорема Хелли
- Голоморфно выпуклая оболочка
- Целостно-выпуклое множество
- Эллипсоид Джона
- Псевдовыпуклость
- Теорема Радона
- Лемма Шепли – Фолкмана.
- Симметричный набор
Рекомендации
- ^ Моррис, Карла С .; Старк, Роберт М. (24 августа 2015 г.). Конечная математика: модели и приложения . Джон Вили и сыновья. п. 121. ISBN. 9781119015383. Проверено 5 апреля 2017 года .
- ^ Кьельдсен, Тинне Хофф. "История выпуклости и математического программирования" (PDF) . Труды Международного конгресса математиков (ICM 2010): 3233–3257. DOI : 10.1142 / 9789814324359_0187 . Архивировано из оригинального (PDF) 11 августа 2017 года . Проверено 5 апреля 2017 года .
- ^ МакКоннелл, Джеффри Дж. (2006). Компьютерная графика: теория в практику . п. 130 . ISBN 0-7637-2250-2..
- ^ Вайсштейн, Эрик В. «Вогнутая» . MathWorld .
- ^ Такаяма, Акира (1994). Аналитические методы в экономике . Пресса Мичиганского университета. п. 54. ISBN 9780472081356.
Часто наблюдаемая путаница - это «вогнутый набор». Вогнутые и выпуклые функции обозначают определенные классы функций, а не наборов, тогда как выпуклое множество обозначает определенный класс наборов, а не класс функций. «Вогнутый набор» путает наборы с функциями.
- ^ Корба, Дин; Stinchcombe, Maxwell B .; Земан, Юрай (2009). Введение в математический анализ для экономической теории и эконометрики . Издательство Принстонского университета. п. 347. ISBN 9781400833085.
Нет такого понятия, как вогнутый набор.
- ^ Мейер, Роберт (1970). «Обоснованность семейства методов оптимизации» (PDF) . SIAM Journal по управлению и оптимизации . 8 : 41–54. DOI : 10.1137 / 0308003 . Руководство по ремонту 0312915 ..
- ^ a b Солтан, Валериу, Введение в аксиоматическую теорию выпуклости , Штиинца, Кишинев , 1984.
- ^ а б Певец, Иван (1997). Абстрактный выпуклый анализ . Серия монографий и расширенных текстов Канадского математического общества. Нью-Йорк: John Wiley & Sons, Inc., стр. Xxii + 491. ISBN 0-471-16015-6. Руководство по ремонту 1461544 .
- ^ Лассак, М. (1993). «Аппроксимация выпуклых тел прямоугольниками». Geometriae Dedicata . 47 : 111–117. DOI : 10.1007 / BF01263495 . S2CID 119508642 .
- ^ а б Сантало, Л. (1961). «Sobre los sistemas completetos de desigualdades entre tres elementos de una figura convxa planas». Mathematicae Notae . 17 : 82–104.
- ^ а б в Бранденберг, Рене; Гонсалес Мерино, Бернардо (2017). «Полная 3-мерная диаграмма Бляшке-Сантало» . Математические неравенства и приложения (2): 301–348. DOI : 10,7153 / миа-20-22 . ISSN 1331-4343 .
- ^ Пустое множество имеет важное значение в дополнение Минковского, так как пустое множество аннулирует все остальные подмножества: Для каждого подмножества S векторного пространства, его сумма с пустым множеством пусто:.
- ^ Теорема 3 (страницы 562–563): Крейн, М .; Шмулян В. (1940). «О правильно выпуклых множествах в пространстве, сопряженном с банаховым пространством». Анналы математики . Вторая серия. 41 . С. 556–583. DOI : 10.2307 / 1968735 . JSTOR 1968735 .
- ^ О коммутативности сложения Минковского и выпуклости см. Теорему 1.1.2 (стр. 2–3) в книге Шнайдера; это ссылка обсуждается много литературы на выпуклые оболочки из Минковского sumsets в его «сложении Глава 3 Минковских» (стр 126-196): Шнайдер, Рольф (1993). Выпуклые тела: теория Брунна – Минковского . Энциклопедия математики и ее приложений. 44 . Кембридж: Издательство Кембриджского университета. С. xiv + 490. ISBN 0-521-35220-7. Руководство по ремонту 1216521 .
- ^ Лемма 5.3: Алипрантис, CD; Граница, KC (2006). Бесконечномерный анализ, Автостопом . Берлин: Springer. ISBN 978-3-540-29587-7.
- ^ Зэлинеску, К. (2002). Выпуклый анализ в общих векторных пространствах . Ривер Эдж, Нью-Джерси: World Scientific Publishing Co., Inc. стр. 7 . ISBN 981-238-067-1. Руководство по ремонту 1921556 .
- ^ Роулинз GJE и Вуд D, "Орто-выпуклость и ее обобщения", в: Computational Morphology , 137-152. Эльзевир , 1988.
- ^ Мункрес, Джеймс ; Топология , Прентис Холл; 2-е издание (28 декабря 1999 г.). ISBN 0-13-181629-2 .
- ^ ван Де Вел, Марсель LJ (1993). Теория выпуклых структур . Математическая библиотека Северной Голландии. Амстердам: North-Holland Publishing Co., стр. Xvi + 540. ISBN 0-444-81505-8. Руководство по ремонту 1234493 .
Внешние ссылки
- «Выпуклое подмножество» . Энциклопедия математики . EMS Press . 2001 [1994].
- Лекции по выпуклым множествам , примечания Нильса Лауритцена, в Орхусском университете , март 2010 г.