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

Выпуклый конус (голубой). Внутри него светло-красный выпуклый конус состоит из всех точек αx + βy с α, β > 0 , для изображенных x и y . Кривые в правом верхнем углу символизируют бесконечность регионов.

В линейной алгебре конус ( иногда называемый линейным конусом, чтобы отличить его от конусов других типов) — это подмножество векторного пространства , замкнутое относительно положительного скалярного умножения; то есть C является конусом, если $x\in C$ подразумевает $sx\in C$ для каждого положительного скаляра s . Конус не обязательно должен быть выпуклым или даже выглядеть как конус в евклидовом пространстве .

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

В данной статье рассматривается только случай скаляров в упорядоченном поле.

Определение

Подмножество ) , C векторного пространства V над упорядоченным полем F является конусом (или иногда называемым конусом если для каждого x в C и положительного скаляра α в F произведение αx находится в C. линейным Обратите внимание, что некоторые авторы определяют конус со скаляром α, охватывающим все неотрицательные скаляры (а не все положительные скаляры, не включающие 0).

Конус C является выпуклым конусом если αx + βy принадлежит C для любых положительных скаляров α , β и любых x , y из C. , Конус C выпуклый тогда и только тогда, когда C + C ⊆ C .

Эта концепция имеет смысл для любого векторного пространства, которое допускает концепцию «положительного» скаляра, например, пространства над рациональными , алгебраическими или (чаще) действительными числами . Также обратите внимание, что скаляры в определении являются положительными, что означает, что начало координат не обязательно должно принадлежать C. Некоторые авторы используют определение, которое гарантирует, что начало координат принадлежит C . Из-за параметров масштабирования α и β конусы бесконечны по протяженности и не ограничены.

Если C — выпуклый конус, то для любого положительного скаляра α и любого x из C вектор $\alpha x={\tfrac {\alpha }{2}}x+{\tfrac {\alpha }{2}}x\in C.$ Отсюда следует, что выпуклый конус С является частным случаем линейного конуса .

Из указанного выше свойства следует, что выпуклый конус можно определить и как линейный конус, замкнутый относительно выпуклых комбинаций или непосредственно сложений . Более кратко, множество C является выпуклым конусом тогда и только тогда, когда αC = C и C + C = C для любого положительного скаляра α .

Примеры

Выпуклый конус, не являющийся конической оболочкой конечного числа образующих.

Выпуклый конус, созданный конической комбинацией трех черных векторов.

Конус (объединение двух лучей), не являющийся выпуклым конусом.

• Для векторного пространства V пространство V и любое линейное подпространство V пустое множество , являются выпуклыми конусами.
• Коническая оболочка конечного или бесконечного набора векторов в $\mathbb {R} ^{n}$ представляет собой выпуклый конус.
• Касательные конусы выпуклого множества являются выпуклыми конусами.
• Набор $$\left\{x\in \mathbb {R} ^{2}\mid x_{2}\geq 0,x_{1}=0\right\}\cup \left\{x\in \mathbb {R} ^{2}\mid x_{1}\geq 0,x_{2}=0\right\}$$ является конусом, но не выпуклым конусом.
• Нормальный конус $$\left\{(x,r)\in \mathbb {R} ^{d+1}\mid \|x\|\leq r\right\}$$ представляет собой выпуклый конус.
• Пересечение двух выпуклых конусов в одном и том же векторном пространстве снова является выпуклым конусом, но их объединение может не быть единым.
• Класс выпуклых конусов замкнут также относительно произвольных линейных отображений . В частности, если C — выпуклый конус, то и его противоположность — выпуклый конус. $-C$ и $C\cap -C$ является крупнейшим линейным подпространством, содержащимся в C .
• Множество положительных полуопределенных матриц .
• Множество неотрицательных непрерывных функций представляет собой выпуклый конус.

Особые примеры

Аффинные выпуклые конусы

Аффинный выпуклый конус — это множество, полученное в результате применения аффинного преобразования к выпуклому конусу. является перемещение выпуклого конуса точкой p : p + C. Типичным примером Технически такие преобразования могут давать неконусы. Например, если p = 0 , p + C не является линейным конусом. Однако его по-прежнему называют аффинным выпуклым конусом.

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

(Линейная) гиперплоскость — это множество вида $\{x\in V\mid f(x)=c\}$ где f — линейный функционал в векторном пространстве V. Замкнутое полупространство — это множество в виде $\{x\in V\mid f(x)\leq c\}$ или $\{x\in V\mid f(x)\geq c\},$ и аналогичным образом открытое полупространство использует строгое неравенство.

Полупространства (открытые или закрытые) представляют собой аффинные выпуклые конусы. Более того (в конечных измерениях) любой выпуклый конус C, не являющийся всем пространством V, должен содержаться в некотором замкнутом полупространстве H пространства V ; это частный случай леммы Фаркаса .

Многогранные и конечно порожденные конусы

Многогранные конусы — это особые виды конусов, которые можно определить несколькими способами:

• Конус C называется многогранником, если он является конической оболочкой конечного числа векторов (это свойство также называется конечно-порожденным ). То есть существует набор векторов $\{v_{1},\ldots ,v_{k}\}$ так что $C=\{a_{1}v_{1}+\cdots +a_{k}v_{k}\mid a_{i}\in \mathbb {R} _{\geq 0},v_{i}\in \mathbb {R} ^{n}\}$.
• Конус называется многогранником, если он является пересечением конечного числа полупространств, на границе которых имеется 0 (это было доказано Вейлем в 1935 г.).
• Конус C называется многогранником, если существует некоторая матрица $A$ такой, что $C=\{x\in \mathbb {R} ^{n}\mid Ax\geq 0\}$.
• Конус называется многогранником, если он является множеством решений системы однородных линейных неравенств. Алгебраически каждое неравенство определяется строкой A. матрицы Геометрически каждое неравенство определяет полупространство, проходящее через начало координат.

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

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

Два представления многогранного конуса — неравенствами и векторами — могут иметь весьма разные размеры. Например, рассмотрите конус всех неотрицательных n на матриц размером n с равными суммами строк и столбцов. Представление неравенства требует n ² неравенств и 2( n − 1) уравнений, но векторное представление требует n ! векторов (см. теорему Биркгофа-фон Неймана ). Может случиться и обратное — число векторов может быть полиномиальным, а количество неравенств — экспоненциальным.

Два представления вместе обеспечивают эффективный способ решить, находится ли данный вектор в конусе: чтобы показать, что он находится в конусе, достаточно представить его как коническую комбинацию определяющих векторов; чтобы показать, что он не находится в конусе, достаточно привести одно определяющее неравенство, которое он нарушает. Этот факт известен как лемма Фаркаша .

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

Тупые, заостренные, плоские, выступающие и правильные конусы.

Согласно приведенному выше определению, если C — выпуклый конус, то C ∪ { 0 } тоже является выпуклым конусом. Говорят, что выпуклый конус указано, если 0 находится в C и тупой, 0 не находится в C. если Тупые конусы можно исключить из определения выпуклого конуса, заменив «неотрицательный» на «положительный» в условии α, β.

Конус называется плоским , если он содержит некоторый ненулевой вектор x и его противоположность − x, что означает, что C содержит линейное подпространство размерности не менее одной и заметное в противном случае. Тупой выпуклый конус обязательно выпуклый, но обратное не обязательно верно. Выпуклый конус C является выпуклым тогда и только тогда, когда C ∩ − C ⊆ { 0 }. Конус C называется порождающим, если $C-C=\{x-y\mid x\in C,y\in C\}$ равно всему векторному пространству.

Некоторые авторы требуют, чтобы выступающие конусы были заостренными. Термин «заостренный» также часто используется для обозначения замкнутого конуса, который не содержит полной линии (т. е. нет нетривиального подпространства объемлющего векторного пространства V или того, что называется выступающим конусом). Термин « собственный ( выпуклый ) конус» определяется по-разному, в зависимости от контекста и автора. Это часто означает конус, который удовлетворяет другим свойствам, например, является выпуклым, закрытым, заостренным, выступающим и полномерным. Из-за различий в определениях для определения этих терминов следует обращаться к контексту или источнику.

Рациональные конусы

Тип конуса, представляющий особый интерес для чистых математиков, — это частично упорядоченный набор рациональных конусов. «Рациональные конусы являются важными объектами в торической алгебраической геометрии, комбинаторной коммутативной алгебре, геометрической комбинаторике, целочисленном программировании». Этот объект возникает, когда мы изучаем конусы в $\mathbb {R} ^{d}$ вместе с решеткой $\mathbb {Z} ^{d}$. Конус называется рациональным (здесь мы предполагаем «заостренным», как определено выше), если все его образующие имеют целочисленные координаты, т. е. если $C$ является рациональным конусом, то $C=\{a_{1}v_{1}+\cdots +a_{k}v_{k}\mid a_{i}\in \mathbb {R} _{+}\}$ для некоторых $v_{i}\in \mathbb {Z} ^{d}$.

Двойной конус

Основная статья: двойной конус

Пусть C ⊂ V — множество (не обязательно выпуклое) в вещественном векторном пространстве V, снабженное скалярным произведением . (Непрерывный или топологический) двойственный конус к C — это множество

$C^{*}=\{v\in V\mid \forall w\in C,\langle w,v\rangle \geq 0\},$

который всегда представляет собой выпуклый конус. Здесь, $\langle w,v\rangle$ является парой двойственности между C и V , т.е. $\langle w,v\rangle =v(w)$.

В более общем смысле, (алгебраический) двойственный конус к C ⊂ V в линейном пространстве V является подмножеством двойственного пространства V*, определяемого следующим образом:

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

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

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

Если C равен своему двойственному конусу, то C называется самодвойственным . Можно сказать, что конус самодвойственный безотносительно к какому-либо данному внутреннему продукту, если существует внутренний продукт, по отношению к которому он равен своему двойственному по первому определению.

Конструкции

• Для замкнутого выпуклого подмножества K гильбертова пространства V внешний нормальный конус к множеству K в точке x в K определяется выражением

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

• Для замкнутого выпуклого подмножества K в V касательный конус (или контингентный конус ) к множеству K в точке x задается формулой

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

• Учитывая замкнутое выпуклое подмножество K гильбертова пространства V , касательный конус к множеству K в точке x в K можно определить как полярный конус к внешнему нормальному конусу. $N_{K}(x)$:

  $T_{K}(x)=N_{K}^{o}(x)\ {\overset {\underset {\mathrm {def} }{}}{=}}\ \{y\in V\mid \forall \xi \in N_{K}(x):\langle y,\xi \rangle \leqslant 0\}$

И нормальный, и касательный конус обладают свойством замкнутости и выпуклости.

Они являются важными понятиями в области выпуклой оптимизации , вариационных неравенств и проектируемых динамических систем .

Характеристики

Если C — непустой выпуклый конус в X , то линейная оболочка C равна C — C , а наибольшее векторное подпространство X , содержащееся в C, равно C ∩ (− C ).

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

Заостренный и выпуклый конус C индуцирует частичный порядок «≥» на V , определенный так, что $x\geq y$ тогда и только тогда, когда $x-y\in C.$ (Если конус плоский, то же определение дает просто предварительный порядок .) Суммы и положительные скалярные кратные действительных неравенств относительно этого порядка остаются действительными неравенствами. Векторное пространство с таким порядком называется упорядоченным векторным пространством . Примеры включают порядок произведения векторов с действительным знаком, $\mathbb {R} ^{n},$ и порядок Левнера на положительных полуопределенных матрицах. Такой порядок обычно встречается в полуопределенном программировании .

См. также

• Конус (значения)
  • Конус (геометрия)
  • Конус (топология)
• Лемма Вольфа
• Биполярная теорема
• Упорядоченное векторное пространство

Ссылки

• Бурбаки, Николя (1987). Топологические векторные пространства . Элементы математики. Берлин, Нью-Йорк: Springer-Verlag . ISBN  978-3-540-13627-9 .
• Наричи, Лоуренс; Бекенштейн, Эдвард (2011). Топологические векторные пространства . Чистая и прикладная математика (Второе изд.). Бока-Ратон, Флорида: CRC Press. ISBN  978-1584888666 . OCLC   144216834 .
• Рокафеллар, RT (1997) [1970]. Выпуклый анализ . Принстон, Нью-Джерси: Издательство Принстонского университета. ISBN  1-4008-7317-7 .
• Шефер, Хельмут Х .; Вольф, Манфред П. (1999). Топологические векторные пространства . ГТМ . Том. 8 (Второе изд.). Нью-Йорк, Нью-Йорк: Springer New York Выходные данные Springer. ISBN  978-1-4612-7155-0 . OCLC   840278135 .
• Тревес, Франсуа (2006) [1967]. Топологические векторные пространства, распределения и ядра . Минеола, Нью-Йорк: Dover Publications. ISBN  978-0-486-45352-1 . OCLC   853623322 .
• Залинеску, К. (2002). Выпуклый анализ в общих векторных пространствах . Ривер Эдж, Нью-Джерси: World Scientific. ISBN  981-238-067-1 . МР   1921556 .