Выпуклый конус

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

Выпуклый конус (светло-синий). Внутри него светло-красный замкнутый выпуклый конус, содержащий все точки ${\displaystyle \alpha x+\beta y}$ с ${\displaystyle \alpha ,\beta >0}$ для выделенных точек ${\displaystyle x}$ и ${\displaystyle y}$. Кривые в правом верхнем углу символизируют бесконечность областей.

Определение

Подмножество ${\displaystyle C}$ векторного пространства ${\displaystyle V}$ является выпуклым конусом, если ${\displaystyle \alpha x+\beta y}$ принадлежит ${\displaystyle C}$ для любых положительных скаляров ${\displaystyle \alpha ,\beta }$ и любых ${\displaystyle x,y}$ из ${\displaystyle C}$.

Определение можно записать более сжато: ${\displaystyle \alpha C+\beta C=C}$ для любых положительных чисел ${\displaystyle \alpha ,\beta }$.

Понятие имеет смысл для любых векторных пространств, в которых существует понятие «положительный» скаляр, такие как пространство над рациональными, алгебраическими или (чаще всего) вещественными числами.

Пустое множество, пространство ${\displaystyle V}$ и любое линейное подпространство пространства ${\displaystyle V}$ (включая тривиальное подпространство {0}), являются выпуклыми конусами по этому определению. Другими примерами служат множество всех произведений на положительное число произвольного вектора ${\displaystyle v}$ из ${\displaystyle V}$, или положительный ортант пространства ${\displaystyle \mathbb {R} ^{n}}$ (множество всех векторов, имеющих положительные координаты).

Более общий пример — множество всех векторов ${\displaystyle \lambda x}$, таких, что ${\displaystyle \lambda }$ положительный скаляр, а ${\displaystyle x}$ — элемент некоторого выпуклого подмножества ${\displaystyle X}$ пространства ${\displaystyle V}$. В частности, если ${\displaystyle V}$ — нормированное векторное пространство, а ${\displaystyle X}$ — открытый (соотв. замкнутый) шар в ${\displaystyle V}$, который не содержит 0, эта конструкция даёт открытый (соотв. замкнутый) выпуклый круговой конус.

Пересечение двух выпуклых конусов в том же векторном пространстве снова является выпуклым конусом, но объединение таковым может не быть.^[1] Класс выпуклых конусов замкнут относительно любых линейных отображений. В частности, если ${\displaystyle C}$ — выпуклый конус, то таковой и его противоположный ${\displaystyle -C}$, а ${\displaystyle C\cap -C}$ является наибольшим линейным подпространством, содержащимся в ${\displaystyle C}$ ^[2]. Такое подпространство называется лезвием.^[3]

Выпуклые конуса и линейные конуса

Если ${\displaystyle C}$ — выпуклый конус, то для любого положительного скаляра ${\displaystyle \alpha }$ и любого вектора ${\displaystyle x}$ из ${\displaystyle C}$ вектор ${\displaystyle \alpha x=(\alpha /2)x+(\alpha /2)x}$ лежит в ${\displaystyle C}$. Отсюда следует, что выпуклый конус ${\displaystyle C}$ является частным случаем линейного конуса^[англ.].

Альтернативные определения

Из сказанного выше следует, что выпуклый конус можно определить как линейный конус, замкнутый относительно выпуклых комбинаций, или просто относительно сложения. Более кратко — множество ${\displaystyle C}$ является выпуклым конусом тогда и только тогда, когда ${\displaystyle \alpha C=C}$ и ${\displaystyle C+C=C}$ для любого положительного скаляра ${\displaystyle \alpha }$.^[4]

Следует также отметить, что фразу «положительные скаляры ${\displaystyle \alpha ,\beta }$» в определении выпуклого конуса можно заменить на «неотрицательные скаляры ${\displaystyle \alpha ,\beta }$, не равные нулю одновременно».

Свойства выпуклого конуса

• Пересечение любого числа выпуклых конусов снова является выпуклым конусом. Тем самым выпуклые конусы образуют замкнутое семейство (по операции пересечения).
• Коническая оболочка ${\displaystyle \operatorname {pos} (X)}$ — это наименьший выпуклый конус, содержащий данное множество.

Тупые и острые конусы

Согласно вышеприведённым определениям, если ${\displaystyle C}$ является выпуклым конусом, то ${\displaystyle C\cup \{0\}}$ является выпуклым конусом тоже. Говорят, что выпуклый конус острый или тупой в зависимости от того, принадлежит ли ему нулевой вектор 0 или нет^[5]. Иногда употребляют термины заострённый и, соответственно, затупленный ^[4][6].

Тупые конусы можно исключить из определения выпуклого конуса, заменив слова «неотрицательные» на «положительные» в условиях, налагаемых на ${\displaystyle \alpha ,\beta }$. Термин «острый» часто используется в другом смысле — для замкнутых конусов, не содержащих полных прямых (то есть нетривиального подпространства окружающего пространства), то есть то, что ниже называется «выступающим» конусом.

Выступающие (острые) конусы

Говорят, что выпуклый конус является плоским, если он содержит некоторый ненулевой вектор ${\displaystyle x}$ и его противоположный ${\displaystyle -x}$, и выступающим в противном случае^[6]. Выступающие конуса часто называют также острыми.

Тупой выпуклый конус всегда является выступающим, но обратное не всегда верно. Выпуклый конус ${\displaystyle C}$ является выступающим в том и только в том случае, когда ${\displaystyle C\cap -C\subseteq \{0\}}$. То есть тогда и только тогда, когда ${\displaystyle C}$ не содержит нетривиального линейного подпространства ${\displaystyle V}$.

Полиэдральные конусы

В 1935 году Г.Вейль доказал равносильность следующих двух определений полиэдрального конуса:

• Полиэдральным конусом называется множество ${\displaystyle C=\{a_{1}v_{1}+\cdots +a_{k}v_{k}\mid a_{i}\in \mathbb {R} _{\geq 0},v_{i}\in \mathbb {R} ^{n}\}}$ линейных комбинаций с неотрицательными коэффициентами фиксированного конечного набора векторов ${\displaystyle v_{1},v_{2},\ldots ,v_{i}}$. Эти векторы называют порождающими конуса.
• Полиэдральным конусом называется пересечение конечного набора (замкнутых) полупространств, опорная гиперплоскость которых проходит через начало координат. Эквивалентно, можно говорить о множестве решений конечного набора однородных линейных неравенств.

Рациональные полиэдральные конусы

Полиэдральный конус называется рациональным, если все его порождающие имеют целочисленные координаты.

Полупространства

Гиперплоскость (линейная) пространства ${\displaystyle V}$ является максимальным возможным собственным линейным подпространством пространства ${\displaystyle V}$. Открытое (соотв. замкнутое) полупространство пространства ${\displaystyle V}$ — это подмножество ${\displaystyle H}$ пространства ${\displaystyle V}$, определённое условием ${\displaystyle L(x)>0}$ (соотв. ${\displaystyle L(x)\geqslant 0}$), где ${\displaystyle L}$ — любая линейная функция из ${\displaystyle V}$ в его поле скаляров. Гиперплоскость, определённая уравнением ${\displaystyle L(v)=0}$, является ограничивающей гиперплоскостью для ${\displaystyle H}$.

Полупространства (открытые или замкнутые) являются выпуклыми конусами. Однако любой выпуклый конус ${\displaystyle C}$, не являющийся всем пространством ${\displaystyle V}$, должен содержаться в некотором замкнутом полупространстве ${\displaystyle H}$ пространства ${\displaystyle V}$. Фактически топологически замкнутый выпуклый конус является пересечением всех замкнутых полупространств, содержащих его. Аналогичное утверждение верно для топологически открытого выпуклого конуса.

Совершенное полупространство пространства ${\displaystyle V}$ определяется рекурсивно следующим образом: если ${\displaystyle V}$ имеет размерность ноль, то это множество ${\displaystyle \{0\}}$, в противном случае это открытое полупространство ${\displaystyle H}$ пространства ${\displaystyle V}$ вместе с совершенным полупространством ограничивающей гиперплоскости для ${\displaystyle H}$^[7]. Иными словами, это аналог понятия флага для полупространств.

Любое совершенное полупространство является выступающим, и, более того, любой выступающий конус содержится в совершенном полупространстве. Другими словами, совершенные полупространства являются максимальными выступающими конусами (по включению). Можно показать, что любой острый выступающий конус (независимо от того, замкнут ли он топологически или открыт) является пересечением всех совершенных полупространств, включающих его.

Сечение и проекция выпуклых множеств

Плоское сечение

Аффинная гиперплоскость пространства ${\displaystyle V}$ — это любое подмножество пространства ${\displaystyle V}$ вида ${\displaystyle v+H}$, где ${\displaystyle v}$ — вектор в ${\displaystyle V}$, а ${\displaystyle H}$ — (линейная) гиперплоскость.

Следующее утверждение следует из свойства включения в полупространства. Пусть ${\displaystyle Q}$ — открытое полупространство в ${\displaystyle V}$ и ${\displaystyle A=H+v}$, где ${\displaystyle H}$ — граничная гиперплоскость ${\displaystyle Q}$, а ${\displaystyle v}$ — любой вектор в ${\displaystyle Q}$. Пусть ${\displaystyle C}$ — линейный конус, содержащийся в ${\displaystyle Q}$. Тогда ${\displaystyle C}$ является выпуклым конусом в том и только в том случае, когда множество ${\displaystyle C'=C\cap A}$ является выпуклым подмножеством гиперплоскости ${\displaystyle A}$ (то есть множеством, замкнутым относительно выпуклых комбинаций).

Вследствие этого результата все свойства выпуклых множеств аффинного пространства имеют аналог для выпуклых конусов, содержащихся в фиксированном открытом полупространстве.

Сферическое сечение

Если дана норма | • | в пространстве ${\displaystyle V}$, мы определяем единичную сферу в ${\displaystyle V}$ как множество

${\displaystyle S=\{x\in V\;:\;|x|=1\}.}$

Если значения | • | являются скалярами в ${\displaystyle V}$, то линейный конус ${\displaystyle C}$ в ${\displaystyle V}$ — это выпуклый конус в том и только в том случае, когда его сферическое сечение ${\displaystyle C\cap S}$ (множество его векторов с единичной нормой) является выпуклым подмножеством ${\displaystyle S}$ в следующем смысле: для любых двух векторов ${\displaystyle u,v\in C}$ с ${\displaystyle u\neq -v}$ все вектора на кратчайшем пути из ${\displaystyle u}$ в ${\displaystyle v}$ на ${\displaystyle S}$ лежат в ${\displaystyle C}$.

Двойственный конус

Основная статья: Двойственный конус

Пусть ${\displaystyle C\subset V}$ — выпуклый конус в вещественном векторном пространстве ${\displaystyle V}$, обладающем скалярным произведением. Двойственный конус к ${\displaystyle C}$ — это множество^[8][9]

${\displaystyle \{v\in V\;:\;\forall w\in C,\langle w,v\rangle \geqslant 0\}.}$

Он тоже является выпуклым конусом. Если ${\displaystyle C}$ совпадает со своим двойственным, ${\displaystyle C}$ называется самодвойственным.

Другое частое определение двойственного конуса для ${\displaystyle C\subset V}$ — это конус ${\displaystyle C^{\ast }}$ в сопряжённом пространстве ${\displaystyle V^{\ast }}$:

${\displaystyle C^{*}:=\left\{v\in V^{*}\;:\;\forall w\in C,v(w)\geqslant 0\right\}.}$

Другими словами, если ${\displaystyle V^{\ast }}$ — сопряжённое пространство пространства ${\displaystyle V}$, то двойственный конус — это множество линейных функций, неотрицательных на конусе ${\displaystyle C}$. Если мы примем, что ${\displaystyle V^{\ast }}$ — непрерывное сопряжённое пространство, то это множество непрерывных линейных функций, неотрицательных на ${\displaystyle C}$.^[10] Такое определение не требует наличия скалярного произведения в пространстве ${\displaystyle V}$.

В конечномерных пространствах оба определения двойственного конуса, по существу, эквивалентны, поскольку любому скалярному произведению сопоставляется линейный изоморфизм (невырожденное линейное отображение) из ${\displaystyle V^{\ast }}$ в ${\displaystyle V}$, и этот изоморфизм переводит двойственный конус (в ${\displaystyle V^{\ast }}$) из второго определения в двойственный конус из первого определения.

Частичный порядок, определённый выпуклым конусом

Острый выступающий выпуклый конус ${\displaystyle C}$ порождает частичный порядок «${\displaystyle \leqslant }$» на ${\displaystyle V}$, определяемый так, что ${\displaystyle x\leqslant y}$ тогда и только тогда, когда ${\displaystyle y-x\in C}$. (Если конус плоский, то же самое определение даёт просто предпорядок.) Суммы и умножение на положительный скаляр верного неравенства по отношению к этому порядку снова дают верные неравенства. Векторное пространство с таким порядком называется упорядоченным векторным пространством^[англ.]. Конус

${\displaystyle P=\left\{x:x\in V,x\geqslant 0\right\}.}$

называется положительным конусом^[6].

В качестве примеров можно привести порядковое произведение^{[англ.][11]} на вещественных векторах (${\displaystyle \mathbb {R} ^{n}}$) и порядок Лёвнера^[12]

Собственный выпуклый конус

Термин собственный (выпуклый) конус определяется различным образом в зависимости от контекста. Он часто означает выступающий выпуклый конус, не содержащий какую-либо гиперплоскость пространства ${\displaystyle V}$, возможно, с другими накладываемыми ограничениями, как, например, топологическую замкнутость (а вследствие этого, конус будет острым), или топологическую открытость (конус будет тупым)^[13]. Некоторые авторы используют термин «клин» для понятия, которое в этой статье обозначает выпуклый конус, и под термином «конус» понимается то, что в статье называется выступающим острым конусом, или то, что только что было названо собственным выпуклым конусом.

Примеры выпуклых конусов

• Пусть задано замкнутое выпуклое подмножество ${\displaystyle K}$ гильбертова пространства ${\displaystyle V}$, нормальный конус для множества ${\displaystyle K}$ из точки ${\displaystyle x}$ в ${\displaystyle K}$ задаётся формулой.^[2]

${\displaystyle N_{K}(x)=\left\{p\in V\;:\;\forall x^{*}\in K,\langle p,x-x^{*}\rangle \geqslant 0\right\}.}$

• Пусть задано замкнутое выпуклое подмножество ${\displaystyle K}$ пространства ${\displaystyle V}$, касательный конус^[англ.] к множеству ${\displaystyle K}$ из точки ${\displaystyle x}$ задаётся формулой^[14]

${\displaystyle T_{K}(x)={\overline {\bigcup _{h>0}{\tfrac {1}{h}}(K-x)}}.}$

• Пусть задано замкнутое выпуклое подмножество ${\displaystyle K}$ гильбертова пространства ${\displaystyle V}$, внешний нормальный конус к множеству ${\displaystyle K}$ из точки ${\displaystyle x}$ в ${\displaystyle K}$ задаётся формулой^[15]

${\displaystyle N_{K}(x)=\left\{p\in V\;:\;\forall x^{*}\in K,\langle p,x-x^{*}\rangle \leqslant 0\right\}.}$

• Пусть задано замкнутое выпуклое подмножество ${\displaystyle K}$ гильбертова пространства ${\displaystyle V}$, касательный конус к множеству ${\displaystyle K}$ в точке ${\displaystyle x}$ из ${\displaystyle K}$ можно определить как полярный конус к внешнему нормальному конусу ${\displaystyle N_{K}(x)}$:^[16][17]

Нормальные и касательные конусы замкнуты и выпуклы. Они являются важными концепциями в области выпуклого программирования, вариационных неравенств^[англ.] .

См. также

• Конус (топология)
• Лемма Фаркаша

Связанные комбинации

Подробнее см. Линейная комбинация § Аффинная, коническая и выпуклая комбинации

• Аффинная комбинация
• Выпуклая комбинация
• Линейная комбинация