For faster navigation, this Iframe is preloading the Wikiwand page for Выпуклое множество.

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

Материал из Википедии — свободной энциклопедии

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

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

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

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

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

Определения

[править | править код]

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

Множество называется выпуклым, если вместе с любыми двумя точками множеству принадлежат все точки отрезка , соединяющего в пространстве точки и . Этот отрезок можно представить как

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

[править | править код]

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

  • Пустое множество и все пространство являются выпуклыми множествами. Поскольку пустое пространство и все пространство являются также и замкнутыми множествами, то они также являются замкнутыми выпуклыми множествами.
  • Совокупность всех выпуклых множеств линейного пространства по отношению порядка образованного отношением включения является частично упорядоченным множеством с минимальным элементом, являющимся пустым множеством и максимальным элементом равным всему пространству. Такое же утверждение справедливо и для совокупности замкнутых выпуклых множеств.
  • Выпуклое множество в топологическом линейном пространстве является связным и линейно связным, гомотопически эквивалентным точке.
  • В терминах связности, выпуклое множество можно определить так: множество выпукло, если его пересечение с любой (вещественной) прямой связно.
  • Пусть  — выпуклое множество в линейном пространстве. Тогда для любых элементов принадлежащих и для всех неотрицательных , таких что , вектор
принадлежит .
Вектор называется выпуклой комбинацией элементов .
  • Пересечение любой совокупности выпуклых множеств является выпуклым множеством. Поскольку операция пересечения обладает также свойствами ассоциативности и коммутативности, совокупность выпуклых множеств по операции пересечения образует коммутативную полугруппу. Эта полугруппа содержит единицу, равную всему пространству. Таким образом совокупность выпуклых множеств является моноидом по операции пересечения.
  • Из замкнутости семейства выпуклых множеств по операции пересечения следует, что для любого подмножества линейного пространства существует наименьшее выпуклое множество, его содержащее. Это множество является пересечением всех выпуклых множеств, содержащих , и называется выпуклой оболочкой множества . Обозначается , , а также .
    • Выпуклая оболочка выпуклого множества совпадает с самим множеством.
    • Выпуклая оболочка замкнутого множества является замкнутым (и выпуклым) множеством.
    • Выпуклая оболочка множества совпадает с множеством всех выпуклых линейных комбинаций векторов , :
    , где неотрицательные числа, такие что .
    • Любой вектор , где — подмножество - мерного линейного пространства , может быть представлен в виде выпуклой комбинации не более чем векторов множества . [1] Это утверждение называется теоремой Каратеодори о выпуклой оболочке.
  • Пусть — некоторое замкнутое выпуклое множество. Тогда найдётся точка такая, что для всех выполняется
.[1]
  • Для произвольного замкнутого выпуклого множества и не принадлежащей ему точки существует гиперплоскость, разделяющая и .[1] Это утверждение называется теоремой об отделимости[1], а также теоремой об опорной гиперплоскости. Теорема об опорной гиперплоскости является частным случаем теоремы Хана — Банаха функционального анализа.
  • Из теоремы об опорной гиперплоскости следует, что для выпуклого замкнутого множества и находящейся вне множества точки существует замкнутое полупространство (множеств точек в пространстве, лежащих с одной стороны гиперплоскости, включая также саму гиперплоскость) , включающее и не содержащее . Из этого следует, что все замкнутые выпуклые множества могут быть образованы пересечениями замкнутых полупространств.
  • Теорема Хелли: Предположим, что в конечном семействе выпуклых подмножеств , пересечение любых из них непусто. Тогда пересечение всех подмножеств из этого семейства непусто.
  • Любое выпуклое множество единичной площади в можно целиком заключить в некоторый треугольник площади 2[2].
  • Теорема Крейна — Мильмана. Выпуклый компакт в локально выпуклом пространстве совпадает с замыканием выпуклой оболочки множества своих крайних точек .
  • Замкнутое множество евклидова пространсва является выпуклым тогда и только тогда, когда для любой точки найдётся единственная ближайшая к ней точка .
    • В этом случае проекция определяемая как является коротким отображением; то есть
для любых .

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

[править | править код]

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

Литература

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

Примечания

[править | править код]
  1. 1 2 3 4 5 Демьянов, Малоземов, 1972.
  2. Weisstein, Eric W. Triangle Circumscribing (англ.) на сайте Wolfram MathWorld.
{{bottomLinkPreText}} {{bottomLinkText}}
Выпуклое множество
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?