В геометрии подмножество евклидова пространства или, в более общем смысле , аффинное пространство над действительными числами , является выпуклым, если для любых двух точек в подмножестве подмножество содержит весь соединяющий их отрезок прямой . Эквивалентно, выпуклое множество или выпуклая область — это подмножество, которое пересекает каждую линию в один сегмент линии (возможно, пустой). [1] [2] Например, сплошной куб представляет собой выпуклое множество, но все, что является полым или имеет углубление, например, в форме полумесяца , не является выпуклым.
Граница выпуклого множества на плоскости всегда является выпуклой кривой . Пересечение всех выпуклых множеств, содержащих данное подмножество A евклидова пространства, называется выпуклой оболочкой A . Это наименьшее выпуклое множество, содержащее A.
Выпуклая функция — это вещественная функция , определенная на интервале , обладающая тем свойством, что ее надграфик (множество точек на графике функции или над ним ) является выпуклым множеством. Выпуклая минимизация — это подобласть оптимизации , которая изучает проблему минимизации выпуклых функций над выпуклыми множествами. Раздел математики, посвященный изучению свойств выпуклых множеств и выпуклых функций, называется выпуклым анализом .
Понятие выпуклого множества можно обобщить, как описано ниже.
Пусть S — векторное пространство или аффинное пространство над действительными числами или, в более общем плане, над некоторым упорядоченным полем (сюда входят евклидовы пространства, которые являются аффинными пространствами). Подмножество C из S является выпуклым , если для всех x и y в C отрезок , соединяющий x и y, включен в C .
Это означает, что аффинная комбинация (1 − t ) x + ty принадлежит C для всех x, y в C и t в интервале [0, 1] . Отсюда следует, что выпуклость инвариантна относительно аффинных преобразований . Кроме того, из этого следует, что выпуклое множество в вещественном или комплексном топологическом векторном пространстве линейно связно (и, следовательно, также связно ).
Множество C естьстрого выпуклый, если каждая точка отрезка, соединяющегоxиy, кроме конечных точек, находится внутритопологическойвнутренностиC. Замкнутое выпуклое подмножество является строго выпуклым тогда и только тогда, когда каждая егограничная точкаявляетсякрайней точкой.[3]
Множество C абсолютно выпукло, если оно выпукло и уравновешено .
Выпуклые подмножества R (множество действительных чисел) — это интервалы и точки R . Некоторыми примерами выпуклых подмножеств евклидовой плоскости являются сплошные правильные многоугольники , сплошные треугольники и пересечения сплошных треугольников. Некоторыми примерами выпуклых подмножеств евклидова трехмерного пространства являются архимедовы тела и платоновые тела . Многогранники Кеплера -Пуансо являются примерами невыпуклых множеств.
Множество, которое не является выпуклым, называется невыпуклым множеством . Многоугольник , который не является выпуклым многоугольником , иногда называют вогнутым многоугольником [4] , а в некоторых источниках термин «вогнутый набор» обычно используется для обозначения невыпуклого набора [5] , но большинство авторитетных источников запрещают такое использование. [6] [7]
Дополнение выпуклого множества, такое как надграфик вогнутой функции , иногда называют обратно-выпуклым множеством , особенно в контексте математической оптимизации . [8]
Учитывая r точек u 1 , ..., ur в выпуклом множестве S и r неотрицательных чисел λ 1 , ..., λ r таких, что λ 1 + ... + λ r = 1 , аффинная комбинация
Такая аффинная комбинация называется выпуклой комбинацией u 1 , ... , ur .
Совокупность выпуклых подмножеств векторного пространства, аффинного пространства или евклидова пространства обладает следующими свойствами: [9] [10]
Замкнутые выпуклые множества — это выпуклые множества, содержащие все свои предельные точки . Их можно охарактеризовать как пересечения замкнутых полупространств (множеств точек в пространстве, лежащих на гиперплоскости и по одну ее сторону ).
Из только что сказанного ясно, что такие пересечения выпуклы и тоже будут замкнутыми множествами. Чтобы доказать обратное, т. е. любое замкнутое выпуклое множество можно представить как такое пересечение, нужна опорная теорема о гиперплоскости в виде того, что для данного замкнутого выпуклого множества C и точки P вне его существует замкнутое полупространство H , которое содержит C , а не P. Теорема о опорной гиперплоскости является частным случаем теоремы Хана–Банаха функционального анализа .
Пусть C — выпуклое тело на плоскости (выпуклое множество, внутренность которого непуста). Мы можем вписать прямоугольник r в C так, что гомотетическая копия R прямоугольника r описана вокруг C . Положительный коэффициент гомотетии не превышает 2 и: [11]
Набор всех плоских выпуклых тел можно параметризовать с точки зрения диаметра выпуклого тела D , его внутреннего радиуса r (самый большой круг, содержащийся в выпуклом теле) и его радиуса описанной окружности R (наименьший круг, содержащий выпуклое тело). Фактически, это множество можно описать набором неравенств, заданных [12], [13]
В качестве альтернативы набор также можно параметризовать по его ширине (наименьшему расстоянию между любыми двумя различными параллельными опорными гиперплоскостями), периметру и площади. [12] [13]
Пусть X — топологическое векторное пространство и выпукло.
Каждое подмножество A векторного пространства содержится в наименьшем выпуклом множестве (называемом выпуклой оболочкой A ) , а именно в пересечении всех выпуклых множеств, содержащих A. Оператор выпуклой оболочки Conv() обладает характерными свойствами оператора выпуклой оболочки :
Операция выпуклой оболочки необходима для того, чтобы набор выпуклых множеств образовал решетку , в которой операция « соединения » представляет собой выпуклую оболочку объединения двух выпуклых множеств.
В реальном векторном пространстве сумма Минковского двух (непустых) множеств, S 1 и S 2 , определяется как набор S 1 + S 2 , образованный путем поэлементного сложения векторов из наборов слагаемых.
Для сложения Минковского нулевое множество {0} , содержащее только нулевой вектор 0, имеет особое значение : для каждого непустого подмножества S векторного пространства
Сложение Минковского хорошо работает по отношению к операции взятия выпуклых оболочек, как показывает следующее предложение:
Пусть S1 , S2 — подмножества вещественного векторного пространства, выпуклая оболочка их суммы Минковского — это сумма Минковского их выпуклых оболочек .
Этот результат справедлив в более общем смысле для каждого конечного набора непустых множеств:
В математической терминологии операции суммирования Минковского и формирования выпуклых оболочек являются коммутирующими операциями. [15] [16]
Сумма Минковского двух компактных выпуклых множеств компактна. Сумма выпуклого компакта и выпуклого замкнутого множества замкнута. [17]
Следующая знаменитая теорема, доказанная Дьедонне в 1966 году, дает достаточное условие замкнутости разности двух замкнутых выпуклых подмножеств. [18] Он использует концепцию конуса рецессии непустого выпуклого подмножества S , определяемого как:
Теорема (Дьедонне). Пусть A и B — непустые, замкнутые и выпуклые подмножества локально выпуклого топологического векторного пространства, которое является линейным подпространством. Если A или B локально компактны, то A − B замкнуто .
Понятие выпуклости в евклидовом пространстве можно обобщить, изменив определение в тех или иных аспектах. Используется общее название «обобщенная выпуклость», поскольку полученные объекты сохраняют определенные свойства выпуклых множеств.
Пусть C — множество в вещественном или комплексном векторном пространстве. C является выпуклой звездой (звездообразной), если существует x 0 в C такой, что отрезок прямой от x 0 до любой точки y в C содержится в C . Следовательно, непустое выпуклое множество всегда звездно-выпуклое, но звездчатое множество не всегда выпуклое.
Примером обобщенной выпуклости является ортогональная выпуклость . [19]
Множество S в евклидовом пространстве называется ортогонально-выпуклым или орто-выпуклым , если любой отрезок, параллельный любой из координатных осей, соединяющих две точки S , полностью лежит внутри S. Легко доказать, что пересечение любого набора ортовыпуклых множеств является ортовыпуклым. Справедливы и некоторые другие свойства выпуклых множеств.
Определение выпуклого множества и выпуклой оболочки естественным образом распространяется на неевклидовы геометрии, определяя геодезически выпуклое множество как такое, которое содержит геодезические, соединяющие любые две точки множества.
Выпуклость может быть распространена на полностью упорядоченное множество X , наделенное порядковой топологией . [20]
Пусть Y ⊆ X. _ Подпространство Y является выпуклым множеством, если для каждой пары точек a , b в Y такой, что a ⩽ b , интервал [ a , b ] = { x ∈ X | a ≤ x ≤ b } содержится в Y . То есть Y является выпуклым тогда и только тогда , когда для всех a , b в Y , a ⩽ b влечет [ a , b ] ⊆ Y.
Выпуклое множество вообще не связно: контрпример дается подпространством {1,2,3} в Z , которое одновременно выпукло и несвязно.
Понятие выпуклости можно обобщить и на другие объекты, если в качестве аксиом выбрать определенные свойства выпуклости .
Для данного множества X выпуклость над X — это совокупность 𝒞 подмножеств X , удовлетворяющая следующим аксиомам: [9] [10] [ 21]
Элементы 𝒞 называются выпуклыми множествами, а пара ( X , 𝒞 ) называется выпуклым пространством . Для обычной выпуклости справедливы первые две аксиомы, а третья тривиальна.
Альтернативное определение абстрактной выпуклости, более подходящее для дискретной геометрии , см. в разделе « Выпуклая геометрия , связанная с антиматроидами» .
Выпуклость можно обобщить как абстрактную алгебраическую структуру: пространство является выпуклым, если можно взять выпуклые комбинации точек.
Часто встречающаяся путаница - это «вогнутый набор». Вогнутые и выпуклые функции обозначают определенные классы функций, а не множеств, тогда как выпуклое множество обозначает определенный класс множеств, а не класс функций. «Вогнутое множество» путает множества с функциями.
Не существует такого понятия, как вогнутый набор.