Выпуклое множество
(перенаправлено с «Выпуклое тело»)
Выпуклое множество в аффинном или векторном пространстве — множество, в котором все точки отрезка, образуемого любыми двумя точками данного множества, также принадлежат данному множеству.
Граница выпуклого множества всегда является выпуклой кривой. Пересечение всех выпуклых множеств, содержащих данное подмножество A евклидова пространства, называется выпуклой оболочкой A. Это наименьшее выпуклое множество, содержащее A.
Выпуклая функция — это вещественнозначная функция, определённая на интервале со свойством, что ее надграфик (множество точек на графике функции или над ним) является выпуклым множеством. Выпуклое программирование — это подраздел оптимизации, изучающая проблему минимизации выпуклых функций над выпуклыми множествами. Раздел математики, посвященный изучению свойств выпуклых множеств и выпуклых функций, называется выпуклым анализом.
Выпуклые множества играют важную роль во многих оптимизационных задачах[1].
Определения
Пусть [math]\displaystyle{ A }[/math] — аффинное или векторное пространство над полем вещественных чисел [math]\displaystyle{ \mathbb{R} }[/math].
Множество [math]\displaystyle{ K\subset A }[/math] называется выпуклым, если вместе с любыми двумя точками [math]\displaystyle{ x,\;y\in K }[/math] множеству [math]\displaystyle{ K }[/math] принадлежат все точки отрезка [math]\displaystyle{ xy }[/math], соединяющего в пространстве [math]\displaystyle{ A }[/math] точки [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math]. Этот отрезок можно представить как
- [math]\displaystyle{ \bigcup\limits_{t\in[0;\;1]}\{x+t\cdot\overrightarrow{xy}\}. }[/math]
Связанные определения
Множество [math]\displaystyle{ K }[/math] векторного пространства [math]\displaystyle{ V }[/math] называется абсолютно выпуклым, если оно выпукло и уравновешенно.
Примеры
- Выпуклые подмножества множества [math]\displaystyle{ \R }[/math] (множество вещественных чисел) представляют собой интервалы из [math]\displaystyle{ \R }[/math].
- Примерами выпуклых подмножеств в двумерном евклидовом пространстве ([math]\displaystyle{ \R^2 }[/math]) являются правильные многоугольники.
- Примерами выпуклых подмножеств в трёхмерном евклидовом пространстве ([math]\displaystyle{ \R^3 }[/math]) являются архимедовы тела и правильные многогранники.
- Тела Кепплера — Пуансо (правильные звездообразные многогранники) являются примерами невыпуклых множеств.
Свойства
- Пустое множество и все пространство являются выпуклыми множествами. Поскольку пустое пространство и все пространство являются также и замкнутыми множествами, то они также являются замкнутыми выпуклыми множествами.
- Совокупность всех выпуклых множеств линейного пространства по отношению порядка образованного отношением включения является частично упорядоченным множеством с минимальным элементом, являющимся пустым множеством и максимальным элементом равным всему пространству. Такое же утверждение справедливо и для совокупности замкнутых выпуклых множеств.
- Выпуклое множество в топологическом линейном пространстве является связным и линейно связным, гомотопически эквивалентным точке.
- В терминах связности, выпуклое множество можно определить так: множество выпукло, если его пересечение с любой (вещественной) прямой связно.
- Пусть [math]\displaystyle{ K }[/math] — выпуклое множество в линейном пространстве. Тогда для любых элементов [math]\displaystyle{ u_1,\;u_2,\;\ldots,\;u_r }[/math] принадлежащих [math]\displaystyle{ K }[/math] и для всех неотрицательных [math]\displaystyle{ \lambda_1,\;\lambda_2,\;\ldots,\;\lambda_r }[/math], таких что [math]\displaystyle{ \lambda_1+\lambda_2+\ldots+\lambda_r=1 }[/math], вектор
- [math]\displaystyle{ w=\sum_{k=1}^r\lambda_k u_k }[/math]
- принадлежит [math]\displaystyle{ K }[/math].
- Вектор [math]\displaystyle{ w }[/math] называется выпуклой комбинацией элементов [math]\displaystyle{ u_1,\;u_2,\;\ldots,\;u_r }[/math].
- Пересечение любой совокупности выпуклых множеств является выпуклым множеством. Поскольку операция пересечения обладает также свойствами ассоциативности и коммутативности, совокупность выпуклых множеств по операции пересечения образует коммутативную полугруппу. Эта полугруппа содержит единицу, равную всему пространству. Таким образом совокупность выпуклых множеств является моноидом по операции пересечения.
- Из замкнутости семейства выпуклых множеств по операции пересечения следует, что для любого подмножества [math]\displaystyle{ A }[/math] линейного пространства существует наименьшее выпуклое множество, его содержащее. Это множество является пересечением всех выпуклых множеств, содержащих [math]\displaystyle{ A }[/math], и называется выпуклой оболочкой множества [math]\displaystyle{ A }[/math]. Обозначается [math]\displaystyle{ co A }[/math], [math]\displaystyle{ co(A) }[/math], а также [math]\displaystyle{ \operatorname{Conv}A }[/math].
- Выпуклая оболочка выпуклого множества совпадает с самим множеством.
- Выпуклая оболочка замкнутого множества является замкнутым (и выпуклым) множеством.
- Выпуклая оболочка множества [math]\displaystyle{ K }[/math] совпадает с множеством всех выпуклых линейных комбинаций векторов [math]\displaystyle{ K }[/math], [math]\displaystyle{ u_1,\;u_2,\;\ldots,\;u_r \in K }[/math]:
- [math]\displaystyle{ w=\sum_{k=1}^r\lambda_k u_k }[/math], где [math]\displaystyle{ \lambda_1,\;\lambda_2,\;\ldots,\;\lambda_r }[/math] неотрицательные числа, такие что [math]\displaystyle{ \lambda_1+\lambda_2+\ldots+\lambda_r=1 }[/math].
- Любой вектор [math]\displaystyle{ X\in \operatorname{Conv} K }[/math], где [math]\displaystyle{ K }[/math] — подмножество [math]\displaystyle{ n }[/math] - мерного линейного пространства [math]\displaystyle{ E^n }[/math], может быть представлен в виде выпуклой комбинации не более чем [math]\displaystyle{ n+1 }[/math] векторов множества [math]\displaystyle{ K }[/math]. [1] Это утверждение называется теоремой Каратеодори о выпуклой оболочке.
- Пусть [math]\displaystyle{ \Omega\subset E^n }[/math] — некоторое замкнутое выпуклое множество. Тогда найдётся точка [math]\displaystyle{ X^*\in \Omega }[/math] такая, что для всех [math]\displaystyle{ X\in \Omega }[/math] выполняется
- [math]\displaystyle{ (X, X^* ) \geqslant (X^*, X^* ) }[/math].[1]
- Для произвольного замкнутого выпуклого множества [math]\displaystyle{ C }[/math] и не принадлежащей ему точки [math]\displaystyle{ P }[/math] существует гиперплоскость, разделяющая [math]\displaystyle{ C }[/math] и [math]\displaystyle{ P }[/math].[1] Это утверждение называется теоремой об отделимости[1], а также теоремой об опорной гиперплоскости. Теорема об опорной гиперплоскости является частным случаем теоремы Хана — Банаха функционального анализа.
- Из теоремы об опорной гиперплоскости следует, что для выпуклого замкнутого множества [math]\displaystyle{ C }[/math] и находящейся вне множества [math]\displaystyle{ C }[/math] точки [math]\displaystyle{ P }[/math] существует замкнутое полупространство (множеств точек в пространстве, лежащих с одной стороны гиперплоскости, включая также саму гиперплоскость) [math]\displaystyle{ H }[/math], включающее [math]\displaystyle{ C }[/math] и не содержащее [math]\displaystyle{ P }[/math]. Из этого следует, что все замкнутые выпуклые множества могут быть образованы пересечениями замкнутых полупространств.
- Теорема Хелли: Предположим, что в конечном семействе выпуклых подмножеств [math]\displaystyle{ \R^d }[/math], пересечение любых [math]\displaystyle{ d+1 }[/math] из них непусто. Тогда пересечение всех подмножеств из этого семейства непусто.
- Любое выпуклое множество единичной площади в [math]\displaystyle{ \R^2 }[/math] можно целиком заключить в некоторый треугольник площади 2[2].
- Теорема Крейна — Мильмана. Выпуклый компакт [math]\displaystyle{ K }[/math] в локально выпуклом пространстве [math]\displaystyle{ L }[/math] совпадает с замыканием выпуклой оболочки множества своих крайних точек [math]\displaystyle{ E(K) }[/math].
Вариации и обобщения
- Без каких-либо изменений определение верно и для аффинных пространств над произвольным расширением поля вещественных чисел.
Алгоритмы
Алгоритм Дикстры — нахождение точки из пересечения выпуклых множеств.
См. также
- Выпуклая функция
- Выпуклое метрическое пространство
- Выпуклый анализ
- Звёздная область
- Лемма Шепли — Фолкмана
Литература
- Яглом И. М., Болтянский В. Г. Выпуклые фигуры. — М.—Л.: ГТТИ, 1951. — 343 с. — (Библиотека математического кружка, вып. 4).
- Лейхтвейс, К. Выпуклые множества. — М.: Наука, 1985. — 336 с.
- Половинкин Е. С., Балашов М. В.. Элементы выпуклого и сильно выпуклого анализа. — М.: ФИЗМАТЛИТ, 2004. — 416 с. — ISBN 5-9221-0499-3..
- Тиморин В. А. Комбинаторика выпуклых многогранников. — М.: МЦНМО, 2002. — 16 с. — ISBN 5-94057-024-0..
- Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. — Москва: Главная редакция физико-математической литературы изд-ва «Наука», 1972. — 368 с.
Примечания
- ↑ 1,0 1,1 1,2 1,3 1,4 Демьянов, Малоземов, 1972.
- ↑ Weisstein, Eric W. Triangle Circumscribing (англ.) на сайте Wolfram MathWorld.