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

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

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

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

Определения

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

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

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

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

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

Алгоритмы

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

См. также

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

Литература

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

Примечания