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

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

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

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

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

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

Определение

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

Многогранные конусы — это особые виды конусов, которые можно определить несколькими способами: ^{[10] : 256–257.}

• Конус C называется многогранником, если он является конической оболочкой конечного числа векторов (это свойство также называется конечно-порожденным ). ^{[11] [12]} Т.е. существует набор векторов такой, что . ${\displaystyle \{v_{1},\ldots ,v_{k}\}}$ ${\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 называется многогранником, если существует такая матрица , что . ${\displaystyle A}$ ${\displaystyle C=\{x\in \mathbb {R} ^{n}\mid Ax\geq 0\}}$
• Конус называется многогранником, если он является множеством решений системы однородных линейных неравенств. Алгебраически каждое неравенство определяется строкой матрицы A. Геометрически каждое неравенство определяет полупространство, проходящее через начало координат.

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

Многогранные конусы играют центральную роль в теории представлений многогранников . Например, теорема о разложении многогранников утверждает, что каждый многогранник можно записать как сумму Минковского выпуклого многогранника и многогранного конуса. ^{[14] [15]} Многогранные конусы также играют важную роль в доказательстве связанной с ней конечной базисной теоремы для многогранников, которая показывает, что каждый многогранник является многогранником, а каждый ограниченный многогранник является многогранником. ^{[14] [16] [17]}

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

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

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

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

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

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

Некоторые авторы требуют, чтобы выступающие конусы были заостренными. ^[22] Термин «заостренный» также часто используется для обозначения замкнутого конуса, который не содержит полной линии (т. е. нет нетривиального подпространства окружающего векторного пространства V или того, что называется выступающим конусом). ^{[23] [24] [25]} Термин «собственный ( выпуклый ) конус» определяется по-разному, в зависимости от контекста и автора. Это часто означает конус, который удовлетворяет другим свойствам, например, является выпуклым, закрытым, заостренным, выступающим и полномерным. ^{[26] [27] [28]} Из-за различий в определениях для определения этих терминов следует обращаться к контексту или источнику.

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

Тип конуса, представляющий особый интерес для чистых математиков, — это частично упорядоченный набор рациональных конусов. «Рациональные конусы являются важными объектами в торической алгебраической геометрии, комбинаторной коммутативной алгебре, геометрической комбинаторике, целочисленном программировании». ^[29] Этот объект возникает, когда мы изучаем конусы вместе с решеткой . Конус называется рациональным (здесь мы предполагаем «заостренным», как определено выше), если все его образующие имеют целые координаты, т. е. если — рациональный конус, то . ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle \mathbb {Z} ^{d}}$ ${\displaystyle C}$ ${\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 — это множество

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

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

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

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

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

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

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

Конструкции

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

  ${\displaystyle 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 задается формулой

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

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

  ${\displaystyle 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 ). ^[32]

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

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

Смотрите также

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

Примечания

1. Бойд, Стивен; Ванденберге, Ливен (8 марта 2004 г.). Выпуклая оптимизация. Издательство Кембриджского университета. ISBN 978-0-521-83378-3.
2. Бернштейн, Деннис С. (26 июля 2009 г.). Матричная математика: теория, факты и формулы (второе изд.). Издательство Принстонского университета. п. 97. ИСБН 978-0691140391.
3. К. Залинеску (1 января 2002 г.). Выпуклый анализ в общих векторных пространствах. Всемирная научная. п. 1. ISBN 978-981-238-067-8.
4. Неф, Уолтер (1 января 1988 г.). Линейная алгебра. Курьерская корпорация. п. 35. ISBN 9780486657721.
5. Ито, Киёси (1 января 1993 г.). Энциклопедический словарь математики. МТИ Пресс. ISBN 9780262590204.
6. Рокафеллар, Ральф Тайрелл (29 апреля 2015 г.). Выпуклый анализ. Издательство Принстонского университета. п. 13. ISBN 9781400873173.
7. Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (6 декабря 2012 г.). Основы выпуклого анализа. Springer Science & Business Media. ISBN 9783642564680.
8. Алипрантис, Хараламбос Д.; Бордер, Ким К. (2 мая 2007 г.). Бесконечномерный анализ: Путеводитель для автостопа. Springer Science & Business Media. п. 197. ИСБН 9783540326960.
9. Рокафеллар, Ральф Тайрелл (29 апреля 2015 г.). Выпуклый анализ. Издательство Принстонского университета. п. 10. ISBN 9781400873173.
10. Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1, МР  0859549
11. Лоэра, Хесус А. Де; Хеммеке, Раймонд; Кеппе, Матиас (01 января 2012 г.). Алгебраические и геометрические идеи в теории дискретной оптимизации. СИАМ. ISBN 9781611972443.
12. Шрайвер, Александр (7 июля 1998 г.). Теория линейного и целочисленного программирования. Джон Уайли и сыновья. ISBN 9780471982326.
13. Брунс, Винфрид; Губеладзе, Иосиф (2009). Многогранники, кольца и K-теория (1-е изд.). Монографии Спрингера по математике. п. 3. ISBN 9780387763552.
14. Шрийвер, Александр (7 июля 1998 г.). Теория линейного и целочисленного программирования. Джон Уайли и сыновья. стр. 88–89. ISBN 9780471982326.
15. Конфорти, Микеле; Корнюжоль, Жерар; Замбелли, Джакомо (15 ноября 2014 г.). Целочисленное программирование. Спрингер. п. 111. ИСБН 9783319110080.
16. Корте, Бернхард; Виген, Йенс (11 ноября 2013 г.). Комбинаторная оптимизация: теория и алгоритмы. Springer Science & Business Media. п. 61. ИСБН 9783662217115.
17. Вильярреал, Рафаэль (26 марта 2015 г.). Мономиальные алгебры, второе издание. ЦРК Пресс. п. 9. ISBN 9781482234701.
18. Дхара, Анулекха; Датта, Джойдип (17 октября 2011 г.). Условия оптимальности в выпуклой оптимизации: конечномерный взгляд. ЦРК Пресс. п. 243. ИСБН 9781439868225.
19. Нойштадт, Люсьен В. (08 марта 2015 г.). Оптимизация: теория необходимых условий. Издательство Принстонского университета. п. 6. ISBN 9781400870530.
20. Эдвардс, RE (25 октября 2012 г.). Функциональный анализ: теория и приложения. Курьерская корпорация. п. 135. ИСБН 9780486145105.
21. Шефер и Вольф 1999, стр. 205–209.
22. Хаджисаввас, Николас; Мартинес-Легас, Хуан Э.; Пено, Жан-Поль (10 апреля 2001 г.). Обобщенная выпуклость и обобщенная монотонность: материалы 6-го Международного симпозиума по обобщенной выпуклости/монотонности, Самос, сентябрь 1999 г. Springer Science & Business Media. п. 238. ИСБН 9783540418061.
23. Баушке, Хайнц Х.; Комбеттс, Патрик Л. (19 апреля 2011 г.). Выпуклый анализ и теория монотонных операторов в гильбертовых пространствах. Springer Science & Business Media. п. 88. ИСБН 9781441994677.
24. Кэмерон, Нил (5 сентября 1985 г.). Введение в линейное и выпуклое программирование. Архив Кубка. п. 32. ISBN 9780521312073.
25. Паник, MJ (01 декабря 2013 г.). Линейное программирование: математика, теория и алгоритмы. Springer Science & Business Media. п. 40. ИСБН 9781461334347.
26. Датторро, Джон (1 января 2005 г.). Выпуклая оптимизация и евклидова дистанционная геометрия. Издательство Meboo США. п. 96. ИСБН 9780976401308.
27. Никола, ПьерКарло (14 марта 2013 г.). Основная математическая экономика в 20 веке. Springer Science & Business Media. п. 125. ИСБН 9783662042380.
28. Фудзивара, Хиденори; Людвиг, Жан (05 декабря 2014 г.). Гармонический анализ экспоненциальных разрешимых групп Ли. Спрингер. п. 246. ИСБН 9784431552888.
29. Губеладзе, Иосиф; Михалек, Матеуш (1 января 2018 г.). «Порядок рациональных конусов». Тихоокеанский математический журнал . 292 (1): 103–115. arXiv : 1606.02083 . дои : 10.2140/pjm.2018.292.103. S2CID  119639952.
30. Хантер, Джон К.; Нахтергаэле, Бруно (1 января 2001 г.). Прикладной анализ. Всемирная научная. п. 116. ИСБН 9789810241919.
31. Карозерс, Нидерланды (1 января 2005 г.). Краткий курс теории банахового пространства. Издательство Кембриджского университета. ISBN 9780521603720.
32. Наричи и Бекенштейн 2011, стр. 149–153.

Рекомендации

• Бурбаки, Николя (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. ОСЛК  840278135.
• Тревес, Франсуа (2006) [1967]. Топологические векторные пространства, распределения и ядра . Минеола, Нью-Йорк: Dover Publications. ISBN 978-0-486-45352-1. ОКЛК  853623322.
• Залинеску, К. (2002). Выпуклый анализ в общих векторных пространствах. Ривер Эдж, Нью-Джерси: World Scientific. ISBN 981-238-067-1. МР  1921556.