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

редактировать

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

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

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

Содержание

1 Определение
2 Примеры
3 Специальные примеры
- 3.1 Аффинные выпуклые конусы
- 3.2 Полупространства
- 3.3 Многогранные и конечно порожденные конусы
- 3.4 Тупые, заостренные, плоские, выступающие и правильные конусы
- 3.5 Рациональные конусы
4 Двойной конус
5 Конструкции
6 Свойства
7 Частичные порядок, определяемый выпуклым конусом
8 См. также
9 Примечания
10 Ссылки

Определение

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

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

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

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

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

Примеры

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

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

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

Для векторного пространства V пустое множество, пространство V и любое линейное подпространство в V являются выпуклыми конусами.
коническая комбинация конечного или бесконечного набора векторов в $R n {\ displaystyle \ mathbb {R} ^ {n}}$ $\ mathbb {R} ^ {n}$ представляет собой выпуклый конус.
касательные конусы выпуклого множества - это выпуклые конусы.
Множество

{x ∈ R 2 ∣ x 2 ≥ 0, x 1 = 0} ∪ {x ∈ R 2 ∣ Икс 1 ≥ 0, Икс 2 знак равно 0} {\ Displaystyle \ left \ {х \ 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 \}}

{\ displaystyle \ left \ {x \ in \ mathbb {R} ^ {2} \ mid x_ {2} \ geq 0, x_ {1} = 0 \ right \} \ чашка \ left \ {x \ in \ mathbb {R} ^ {2} \ mid x_ {1} \ geq 0, x_ {2} = 0 \ right \}}

конус, но не выпуклый конус

Нормальный конус

{(x, r) ∈ R d + 1 ∣ ‖ x ‖ ≤ r} {\ displaystyle \ left \ {(x, r) \ in \ mathbb {R} ^ {d +1} \ mid \ | x \ | \ leq r \ right \}}

{\ displaystyle \ left \ {(x, r) \ in \ mathbb {R} ^ {d + 1} \ mid \ | x \ | \ leq r \ вправо \}}

- выпуклый конус.

Целое Сечение двух выпуклых конусов в одном векторном пространстве снова является выпуклым конусом, но их объединение может не быть единым.
Класс выпуклых конусов также замкнут при произвольных линейных отображениях. В частности, если C - выпуклый конус, то и его противоположность $- C {\ displaystyle -C}$ ${\ displaystyle -C}$ и $C ∩ - C {\ displaystyle C \ cap -C}$ ${\ displaystyle C \ cap -C}$ - наибольшее линейное подпространство, содержащееся в C.
Набор положительно полуопределенных матриц.
Набор неотрицательных непрерывных функций представляет собой выпуклый конус.

Специальные примеры

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

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

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

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

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

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

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

Конус C является полиэдральным, если это коническая комбинация конечного числа векторов (это свойство также называется конечно-порожденным ). Т.е. существует набор векторов ${v 1,…, vk} {\ displaystyle \ {v_ {1}, \ ldots, v_ {k} \}}$ ${\ displaystyle \ {v_ {1}, \ ldots, v_ {k} \}}$ , так что $C = {a 1 v 1 + ⋯ + akvk ∣ ai ∈ R ≥ 0, vi ∈ R n} {\ 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 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 {\ displaystyle A}$ $A$ такой, что $C = {x ∈ R n ∣ A x ≥ 0} {\ displaystyle C = \ {x \ in \ mathbb {R} ^ {n} \ mid Ax \ geq 0 \}}$ ${\ displaystyle 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 равно всему векторному пространству.

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

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

Тип конуса, представляющий особый интерес для чистых математиков, - это частично упорядоченный набор рациональных конусов. «Рациональные конусы - важные объекты в торической алгебраической геометрии, комбинаторной коммутативной алгебре, геометрической комбинаторике, целочисленном программировании».. Этот объект возникает, когда мы изучаем конусы в $R d {\ displaystyle \ mathbb {R} ^ {d}}$ $\ mathbb {R} ^ {d}$ вместе с lattice $Z d {\ displaystyle \ mathbb {Z} ^ {d}}$ ${\ displaystyle \ mathbb {Z} ^ {d}}$ . Конус называется рациональным (здесь мы предполагаем «заостренный», как определено выше), если все его генераторы имеют целочисленные координаты, т. Е. Если $C {\ displaystyle C}$ $C$ - рациональный конус, тогда $C = {a 1 v 1 + ⋯ + akvk ∣ ai ∈ R +, vi ∈ Z d} {\ displaystyle C = \ {a_ {1} v_ {1 } + \ cdots + a_ {k} v_ {k} \ mid a_ {i} \ in \ mathbb {R} _ {+}, v_ {i} \ in \ mathbb {Z} ^ {d} \}}$ ${\ displaystyle 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 ∈ V ∣ ∀ w ∈ C, ⟨w, v⟩ ≥ 0}, {\ displaystyle C ^ { *} = \ {v \ in V \ mid \ forall w \ in C, \ langle w, v \ rangle \ geq 0 \},}

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

который всегда является выпуклым конусом.

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

C ∗: = { v ∈ V ∗ ∣ ∀ w ∈ C, v (w) ≥ 0}. {\ displaystyle C ^ {*}: = \ left \ {v \ in V ^ {*} \ mid \ forall w \ in C, v (w) \ geq 0 \ right \}.}

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

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

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

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

Конструкции

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

NK (x) = {p ∈ V: ∀ x ∗ ∈ K, ⟨p, x ∗ - x⟩ ≤ 0}. {\ displaystyle N_ {K} (x) = \ left \ {p \ in V \;: \; \ forall x ^ {*} \ in K, \ langle p, x ^ {*} - x \ rangle \ leq 0 \ right \}.}

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

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

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

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

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

TK (x) = NK ∗ (x) = def {y ∈ V | ∀ ξ ∈ NK (x) : ⟨Y, ξ⟩ ⩽ 0} {\ displaystyle T_ {K} (x) = N_ {K} ^ {*} (x) {\ overset {\ underset {\ mathrm {def}} {}} {=} } \ {y \ in V | \ forall \ xi \ in N_ {K} (x): \ langle y, \ xi \ rangle \ leqslant 0 \}}

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

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

Свойства

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

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

A заостренный и выступающий выпуклый конус C индуцирует частичный порядок "≤" на V, определенный так, что $x ≤ y {\ displaystyle x \ leq y}$ $Икс \ Leq Y$ тогда и только тогда, когда $y - x ∈ C. {\ displaystyle yx \ in C.}$ ${\ displaystyle yx \ in C.}$ (Если конус плоский, то же определение дает просто предварительный порядок.) Суммы и положительные скалярные кратные действительных неравенств относительно этого порядка остаются в силе неравенства. Векторное пространство с таким порядком называется упорядоченным векторным пространством . Примеры включают заказ продукта на векторах с действительным знаком, $R n, {\ displaystyle \ mathbb {R} ^ {n},}$ ${\ displaystyle \ mathbb {R} ^ {n },}$ и порядок Loewner на положительно полуопределенных матрицах. Такой порядок обычно встречается в позитивном полуопределенном программировании.

См. Также

Примечания

Литература

Бурбаки, Николас (1987). Топологические векторные пространства. Элементы математики. Берлин, Нью-Йорк: Springer-Verlag. ISBN 978-3-540-13627-9.
; (2011). Топологические векторные пространства. Чистая и прикладная математика (Второе изд.). Бока-Ратон, Флорида: CRC Press. ISBN 978-1584888666. OCLC 144216834.
Рокафеллар, Р. Т. (1997) [1970]. Анализ выпуклости. Принстон, Нью-Джерси: Издательство Принстонского университета. ISBN 1-4008-7317-7.
Шефер, Гельмут Х. ; (1999). Топологические векторные пространства. GTM. 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. MR 1921556.