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

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

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

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

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

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

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

Определения

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

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

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

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

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

Примеры

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

Свойства

• Пустое множество и все пространство являются выпуклыми множествами. Поскольку пустое пространство и все пространство являются также и замкнутыми множествами, то они также являются замкнутыми выпуклыми множествами.
• Совокупность всех выпуклых множеств линейного пространства по отношению порядка образованного отношением включения является частично упорядоченным множеством с минимальным элементом, являющимся пустым множеством и максимальным элементом равным всему пространству. Такое же утверждение справедливо и для совокупности замкнутых выпуклых множеств.
• Выпуклое множество в топологическом линейном пространстве является связным и линейно связным, гомотопически эквивалентным точке.
• В терминах связности, выпуклое множество можно определить так: множество выпукло, если его пересечение с любой (вещественной) прямой связно.
• Пусть $K$ — выпуклое множество в линейном пространстве. Тогда для любых элементов $u_1,u_2,\dots ,u_r$ принадлежащих $K$ и для всех неотрицательных ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_r$, таких что ${\lambda }_1+{\lambda }_2+\dots +{\lambda }_r=1$, вектор

  $w=\sum _{k=1}^r{\lambda }_k{u}_k$

принадлежит $K$.

Вектор $w$ называется выпуклой комбинацией элементов $u_1,u_2,\dots ,u_r$.

• Пересечение любой совокупности выпуклых множеств является выпуклым множеством. Поскольку операция пересечения обладает также свойствами ассоциативности и коммутативности, совокупность выпуклых множеств по операции пересечения образует коммутативную полугруппу. Эта полугруппа содержит единицу, равную всему пространству. Таким образом совокупность выпуклых множеств является моноидом по операции пересечения.
• Из замкнутости семейства выпуклых множеств по операции пересечения следует, что для любого подмножества $A$ линейного пространства существует наименьшее выпуклое множество, его содержащее. Это множество является пересечением всех выпуклых множеств, содержащих $A$, и называется выпуклой оболочкой множества $A$. Обозначается $coA$, $co(A)$, а также $\mathrm{Conv}A$.
  • Выпуклая оболочка выпуклого множества совпадает с самим множеством.
  • Выпуклая оболочка замкнутого множества является замкнутым (и выпуклым) множеством.
  • Выпуклая оболочка множества $K$ совпадает с множеством всех выпуклых линейных комбинаций векторов $K$, $u_1,u_2,\dots ,u_r\in K$:

  $w=\sum _{k=1}^r{\lambda }_k{u}_k$, где ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_r$ неотрицательные числа, такие что ${\lambda }_1+{\lambda }_2+\dots +{\lambda }_r=1$.

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

$(X,X^{*})⩾(X^{*},X^{*})$.

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

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

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

Алгоритмы

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

См. также

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

Литература

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