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

В линейной алгебре конус ( иногда называемый линейным конусом, чтобы отличить его от конусов других типов) — это подмножество векторного пространства , замкнутое относительно положительного скалярного умножения; то есть C является конусом, если подразумевает для каждого положительного скаляра s . Конус не обязательно должен быть выпуклым или даже выглядеть как конус в евклидовом пространстве .
Когда скаляры являются действительными числами или принадлежат упорядоченному полю обычно называют , конусом подмножество векторного пространства, замкнутое при умножении на положительный скаляр . В этом контексте выпуклый конус — это конус, замкнутый относительно сложения, или, что то же самое, подмножество векторного пространства, замкнутое относительно линейных комбинаций с положительными коэффициентами. Отсюда следует, что выпуклые конусы являются выпуклыми множествами . [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 является выпуклым конусом тогда и только тогда, когда αC = C и C + C = C для любого положительного скаляра α .
Примеры [ править ]



- Для векторного пространства V пространство V и любое линейное подпространство V пустое множество , являются выпуклыми конусами.
- Коническая оболочка конечного или бесконечного набора векторов в представляет собой выпуклый конус.
- Касательные конусы выпуклого множества являются выпуклыми конусами.
- Набор является конусом, но не выпуклым конусом.
- Нормальный конус представляет собой выпуклый конус.
- Пересечение двух выпуклых конусов в одном и том же векторном пространстве снова является выпуклым конусом, но их объединение может не быть единым.
- Класс выпуклых конусов замкнут также относительно произвольных линейных отображений . В частности, если C — выпуклый конус, то и его противоположность — выпуклый конус. и является крупнейшим линейным подпространством, содержащимся в C .
- Множество положительных полуопределенных матриц .
- Множество неотрицательных непрерывных функций представляет собой выпуклый конус.
Особые примеры [ править ]
Аффинные выпуклые конусы [ править ]
Аффинный выпуклый конус — это множество, полученное в результате применения аффинного преобразования к выпуклому конусу. [7] является перемещение выпуклого конуса точкой p : p + C. Типичным примером Технически такие преобразования могут давать неконусы. Например, если p = 0 , p + C не является линейным конусом. Однако его по-прежнему называют аффинным выпуклым конусом.
Полупространства [ править ]
(Линейная) гиперплоскость — это множество в виде где f — линейный функционал в векторном пространстве V. Замкнутое полупространство — это множество в виде или и аналогичным образом открытое полупространство использует строгое неравенство. [8] [9]
Полупространства (открытые или закрытые) представляют собой аффинные выпуклые конусы. Более того (в конечных измерениях) любой выпуклый конус C, не являющийся всем пространством V, должен содержаться в некотором замкнутом полупространстве H пространства V ; это частный случай леммы Фаркаса .
Многогранные и конечно порожденные конусы
Многогранные конусы — это особые виды конусов, которые можно определить несколькими способами: [10] : 256–257
- Конус C называется многогранником, если он является конической оболочкой конечного числа векторов (это свойство также называется конечно-порожденным ). [11] [12] То есть существует набор векторов так что .
- Конус называется многогранником, если он является пересечением конечного числа полупространств, на границе которых имеется 0 (это было доказано Вейлем в 1935 г.).
- Конус C называется многогранником, если существует некоторая матрица такой, что .
- Конус называется многогранником, если он является множеством решений системы однородных линейных неравенств. Алгебраически каждое неравенство определяется строкой матрицы A . Геометрически каждое неравенство определяет полупространство, проходящее через начало координат.
Каждый конечно порожденный конус является многогранным конусом, а каждый многогранный конус является конечно порожденным конусом. [11] Каждый многогранный конус имеет уникальное представление в виде конической оболочки своих экстремальных образующих и уникальное представление пересечений полупространств, при этом каждая линейная форма, связанная с полупространствами, также определяет опорную гиперплоскость фасета. [13]
Многогранные конусы играют центральную роль в теории представлений многогранников . Например, теорема о разложении многогранников утверждает, что каждый многогранник можно записать как сумму Минковского и выпуклого многогранника многогранного конуса. [14] [15] Многогранные конусы также играют важную роль в доказательстве соответствующей теоремы о конечном базисе для многогранников, которая показывает, что каждый многогранник является многогранником, а каждый ограниченный многогранник является многогранником. [14] [16] [17]
Два представления многогранного конуса — неравенствами и векторами — могут иметь весьма разные размеры. Например, рассмотрим конус всех неотрицательных n на матриц размером n с равными суммами строк и столбцов. Представление неравенства требует n 2 неравенств и 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]
Некоторые авторы требуют, чтобы выступающие конусы были заостренными. [22] Термин «заостренный» также часто используется для обозначения замкнутого конуса, который не содержит полной линии (т. е. нет нетривиального подпространства объемлющего векторного пространства V или того, что называется выступающим конусом). [23] [24] [25] Термин « собственный ( выпуклый ) конус» определяется по-разному, в зависимости от контекста и автора. Это часто означает конус, который удовлетворяет другим свойствам, например, является выпуклым, закрытым, заостренным, выступающим и полномерным. [26] [27] [28] Из-за различий в определениях для определения этих терминов следует обращаться к контексту или источнику.
Рациональные конусы [ править ]
Тип конуса, представляющий особый интерес для чистых математиков, — это частично упорядоченный набор рациональных конусов. «Рациональные конусы являются важными объектами в торической алгебраической геометрии, комбинаторной коммутативной алгебре, геометрической комбинаторике, целочисленном программировании». [29] Этот объект возникает, когда мы изучаем конусы в вместе с решеткой . Конус называется рациональным (здесь мы предполагаем «заостренным», как определено выше), если все его образующие имеют целочисленные координаты, т. е. если является рациональным конусом, то .
Двойной конус [ править ]
Пусть C ⊂ V — множество (не обязательно выпуклое) в вещественном векторном пространстве V, снабженное скалярным произведением . (Непрерывный или топологический) двойственный конус к C — это множество
который всегда представляет собой выпуклый конус. Здесь, является парой двойственности между C и V , т.е. .
В более общем смысле, (алгебраический) двойственный конус к C ⊂ V в линейном пространстве V является подмножеством двойственного пространства V*, определяемого следующим образом:
Другими словами, если V* — алгебраическое двойственное к V пространство , C* — множество линейных функционалов, неотрицательных на прямом C. конусе Если мы возьмем V* как непрерывное дуальное пространство , то это множество непрерывных линейных функционалов, неотрицательных на C . [30] Это понятие не требует указания внутреннего продукта на V .
В конечных измерениях два понятия двойственного конуса по существу одинаковы, поскольку каждый конечномерный линейный функционал непрерывен, [31] и каждый непрерывный линейный функционал в пространстве внутреннего произведения индуцирует линейный изоморфизм (несингулярное линейное отображение) из V* в V , и этот изоморфизм переводит двойственный конус, заданный вторым определением, в V* , в конус, заданный первым определение; см. теорему о представлении Рисса . [30]
Если C равен своему двойственному конусу, то C называется самодвойственным . Можно сказать, что конус самодвойственный безотносительно к какому-либо данному внутреннему продукту, если существует внутренний продукт, по отношению к которому он равен своему двойственному по первому определению.
Конструкции [ править ]
- Для замкнутого выпуклого подмножества K гильбертова пространства V внешний нормальный конус к множеству K в точке x в K определяется выражением
- Для замкнутого выпуклого подмножества K в V касательный конус (или контингентный конус ) к множеству K в точке x задается формулой
- Учитывая замкнутое выпуклое подмножество K гильбертова пространства V , касательный конус к множеству K в точке x в K можно определить как полярный конус к внешнему нормальному конусу. :
И нормальный, и касательный конусы обладают свойством замкнутости и выпуклости.
Они являются важными концепциями в области выпуклой оптимизации , вариационных неравенств и проектируемых динамических систем .
Свойства [ править ]
Если C — непустой выпуклый конус в X , то линейная оболочка C равна C — C , а наибольшее векторное подпространство X , содержащееся в C, равно C ∩ (− C ). [32]
Частичный порядок, определяемый выпуклым конусом [ править ]
Заостренный и выпуклый конус C индуцирует частичный порядок «≥» на V , определенный так, что тогда и только тогда, когда (Если конус плоский, то же определение дает просто предварительный порядок .) Суммы и положительные скалярные кратные действительных неравенств относительно этого порядка остаются действительными неравенствами. Векторное пространство с таким порядком называется упорядоченным векторным пространством . Примеры включают порядок произведения векторов с действительным знаком, и порядок Левнера на положительных полуопределенных матрицах. Такой порядок обычно встречается в полуопределенном программировании .
См. также [ править ]
Примечания [ править ]
- ^ Бойд, Стивен; Ванденберге, Ливен (8 марта 2004 г.). Выпуклая оптимизация . Издательство Кембриджского университета. ISBN 978-0-521-83378-3 .
- ^ Jump up to: Перейти обратно: а б Бернштейн, Деннис С. (26 июля 2009 г.). Матричная математика: теория, факты и формулы (второе изд.). Издательство Принстонского университета. п. 97. ИСБН 978-0691140391 .
- ^ К. Залинеску (1 января 2002 г.). Выпуклый анализ в общих векторных пространствах . Всемирная научная. п. 1. ISBN 978-981-238-067-8 .
- ^ Неф, Уолтер (1 января 1988 г.). Линейная алгебра . Курьерская корпорация. п. 35. ISBN 9780486657721 .
- ^ Ито, Кийоси (1 января 1993 г.). Энциклопедический словарь математики . МТИ Пресс. ISBN 9780262590204 .
- ^ Рокафеллар, Ральф Тайрелл (29 апреля 2015 г.). Выпуклый анализ . Издательство Принстонского университета. п. 13. ISBN 9781400873173 .
- ^ Хириар-Уррути, Жан-Батист; Лемарешаль, Клод (6 декабря 2012 г.). Основы выпуклого анализа . Springer Science & Business Media. ISBN 9783642564680 .
- ^ Алипрантис, Хараламбос Д.; Бордер, Ким К. (02 мая 2007 г.). Бесконечномерный анализ: Путеводитель для автостопщика . Springer Science & Business Media. п. 197. ИСБН 9783540326960 .
- ^ Рокафеллар, Ральф Тайрелл (29 апреля 2015 г.). Выпуклый анализ . Издательство Принстонского университета. п. 10. ISBN 9781400873173 .
- ^ Jump up to: Перейти обратно: а б Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1 , МР 0859549
- ^ Jump up to: Перейти обратно: а б Лоэра, Хесус А. Де; Хеммеке, Раймонд; Кеппе, Матиас (01 января 2012 г.). Алгебраические и геометрические идеи в теории дискретной оптимизации . СИАМ. ISBN 9781611972443 .
- ^ Шрийвер, Александр (7 июля 1998 г.). Теория линейного и целочисленного программирования . Джон Уайли и сыновья. ISBN 9780471982326 .
- ^ Брунс, Винфрид; Губеладзе, Иосиф (2009). Многогранники, кольца и K-теория (1-е изд.). Монографии Спрингера по математике. п. 3 . ISBN 9780387763552 .
- ^ Jump up to: Перейти обратно: а б Шрийвер, Александр (7 июля 1998 г.). Теория линейного и целочисленного программирования . Джон Уайли и сыновья. стр. 88–89. ISBN 9780471982326 .
- ^ Конфорти, Микеле; Корнюжольс, Жерар; Замбелли, Джакомо (15 ноября 2014 г.). Целочисленное программирование . Спрингер. п. 111. ИСБН 9783319110080 .
- ^ Корте, Бернхард; Виген, Йенс (11 ноября 2013 г.). Комбинаторная оптимизация: теория и алгоритмы . Springer Science & Business Media. п. 61. ИСБН 9783662217115 .
- ^ Вильярреал, Рафаэль (26 марта 2015 г.). Мономиальные алгебры, второе издание . ЦРК Пресс. п. 9. ISBN 9781482234701 .
- ^ Дхара, Анулекха; Датта, Джойдип (17 октября 2011 г.). Условия оптимальности в выпуклой оптимизации: конечномерный взгляд . ЦРК Пресс. п. 243. ИСБН 9781439868225 .
- ^ Нойштадт, Люсьен В. (08 марта 2015 г.). Оптимизация: теория необходимых условий . Издательство Принстонского университета. п. 6. ISBN 9781400870530 .
- ^ Эдвардс, Р.Э. (25 октября 2012 г.). Функциональный анализ: теория и приложения . Курьерская корпорация. п. 135. ИСБН 9780486145105 .
- ^ Шефер и Вольф 1999 , стр. 205–209.
- ^ Хаджисаввас, Николас; Мартинес-Легас, Хуан Э.; Пено, Жан-Поль (10 апреля 2001 г.). Обобщенная выпуклость и обобщенная монотонность: материалы 6-го Международного симпозиума по обобщенной выпуклости/монотонности, Самос, сентябрь 1999 г. Springer Science & Business Media. п. 238. ИСБН 9783540418061 .
- ^ Баушке, Хайнц Х.; Комбеттс, Патрик Л. (19 апреля 2011 г.). Выпуклый анализ и теория монотонных операторов в гильбертовых пространствах . Springer Science & Business Media. п. 88. ИСБН 9781441994677 .
- ^ Кэмерон, Нил (5 сентября 1985 г.). Введение в линейное и выпуклое программирование . Архив Кубка. п. 32. ISBN 9780521312073 .
- ^ Паник, МЮ (1 декабря 2013 г.). Линейное программирование: математика, теория и алгоритмы . Springer Science & Business Media. п. 40. ИСБН 9781461334347 .
- ^ Датторро, Джон (1 января 2005 г.). Выпуклая оптимизация и евклидова дистанционная геометрия . Издательство Meboo США. п. 96. ИСБН 9780976401308 .
- ^ Никола, ПьерКарло (14 марта 2013 г.). Основное направление математической экономики в 20 веке . Springer Science & Business Media. п. 125. ИСБН 9783662042380 .
- ^ Фудзивара, Хиденори; Людвиг, Жан (05 декабря 2014 г.). Гармонический анализ на экспоненциальных разрешимых группах Ли . Спрингер. п. 246. ИСБН 9784431552888 .
- ^ Губеладзе, Иосиф; Михалек, Матеуш (1 января 2018 г.). «Порядок рациональных конусов». Тихоокеанский математический журнал . 292 (1): 103–115. arXiv : 1606.02083 . дои : 10.2140/pjm.2018.292.103 . S2CID 119639952 .
- ^ Jump up to: Перейти обратно: а б Хантер, Джон К.; Нахтергаэле, Бруно (1 января 2001 г.). Прикладной анализ . Всемирная научная. п. 116. ИСБН 9789810241919 .
- ^ Карозерс, Нидерланды (01 января 2005 г.). Краткий курс теории банахового пространства . Издательство Кембриджского университета. ISBN 9780521603720 .
- ^ Наричи и Бекенштейн, 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 . OCLC 840278135 .
- Тревес, Франсуа (2006) [1967]. Топологические векторные пространства, распределения и ядра . Минеола, Нью-Йорк: Dover Publications. ISBN 978-0-486-45352-1 . OCLC 853623322 .
- Залинеску, К. (2002). Выпуклый анализ в общих векторных пространствах . Ривер Эдж, Нью-Джерси: World Scientific. ISBN 981-238-067-1 . МР 1921556 .