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

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

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

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

Граница выпуклого множества всегда является выпуклой кривой. Пересечение всех выпуклых множеств, содержащих данное подмножество A евклидова пространства, называется выпуклой оболочкой A. Это наименьшее выпуклое множество, содержащее A.

Выпуклая функция — это вещественнозначная функция, определённая на интервале со свойством, что ее надграфик (множество точек на графике функции или над ним) является выпуклым множеством. Выпуклое программирование — это подраздел оптимизации, изучающая проблему минимизации выпуклых функций над выпуклыми множествами. Раздел математики, посвященный изучению свойств выпуклых множеств и выпуклых функций, называется выпуклым анализом.

Выпуклые множества играют важную роль во многих оптимизационных задачах^[1].

Определения

Пусть ${\displaystyle A}$ — аффинное или векторное пространство над полем вещественных чисел ${\displaystyle \mathbb {R} }$.

Множество ${\displaystyle K\subset A}$ называется выпуклым, если вместе с любыми двумя точками ${\displaystyle x,\;y\in K}$ множеству ${\displaystyle K}$ принадлежат все точки отрезка ${\displaystyle xy}$, соединяющего в пространстве ${\displaystyle A}$ точки ${\displaystyle x}$ и ${\displaystyle y}$. Этот отрезок можно представить как

${\displaystyle \bigcup \limits _{t\in [0;\;1]}\{x+t\cdot {\overrightarrow {xy}}\}.}$

Связанные определения

Множество ${\displaystyle K}$ векторного пространства ${\displaystyle V}$ называется абсолютно выпуклым, если оно выпукло и уравновешенно.

Примеры

• Выпуклые подмножества множества ${\displaystyle \mathbb {R} }$ (множество вещественных чисел) представляют собой промежутки из ${\displaystyle \mathbb {R} }$.
• Примерами выпуклых подмножеств в двумерном евклидовом пространстве (${\displaystyle \mathbb {R} ^{2}}$) являются правильные многоугольники.
• Примерами выпуклых подмножеств в трёхмерном евклидовом пространстве (${\displaystyle \mathbb {R} ^{3}}$) являются архимедовы тела и правильные многогранники.
• Тела Кепплера — Пуансо (правильные звездообразные многогранники) являются примерами невыпуклых множеств.

Свойства

• Пустое множество и все пространство являются выпуклыми множествами. Поскольку пустое пространство и все пространство являются также и замкнутыми множествами, то они также являются замкнутыми выпуклыми множествами.
• Совокупность всех выпуклых множеств линейного пространства по отношению порядка образованного отношением включения является частично упорядоченным множеством с минимальным элементом, являющимся пустым множеством и максимальным элементом равным всему пространству. Такое же утверждение справедливо и для совокупности замкнутых выпуклых множеств.
• Выпуклое множество в топологическом линейном пространстве является связным и линейно связным, гомотопически эквивалентным точке.
• В терминах связности, выпуклое множество можно определить так: множество выпукло, если его пересечение с любой (вещественной) прямой связно.
• Пусть ${\displaystyle K}$ — выпуклое множество в линейном пространстве. Тогда для любых элементов ${\displaystyle u_{1},\;u_{2},\;\ldots ,\;u_{r}}$ принадлежащих ${\displaystyle K}$ и для всех неотрицательных ${\displaystyle \lambda _{1},\;\lambda _{2},\;\ldots ,\;\lambda _{r}}$, таких что ${\displaystyle \lambda _{1}+\lambda _{2}+\ldots +\lambda _{r}=1}$, вектор

  ${\displaystyle w=\sum _{k=1}^{r}\lambda _{k}u_{k}}$

принадлежит ${\displaystyle K}$.

Вектор ${\displaystyle w}$ называется выпуклой комбинацией элементов ${\displaystyle u_{1},\;u_{2},\;\ldots ,\;u_{r}}$.

• Пересечение любой совокупности выпуклых множеств является выпуклым множеством. Поскольку операция пересечения обладает также свойствами ассоциативности и коммутативности, совокупность выпуклых множеств по операции пересечения образует коммутативную полугруппу. Эта полугруппа содержит единицу, равную всему пространству. Таким образом совокупность выпуклых множеств является моноидом по операции пересечения.
• Из замкнутости семейства выпуклых множеств по операции пересечения следует, что для любого подмножества ${\displaystyle A}$ линейного пространства существует наименьшее выпуклое множество, его содержащее. Это множество является пересечением всех выпуклых множеств, содержащих ${\displaystyle A}$, и называется выпуклой оболочкой множества ${\displaystyle A}$. Обозначается ${\displaystyle coA}$, ${\displaystyle co(A)}$, а также ${\displaystyle \operatorname {Conv} A}$.
  • Выпуклая оболочка выпуклого множества совпадает с самим множеством.
  • Выпуклая оболочка замкнутого множества является замкнутым (и выпуклым) множеством.
  • Выпуклая оболочка множества ${\displaystyle K}$ совпадает с множеством всех выпуклых линейных комбинаций векторов ${\displaystyle K}$, ${\displaystyle u_{1},\;u_{2},\;\ldots ,\;u_{r}\in K}$:

  ${\displaystyle w=\sum _{k=1}^{r}\lambda _{k}u_{k}}$, где ${\displaystyle \lambda _{1},\;\lambda _{2},\;\ldots ,\;\lambda _{r}}$ неотрицательные числа, такие что ${\displaystyle \lambda _{1}+\lambda _{2}+\ldots +\lambda _{r}=1}$.

  • Любой вектор ${\displaystyle X\in \operatorname {Conv} K}$, где ${\displaystyle K}$ — подмножество ${\displaystyle n}$ - мерного линейного пространства ${\displaystyle E^{n}}$, может быть представлен в виде выпуклой комбинации не более чем ${\displaystyle n+1}$ векторов множества ${\displaystyle K}$. ^[1] Это утверждение называется теоремой Каратеодори о выпуклой оболочке.
• Пусть ${\displaystyle \Omega \subset E^{n}}$ — некоторое замкнутое выпуклое множество. Тогда найдётся точка ${\displaystyle X^{*}\in \Omega }$ такая, что для всех ${\displaystyle X\in \Omega }$ выполняется

${\displaystyle (X,X^{*})\geqslant (X^{*},X^{*})}$.^[1]

• Для произвольного замкнутого выпуклого множества ${\displaystyle C}$ и не принадлежащей ему точки ${\displaystyle P}$ существует гиперплоскость, разделяющая ${\displaystyle C}$ и ${\displaystyle P}$.^[1] Это утверждение называется теоремой об отделимости^[1], а также теоремой об опорной гиперплоскости. Теорема об опорной гиперплоскости является частным случаем теоремы Хана — Банаха функционального анализа.
• Из теоремы об опорной гиперплоскости следует, что для выпуклого замкнутого множества ${\displaystyle C}$ и находящейся вне множества ${\displaystyle C}$ точки ${\displaystyle P}$ существует замкнутое полупространство (множеств точек в пространстве, лежащих с одной стороны гиперплоскости, включая также саму гиперплоскость) ${\displaystyle H}$, включающее ${\displaystyle C}$ и не содержащее ${\displaystyle P}$. Из этого следует, что все замкнутые выпуклые множества могут быть образованы пересечениями замкнутых полупространств.
• Теорема Хелли: Предположим, что в конечном семействе выпуклых подмножеств ${\displaystyle \mathbb {R} ^{d}}$, пересечение любых ${\displaystyle d+1}$ из них непусто. Тогда пересечение всех подмножеств из этого семейства непусто.
• Любое выпуклое множество единичной площади в ${\displaystyle \mathbb {R} ^{2}}$ можно целиком заключить в некоторый треугольник площади 2^[2].
• Теорема Крейна — Мильмана. Выпуклый компакт ${\displaystyle K}$ в локально выпуклом пространстве ${\displaystyle L}$ совпадает с замыканием выпуклой оболочки множества своих крайних точек ${\displaystyle E(K)}$.
• Замкнутое множество ${\displaystyle K}$ евклидова пространсва ${\displaystyle \mathbb {E} ^{d}}$ является выпуклым тогда и только тогда, когда для любой точки ${\displaystyle x\in \mathbb {E} ^{d}}$ найдётся единственная ближайшая к ней точка ${\displaystyle x^{*}\in K}$.
  • В этом случае проекция ${\displaystyle \mathbb {E} ^{d}\to K}$ определяемая как ${\displaystyle x\mapsto x^{*}}$ является коротким отображением; то есть

    ${\displaystyle |x-y|\geqslant |x^{*}-y^{*}|}$

для любых ${\displaystyle x,y\in \mathbb {E} ^{d}}$.

Вариации и обобщения

• Без каких-либо изменений определение верно и для аффинных пространств над произвольным расширением поля вещественных чисел.

Алгоритмы

Алгоритм Дикстры — нахождение точки из пересечения выпуклых множеств.

См. также

• Выпуклая функция
• Выпуклое метрическое пространство
• Выпуклый анализ
• Звёздная область
• Лемма Шепли — Фолкмана

Литература

• Яглом И. М., Болтянский В. Г. Выпуклые фигуры (рус.). — М.—Л.: ГТТИ, 1951. — 343 с. — (Библиотека математического кружка, вып. 4).
• Лейхтвейс, К. Выпуклые множества. — М.: Наука, 1985. — 336 с.
• Половинкин Е. С., Балашов М. В.. Элементы выпуклого и сильно выпуклого анализа. — М.: ФИЗМАТЛИТ, 2004. — 416 с. — ISBN 5-9221-0499-3..
• Тиморин В. А. Комбинаторика выпуклых многогранников. — М.: МЦНМО, 2002. — 16 с. — ISBN 5-94057-024-0..
• Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. — Москва: Главная редакция физико-математической литературы изд-ва «Наука», 1972. — 368 с.

Примечания

1. Демьянов, Малоземов, 1972.
2. Weisstein, Eric W. Triangle Circumscribing (англ.) на сайте Wolfram MathWorld.