Русская Википедия:Выпуклое множество
Выпуклое множество в аффинном или векторном пространстве — множество, в котором все точки отрезка, образуемого любыми двумя точками данного множества, также принадлежат данному множеству.
Граница выпуклого множества всегда является выпуклой кривой. Пересечение всех выпуклых множеств, содержащих данное подмножество Шаблон:Mvar евклидова пространства, называется выпуклой оболочкой Шаблон:Mvar. Это наименьшее выпуклое множество, содержащее Шаблон:Mvar.
Выпуклая функция — это вещественнозначная функция, определённая на интервале со свойством, что ее надграфик (множество точек на графике функции или над ним) является выпуклым множеством. Выпуклое программирование — это подраздел оптимизации, изучающая проблему минимизации выпуклых функций над выпуклыми множествами. Раздел математики, посвященный изучению свойств выпуклых множеств и выпуклых функций, называется выпуклым анализом.
Выпуклые множества играют важную роль во многих оптимизационных задачахШаблон:Sfn.
Определения
Пусть <math>A</math> — аффинное или векторное пространство над полем вещественных чисел <math>\mathbb{R}</math>.
Множество <math>K\subset A</math> называется выпуклым, если вместе с любыми двумя точками <math>x,\;y\in K</math> множеству <math>K</math> принадлежат все точки отрезка <math>xy</math>, соединяющего в пространстве <math>A</math> точки <math>x</math> и <math>y</math>. Этот отрезок можно представить как
- <math>\bigcup\limits_{t\in[0;\;1]}\{x+t\cdot\overrightarrow{xy}\}.</math>
Связанные определения
Множество <math>K</math> векторного пространства <math>V</math> называется абсолютно выпуклым, если оно выпукло и уравновешенно.
Примеры
- Выпуклые подмножества множества <math>\R</math> (множество вещественных чисел) представляют собой промежутки из <math>\R</math>.
- Примерами выпуклых подмножеств в двумерном евклидовом пространстве (<math>\R^2</math>) являются правильные многоугольники.
- Примерами выпуклых подмножеств в трёхмерном евклидовом пространстве (<math>\R^3</math>) являются архимедовы тела и правильные многогранники.
- Тела Кепплера — Пуансо (правильные звездообразные многогранники) являются примерами невыпуклых множеств.
Свойства
- Пустое множество и все пространство являются выпуклыми множествами. Поскольку пустое пространство и все пространство являются также и замкнутыми множествами, то они также являются замкнутыми выпуклыми множествами.
- Совокупность всех выпуклых множеств линейного пространства по отношению порядка образованного отношением включения является частично упорядоченным множеством с минимальным элементом, являющимся пустым множеством и максимальным элементом равным всему пространству. Такое же утверждение справедливо и для совокупности замкнутых выпуклых множеств.
- Выпуклое множество в топологическом линейном пространстве является связным и линейно связным, гомотопически эквивалентным точке.
- В терминах связности, выпуклое множество можно определить так: множество выпукло, если его пересечение с любой (вещественной) прямой связно.
- Пусть <math>K</math> — выпуклое множество в линейном пространстве. Тогда для любых элементов <math>u_1,\;u_2,\;\ldots,\;u_r</math> принадлежащих <math>K</math> и для всех неотрицательных <math>\lambda_1,\;\lambda_2,\;\ldots,\;\lambda_r </math>, таких что <math>\lambda_1+\lambda_2+\ldots+\lambda_r=1</math>, вектор
- <math>w=\sum_{k=1}^r\lambda_k u_k</math>
- принадлежит <math>K</math>.
- Вектор <math>w</math> называется выпуклой комбинацией элементов <math>u_1,\;u_2,\;\ldots,\;u_r</math>.
- Пересечение любой совокупности выпуклых множеств является выпуклым множеством. Поскольку операция пересечения обладает также свойствами ассоциативности и коммутативности, совокупность выпуклых множеств по операции пересечения образует коммутативную полугруппу. Эта полугруппа содержит единицу, равную всему пространству. Таким образом совокупность выпуклых множеств является моноидом по операции пересечения.
- Из замкнутости семейства выпуклых множеств по операции пересечения следует, что для любого подмножества <math>A</math> линейного пространства существует наименьшее выпуклое множество, его содержащее. Это множество является пересечением всех выпуклых множеств, содержащих <math>A</math>, и называется выпуклой оболочкой множества <math>A</math>. Обозначается <math>co A</math>, <math>co(A)</math>, а также <math>\operatorname{Conv}A</math>.
- Выпуклая оболочка выпуклого множества совпадает с самим множеством.
- Выпуклая оболочка замкнутого множества является замкнутым (и выпуклым) множеством.
- Выпуклая оболочка множества <math>K</math> совпадает с множеством всех выпуклых линейных комбинаций векторов <math> K</math>, <math>u_1,\;u_2,\;\ldots,\;u_r \in K</math>:
- <math>w=\sum_{k=1}^r\lambda_k u_k</math>, где <math>\lambda_1,\;\lambda_2,\;\ldots,\;\lambda_r </math> неотрицательные числа, такие что <math>\lambda_1+\lambda_2+\ldots+\lambda_r=1</math>.
- Любой вектор <math>X\in \operatorname{Conv} K</math>, где <math>K</math> — подмножество <math>n</math> - мерного линейного пространства <math>E^n</math>, может быть представлен в виде выпуклой комбинации не более чем <math>n+1</math> векторов множества <math>K</math>. Шаблон:Sfn Это утверждение называется теоремой Каратеодори о выпуклой оболочке.
- Пусть <math>\Omega\subset E^n</math> — некоторое замкнутое выпуклое множество. Тогда найдётся точка <math>X^*\in \Omega</math> такая, что для всех <math>X\in \Omega</math> выполняется
- <math>(X, X^* ) \geqslant (X^*, X^* ) </math>.Шаблон:Sfn
- Для произвольного замкнутого выпуклого множества <math>C</math> и не принадлежащей ему точки <math>P</math> существует гиперплоскость, разделяющая <math>C</math> и <math>P</math>.Шаблон:Sfn Это утверждение называется теоремой об отделимостиШаблон:Sfn, а также теоремой об опорной гиперплоскости. Теорема об опорной гиперплоскости является частным случаем теоремы Хана — Банаха функционального анализа.
- Из теоремы об опорной гиперплоскости следует, что для выпуклого замкнутого множества <math>C</math> и находящейся вне множества <math>C</math> точки <math>P</math> существует замкнутое полупространство (множеств точек в пространстве, лежащих с одной стороны гиперплоскости, включая также саму гиперплоскость) <math>H</math>, включающее <math>C</math> и не содержащее <math>P</math>. Из этого следует, что все замкнутые выпуклые множества могут быть образованы пересечениями замкнутых полупространств.
- Теорема Хелли: Предположим, что в конечном семействе выпуклых подмножеств <math>\R^d</math>, пересечение любых <math>d+1</math> из них непусто. Тогда пересечение всех подмножеств из этого семейства непусто.
- Любое выпуклое множество единичной площади в <math>\R^2</math> можно целиком заключить в некоторый треугольник площади 2[1].
- Теорема Крейна — Мильмана. Выпуклый компакт <math>K</math> в локально выпуклом пространстве <math>L</math> совпадает с замыканием выпуклой оболочки множества своих крайних точек <math>E(K)</math>.
Вариации и обобщения
- Без каких-либо изменений определение верно и для аффинных пространств над произвольным расширением поля вещественных чисел.
Алгоритмы
Алгоритм Дикстры — нахождение точки из пересечения выпуклых множеств.
См. также
- Выпуклая функция
- Выпуклое метрическое пространство
- Выпуклый анализ
- Звёздная область
- Лемма Шепли — Фолкмана
Литература
Примечания
