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

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

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

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

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

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

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

Определения

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

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

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

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

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

Примеры

• Выпуклые подмножества множества $ℝ$ (множество вещественных чисел) представляют собой промежутки из $ℝ$.
• Примерами выпуклых подмножеств в двумерном евклидовом пространстве (${ℝ}^2$) являются правильные многоугольники.
• Примерами выпуклых подмножеств в трёхмерном евклидовом пространстве (${ℝ}^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$. Шаблон:Sfn Это утверждение называется теоремой Каратеодори о выпуклой оболочке.
• Пусть $\Omega \subset E^n$ — некоторое замкнутое выпуклое множество. Тогда найдётся точка $X^{\ast }\in \Omega$ такая, что для всех $X\in \Omega$ выполняется

$(X,X^{\ast })⩾(X^{\ast },X^{\ast })$.Шаблон:Sfn

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

    $|x-y|⩾|x^{\ast }-y^{\ast }|$

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

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

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

Алгоритмы

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга.
• Шаблон:Книга.
• Шаблон:Книга