Введение
В геометрии, множество, пересечение которого с каждой прямой является одним отрезком прямой. В геометрии, подмножество евклидова пространства или, в более общем случае, аффинного пространства над действительными числами, называется выпуклым, если для любых двух точек этого подмножества сам подмножество содержит весь отрезок прямой, соединяющий эти точки. Эквивалентно, выпуклое множество или выпуклая область – это подмножество, которое пересекает каждую прямую в один отрезок (возможно, пустой). Например, сплошный куб является выпуклым множеством, но любое тело с вогнутостью или углублением, например, в форме полумесяца, не является выпуклым. Граница выпуклого множества на плоскости всегда представляет собой выпуклую кривую. Пересечение всех выпуклых множеств, содержащих данное подмножество A евклидова пространства, называется выпуклой оболочкой A. Это наименьшее выпуклое множество, содержащее A. Выпуклой функцией называется функция, принимающая действительные значения и определенная на интервале, обладающая свойством, что её эпиграф (множество точек, лежащих на графике функции или выше него) является выпуклым множеством. Выпуклое программирование – это раздел оптимизации, изучающий задачу минимизации выпуклых функций на выпуклых множествах. Раздел математики, посвященный изучению свойств выпуклых множеств и выпуклых функций, называется выпуклым анализом. Понятие выпуклого множества может быть обобщено, как описано ниже.
In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex region is a subset that intersects every line into a single line segment (possibly empty). For example, a solid cube is a convex set, but anything that is hollow or has an indent, for example, a crescent shape, is not convex. The boundary of a convex set in the plane is always a convex curve. The intersection of all the convex sets that contain a given subset A of Euclidean space is called the convex hull of A. It is the smallest convex set containing A. A convex function is a real valued function defined on an interval with the property that its epigraph (the set of points on or above the graph of the function) is a convex set. Convex minimization is a subfield of optimization that studies the problem of minimizing convex functions over convex sets. The branch of mathematics devoted to the study of properties of convex sets and convex functions is called convex analysis. The notion of a convex set can be generalized as described below.
Определения
Пусть S — векторное пространство или аффинное пространство над действительными числами, или, в более общем случае, над некоторым упорядоченным полем (это включает в себя евклидовы пространства, которые являются аффинными пространствами). Подмножество C множества S является выпуклым, если для любых x и y из C отрезок, соединяющий x и y, содержится в C. Это означает, что аффинная комбинация (1 − t)x + ty принадлежит C для всех x, y из C и t из интервала [0, 1]. Это влечет за собой, что выпуклость инвариантна относительно аффинных преобразований. Кроме того, это влечет за собой, что выпуклое множество в реальном или комплексном топологическом векторном пространстве является связным по пути (и, следовательно, также связным). Множество C называется строго выпуклым, если каждая точка на отрезке, соединяющем x и y, отличная от конечных точек, лежит во внутренней топологической области C. Закрытое выпуклое подмножество является строго выпуклым тогда и только тогда, когда каждая его граничная точка является экстремальной точкой. Множество C называется абсолютно выпуклым, если оно выпуклое и сбалансированное.
This means that the affine combination (1 − t)x + ty belongs to C for all x,y in C and t in the interval [0, 1]. This implies that convexity is invariant under affine transformations. Further, it implies that a convex set in a real or complex topological vector space is path connected (and therefore also connected). A set C is strictly convex if every point on the line segment connecting x and y other than the endpoints is inside the topological interior of C. A closed convex subset is strictly convex if and only if every one of its boundary points is an extreme point. A set C is absolutely convex if it is convex and balanced.
Примеры
Выпуклые подмножества ℝ (множество вещественных чисел) — это интервалы и точки ℝ. Некоторые примеры выпуклых подмножеств евклидовой плоскости — это заполненные правильные многоугольники, заполненные треугольники и пересечения заполненных треугольников. Некоторые примеры выпуклых подмножеств трехмерного евклидова пространства — это архимедовы тела и платоновы тела. Полиэдры Кеплера — Пуансо являются примерами невыпуклых множеств.
Невыпуклый набор
Набор, который не является выпуклым, называется невыпуклым множеством. Многоугольник, который не является выпуклым многоугольником, иногда называют вогнутым многоугольником, а некоторые источники в более широком смысле используют термин "вогнутое множество" для обозначения невыпуклого множества, однако большинство специалистов не рекомендуют такое употребление. Дополнение выпуклого множества, например, эпиграф вогнутой функции, иногда называют обращенно-выпуклым множеством, особенно в контексте математической оптимизации.
Свойства
При заданных r точках u1, ..., ur в выпуклом множестве S и r неотрицательных чисел λ1, ..., λr таких, что их сумма равна 1, аффинная комбинация
nonnegative numbers λ1, , λr such that , the affine combination
принадлежит S. Поскольку определение выпуклого множества является частным случаем, когда r = 2, это свойство характеризует выпуклые множества. Такая аффинная комбинация называется выпуклой комбинацией точек u1, ..., ur.
Закрытые выпукловидные наборы
Закрытые выпуклые множества — это выпуклые множества, содержащие все свои предельные точки. Их можно охарактеризовать как пересечения замкнутых полупространств (множеств точек в пространстве, лежащих на гиперплоскости и по одну сторону от неё). Из вышесказанного следует, что такие пересечения являются выпуклыми и замкнутыми множествами. Чтобы доказать обратное, то есть что любое замкнутое выпуклое множество можно представить в виде такого пересечения, требуется теорема о поддерживающей гиперплоскости в формулировке, согласно которой для заданного замкнутого выпуклого множества C и точки P, лежащей вне его, существует замкнутое полупространство H, содержащее C, но не содержащее P. Теорема о поддерживающей гиперплоскости является частным случаем теоремы Хана — Банаха из функционального анализа.
Выпуклые множества и прямоугольники
Пусть C — выпуклое тело на плоскости (выпуклое множество с непустым внутренним пространством). В C можно вписать прямоугольник r, такой что гомотетическое изображение R прямоугольника r является описанным около C. Положительный коэффициент гомотетии не превосходит 2 и:
Диаграмма Бласке-Сантало
Множество всех плоских выпуклых тел может быть параметризовано с точки зрения диаметра выпуклого тела D, его внутренней радиуса r (наибольшего круга, содержащегося в выпуклом теле) и его внешней радиуса R (наименьшего круга, содержащего выпуклое тело). Фактически, это множество может быть описано системой неравенств, представленных ниже, и может быть визуализировано как образ функции g, которая отображает выпуклое тело в точку R² , задаваемую как (r/R, D/2R). Образ этой функции известен как диаграмма Блэка-Сантало (r, D, R).
and can be visualized as the image of the function g that maps a convex body to the 'R'^(2) point given by (r/R, D/2R). The image of this function is known a (r, D, R) Blachke Santaló diagram.
Сумма Минковского выпуклостей
Сумма Минковского двух компактных выпуклых множеств компактна. Сумма компактного выпуклого множества и замкнутого выпуклого множества замкнута. Следующая известная теорема, доказанная Дьёдонне в 1966 году, дает достаточное условие для того, чтобы разность двух замкнутых выпуклых подмножеств была замкнутой. В ней используется понятие конуса рецессии непустого выпуклого подмножества S, определяемого как:
где это множество является выпуклым конусом, содержащим 0 и удовлетворяющим условию: если S замкнуто и выпукло, то конус рецессии замкнут и для всех x, y.
Теорема (Дьёдонне). Пусть A и B – непустые, замкнутые и выпуклые подмножества локально выпуклого топологического векторного пространства, такие что A ∩ B является линейным подпространством. Если A или B локально компактны, то A − B замкнуто.
Обобщения и расширения для выпуклости
Понятие выпуклости в евклидовом пространстве может быть обобщено путем изменения определения в тех или иных аспектах. Используется общее название "обобщенная выпуклость", поскольку полученные объекты сохраняют определенные свойства выпуклых множеств.
Звездные выпуклые (звездные) наборы
Пусть C – множество в вещественном или комплексном векторном пространстве. Множество C называется звездообразным, если существует точка x0 ∈ C такая, что отрезок, соединяющий x0 с любой точкой y ∈ C, содержится в C. Следовательно, непустое выпуклое множество всегда является звездообразным, но звездообразное множество не всегда является выпуклым.
Ортогональная выпуклость
Примером обобщенной выпуклости является ортогональная выпуклость. Множество S в евклидовом пространстве называется ортогонально выпуклым или ортовыпуклым, если любой отрезок, параллельный какой-либо из координатных осей и соединяющий две точки множества S, полностью лежит внутри S. Легко доказать, что пересечение любого семейства ортовыпуклых множеств является ортовыпуклым. Некоторые другие свойства выпуклых множеств также справедливы.
Неевклидова геометрия
Определение выпуклого множества и выпуклой оболочки естественно распространяется на геометрии, отличные от евклидовой, определяя геодезически выпуклое множество как множество, содержащее геодезические, соединяющие любые две точки в этом множестве.
Топология порядка
Выпуклость может быть расширена на полностью упорядоченное множество X, наделенное топологией порядка. Пусть Y ⊆ X. Подпространство Y является выпуклым множеством, если для каждой пары точек a, b из Y, таких что a ≤ b, интервал [a, b] содержится в Y. То есть, Y является выпуклым тогда и только тогда, когда для всех a, b из Y, a ≤ b влечет [a, b] ⊆ Y. Выпуклое множество не является связным в общем случае: контрпример представляет собой подпространство {1, 2, 3} в Z, которое одновременно выпукло и не связно.
Выпуклые пространства
Выпуклость может быть обобщена как абстрактная алгебраическая структура: пространство считается выпуклым, если возможно построение выпуклых комбинаций точек.