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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если 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 ). ^[34]

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

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

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

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

Примечания

1. Бойд, Стивен; Ванденберг, Ливен (2004-03-08). Выпуклая оптимизация. Cambridge University Press. ISBN 978-0-521-83378-3.
2. Бернстайн, Деннис С. (2009-07-26). Матричная математика: теория, факты и формулы (второе издание). Princeton University Press. стр. 97. ISBN 978-0691140391.
3. C. Zalinescu (1 января 2002 г.). Выпуклый анализ в общих векторных пространствах. World Scientific. стр. 1. ISBN 978-981-238-067-8.
4. Неф, Уолтер (1988-01-01). Линейная алгебра. Courier Corporation. стр. 35. ISBN 9780486657721.
5. Ито, Киёси (1 января 1993 г.). Энциклопедический словарь математики. МТИ Пресс. ISBN 9780262590204.
6. Рокафеллар, Ральф Тайрелл (2015-04-29). Выпуклый анализ. Princeton University Press. стр. 13. ISBN 9781400873173.
7. Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (2012-12-06). Основы выпуклого анализа. Springer Science & Business Media. ISBN 9783642564680.
8. Aliprantis, Charalambos D.; Border, Kim C. (2007-05-02). Анализ бесконечных измерений: путеводитель для путешествующих автостопом. Springer Science & Business Media. стр. 197. ISBN 9783540326960.
9. Рокафеллар, Ральф Тайрелл (2015-04-29). Выпуклый анализ. Princeton University Press. стр. 10. ISBN 9781400873173.
10. Ловаш, Ласло ; Пламмер, доктор медицины (1986). Теория соответствия . Анналы дискретной математики. Том. 29. Северная Голландия. ISBN 0-444-87916-1. МР  0859549.
11. Лоэра, Хесус А. Де; Хеммеке, Раймонд; Кеппе, Матиас (01 января 2012 г.). Алгебраические и геометрические идеи в теории дискретной оптимизации. СИАМ. ISBN 9781611972443.
12. Шрайвер, Александр (7 июля 1998 г.). Теория линейного и целочисленного программирования. Джон Уайли и сыновья. ISBN 9780471982326.
13. Вейль, Х. (1935). «Элементарная теория выпуклого полиэдра». Комментарии по математике Helvetici . 7 : 290–306. дои : 10.1007/BF01292722.
14. Mirkil, H. (1957). «Новые характеристики многогранных конусов». Canadian Journal of Mathematics . 9 : 1–4. doi :10.4153/CJM-1957-001-5. MR  0083761.
15. Брунс, Винфрид; Губеладзе, Джозеф (2009). Многогранники, кольца и K-теория (1-е изд.). Springer Monographs in Mathematics. стр. 3. ISBN 9780387763552.
16. Шрийвер, Александр (7 июля 1998 г.). Теория линейного и целочисленного программирования. Джон Уайли и сыновья. стр. 88–89. ISBN 9780471982326.
17. Конфорти, Микеле; Корнюжольс, Жерар; Замбелли, Джакомо (15 ноября 2014 г.). Целочисленное программирование. Спрингер. п. 111. ИСБН 9783319110080.
18. Корте, Бернхард; Виген, Йенс (2013-11-11). Комбинаторная оптимизация: теория и алгоритмы. Springer Science & Business Media. стр. 61. ISBN 9783662217115.
19. Вильярреал, Рафаэль (2015-03-26). Мономиальные алгебры, второе издание. CRC Press. стр. 9. ISBN 9781482234701.
20. Дхара, Анулеха; Дутта, Джойдип (2011-10-17). Условия оптимальности в выпуклой оптимизации: конечномерный вид. CRC Press. стр. 243. ISBN 9781439868225.
21. Нойштадт, Люсьен В. (2015-03-08). Оптимизация: Теория необходимых условий. Princeton University Press. стр. 6. ISBN 9781400870530.
22. Эдвардс, Р. Э. (2012-10-25). Функциональный анализ: теория и приложения. Courier Corporation. стр. 135. ISBN 9780486145105.
23. Шефер и Вольф 1999, стр. 205–209.
24. Хаджисаввас, Николас; Мартинес-Легас, Хуан Э.; Пено, Жан-Поль (2001-04-10). Обобщенная выпуклость и обобщенная монотонность: Труды 6-го Международного симпозиума по обобщенной выпуклости/монотонности, Самос, сентябрь 1999 г. Springer Science & Business Media. стр. 238. ISBN 9783540418061.
25. Bauschke, Heinz H.; Combettes, Patrick L. (2011-04-19). Выпуклый анализ и теория монотонных операторов в гильбертовых пространствах. Springer Science & Business Media. стр. 88. ISBN 9781441994677.
26. Кэмерон, Нил (1985-09-05). Введение в линейное и выпуклое программирование. Архив CUP. стр. 32. ISBN 9780521312073.
27. Паник, М.Дж. (2013-12-01). Линейное программирование: математика, теория и алгоритмы. Springer Science & Business Media. стр. 40. ISBN 9781461334347.
28. Датторро, Джон (2005-01-01). Выпуклая оптимизация и геометрия евклидовых расстояний. Meboo Publishing USA. стр. 96. ISBN 9780976401308.
29. Никола, ПьерКарло (2013-03-14). Основное течение математической экономики в 20 веке. Springer Science & Business Media. стр. 125. ISBN 9783662042380.
30. Фудзивара, Хиденори; Людвиг, Жан (2014-12-05). Гармонический анализ на экспоненциально разрешимых группах Ли. Springer. стр. 246. ISBN 9784431552888.
31. Губеладзе, Иосиф; Михалек, Матеуш (1 января 2018 г.). «Последовательность рациональных конусов». Тихоокеанский математический журнал . 292 (1): 103–115. arXiv : 1606.02083 . дои : 10.2140/pjm.2018.292.103. S2CID  119639952.
32. Хантер, Джон К.; Нахтергале, Бруно (2001-01-01). Прикладной анализ. World Scientific. стр. 116. ISBN 9789810241919.
33. Карозерс, Н. Л. (2005-01-01). Краткий курс теории банахова пространства. Cambridge University Press. ISBN 9780521603720.
34. Наричи и Бекенштейн 2011, стр. 149–153.

Ссылки

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