Выпуклый конус - NiNa.Az

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

Выпуклый конус (светло-синий). Внутри него светло-красный замкнутый выпуклый конус, содержащий все точки ${\displaystyle \alpha x+\beta y}$ с ${\displaystyle \alpha ,\beta >0}$ для выделенных точек ${\displaystyle x}$ и ${\displaystyle y}$. Кривые в правом верхнем углу символизируют бесконечность областей.

Определение

Подмножество ${\displaystyle C}$ векторного пространства ${\displaystyle V}$ является выпуклым конусом, если ${\displaystyle \alpha x+\beta y}$ принадлежит ${\displaystyle C}$ для любых положительных скаляров ${\displaystyle \alpha ,\beta }$ и любых ${\displaystyle x,y}$ из ${\displaystyle C}$.

Определение можно записать более сжато: ${\displaystyle \alpha C+\beta C=C}$ для любых положительных чисел ${\displaystyle \alpha ,\beta }$.

Понятие имеет смысл для любых векторных пространств, в которых существует понятие «положительный» скаляр, такие как пространство над рациональными, алгебраическими или (чаще всего) вещественными числами.

Пустое множество, пространство ${\displaystyle V}$ и любое линейное подпространство пространства ${\displaystyle V}$ (включая тривиальное подпространство {0}), являются выпуклыми конусами по этому определению. Другими примерами служат множество всех произведений на положительное число произвольного вектора ${\displaystyle v}$ из ${\displaystyle V}$, или положительный ортант пространства ${\displaystyle \mathbb {R} ^{n}}$ (множество всех векторов, имеющих положительные координаты).

Более общий пример — множество всех векторов ${\displaystyle \lambda x}$, таких, что ${\displaystyle \lambda }$ положительный скаляр, а ${\displaystyle x}$ — элемент некоторого выпуклого подмножества ${\displaystyle X}$ пространства ${\displaystyle V}$. В частности, если ${\displaystyle V}$ — нормированное векторное пространство, а ${\displaystyle X}$ — открытый (соотв. замкнутый) шар в ${\displaystyle V}$, который не содержит 0, эта конструкция даёт открытый (соотв. замкнутый) выпуклый круговой конус.

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

Выпуклые конуса и линейные конуса

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

Альтернативные определения

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

Следует также отметить, что фразу «положительные скаляры ${\displaystyle \alpha ,\beta }$» в определении выпуклого конуса можно заменить на «неотрицательные скаляры ${\displaystyle \alpha ,\beta }$, не равные нулю одновременно».

Свойства выпуклого конуса

• Пересечение любого числа выпуклых конусов снова является выпуклым конусом. Тем самым выпуклые конусы образуют замкнутое семейство (по операции пересечения).
• Коническая оболочка ${\displaystyle \operatorname {pos} (X)}$ — это наименьший выпуклый конус, содержащий данное множество.

Тупые и острые конусы

Согласно вышеприведённым определениям, если ${\displaystyle C}$ является выпуклым конусом, то ${\displaystyle C\cup \{0\}}$ является выпуклым конусом тоже. Говорят, что выпуклый конус острый или тупой в зависимости от того, принадлежит ли ему нулевой вектор 0 или нет. Иногда употребляют термины заострённый и, соответственно, затупленный .

Тупые конусы можно исключить из определения выпуклого конуса, заменив слова «неотрицательные» на «положительные» в условиях, налагаемых на ${\displaystyle \alpha ,\beta }$. Термин «острый» часто используется в другом смысле — для замкнутых конусов, не содержащих полных прямых (то есть нетривиального подпространства окружающего пространства), то есть то, что ниже называется «выступающим» конусом.

Выступающие (острые) конусы

Говорят, что выпуклый конус является плоским, если он содержит некоторый ненулевой вектор ${\displaystyle x}$ и его противоположный ${\displaystyle -x}$, и выступающим в противном случае. Выступающие конуса часто называют также острыми.

Тупой выпуклый конус всегда является выступающим, но обратное не всегда верно. Выпуклый конус ${\displaystyle C}$ является выступающим в том и только в том случае, когда ${\displaystyle C\cap -C\subseteq \{0\}}$. То есть тогда и только тогда, когда ${\displaystyle C}$ не содержит нетривиального линейного подпространства ${\displaystyle V}$.

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

В 1935 году Г.Вейль доказал равносильность следующих двух определений полиэдрального конуса:

• Полиэдральным конусом называется множество ${\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 v_{1},v_{2},\ldots ,v_{i}}$. Эти векторы называют порождающими конуса.
• Полиэдральным конусом называется пересечение конечного набора (замкнутых) полупространств, опорная гиперплоскость которых проходит через начало координат. Эквивалентно, можно говорить о множестве решений конечного набора однородных линейных неравенств.

Рациональные полиэдральные конусы

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

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

Гиперплоскость (линейная) пространства ${\displaystyle V}$ является максимальным возможным собственным линейным подпространством пространства ${\displaystyle V}$. Открытое (соотв. замкнутое) полупространство пространства ${\displaystyle V}$ — это подмножество ${\displaystyle H}$ пространства ${\displaystyle V}$, определённое условием ${\displaystyle L(x)>0}$ (соотв. ${\displaystyle L(x)\geqslant 0}$), где ${\displaystyle L}$ — любая линейная функция из ${\displaystyle V}$ в его поле скаляров. Гиперплоскость, определённая уравнением ${\displaystyle L(v)=0}$, является ограничивающей гиперплоскостью для ${\displaystyle H}$.

Полупространства (открытые или замкнутые) являются выпуклыми конусами. Однако любой выпуклый конус ${\displaystyle C}$, не являющийся всем пространством ${\displaystyle V}$, должен содержаться в некотором замкнутом полупространстве ${\displaystyle H}$ пространства ${\displaystyle V}$. Фактически топологически замкнутый выпуклый конус является пересечением всех замкнутых полупространств, содержащих его. Аналогичное утверждение верно для топологически открытого выпуклого конуса.

Совершенное полупространство пространства ${\displaystyle V}$ определяется рекурсивно следующим образом: если ${\displaystyle V}$ имеет размерность ноль, то это множество ${\displaystyle \{0\}}$, в противном случае это открытое полупространство ${\displaystyle H}$ пространства ${\displaystyle V}$ вместе с совершенным полупространством ограничивающей гиперплоскости для ${\displaystyle H}$. Иными словами, это аналог понятия флага для полупространств.

Любое совершенное полупространство является выступающим, и, более того, любой выступающий конус содержится в совершенном полупространстве. Другими словами, совершенные полупространства являются максимальными выступающими конусами (по включению). Можно показать, что любой острый выступающий конус (независимо от того, замкнут ли он топологически или открыт) является пересечением всех совершенных полупространств, включающих его.

Сечение и проекция выпуклых множеств

Плоское сечение

Аффинная гиперплоскость пространства ${\displaystyle V}$ — это любое подмножество пространства ${\displaystyle V}$ вида ${\displaystyle v+H}$, где ${\displaystyle v}$ — вектор в ${\displaystyle V}$, а ${\displaystyle H}$ — (линейная) гиперплоскость.

Следующее утверждение следует из свойства включения в полупространства. Пусть ${\displaystyle Q}$ — открытое полупространство в ${\displaystyle V}$ и ${\displaystyle A=H+v}$, где ${\displaystyle H}$ — граничная гиперплоскость ${\displaystyle Q}$, а ${\displaystyle v}$ — любой вектор в ${\displaystyle Q}$. Пусть ${\displaystyle C}$ — линейный конус, содержащийся в ${\displaystyle Q}$. Тогда ${\displaystyle C}$ является выпуклым конусом в том и только в том случае, когда множество ${\displaystyle C'=C\cap A}$ является выпуклым подмножеством гиперплоскости ${\displaystyle A}$ (то есть множеством, замкнутым относительно выпуклых комбинаций).

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

Сферическое сечение

Если дана норма | • | в пространстве ${\displaystyle V}$, мы определяем единичную сферу в ${\displaystyle V}$ как множество

${\displaystyle S=\{x\in V\;:\;|x|=1\}.}$

Если значения | • | являются скалярами в ${\displaystyle V}$, то линейный конус ${\displaystyle C}$ в ${\displaystyle V}$ — это выпуклый конус в том и только в том случае, когда его сферическое сечение ${\displaystyle C\cap S}$ (множество его векторов с единичной нормой) является выпуклым подмножеством ${\displaystyle S}$ в следующем смысле: для любых двух векторов ${\displaystyle u,v\in C}$ с ${\displaystyle u\neq -v}$ все вектора на кратчайшем пути из ${\displaystyle u}$ в ${\displaystyle v}$ на ${\displaystyle S}$ лежат в ${\displaystyle C}$.

Двойственный конус

Основная статья: Двойственный конус

Пусть ${\displaystyle C\subset V}$ — выпуклый конус в вещественном векторном пространстве ${\displaystyle V}$, обладающем скалярным произведением. Двойственный конус к ${\displaystyle C}$ — это множество

${\displaystyle \{v\in V\;:\;\forall w\in C,\langle w,v\rangle \geqslant 0\}.}$

Он тоже является выпуклым конусом. Если ${\displaystyle C}$ совпадает со своим двойственным, ${\displaystyle C}$ называется самодвойственным.

Другое частое определение двойственного конуса для ${\displaystyle C\subset V}$ — это конус ${\displaystyle C^{\ast }}$ в сопряжённом пространстве ${\displaystyle V^{\ast }}$:

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

Другими словами, если ${\displaystyle V^{\ast }}$ — сопряжённое пространство пространства ${\displaystyle V}$, то двойственный конус — это множество линейных функций, неотрицательных на конусе ${\displaystyle C}$. Если мы примем, что ${\displaystyle V^{\ast }}$ — непрерывное сопряжённое пространство, то это множество непрерывных линейных функций, неотрицательных на ${\displaystyle C}$. Такое определение не требует наличия скалярного произведения в пространстве ${\displaystyle V}$.

В конечномерных пространствах оба определения двойственного конуса, по существу, эквивалентны, поскольку любому скалярному произведению сопоставляется линейный изоморфизм (невырожденное линейное отображение) из ${\displaystyle V^{\ast }}$ в ${\displaystyle V}$, и этот изоморфизм переводит двойственный конус (в ${\displaystyle V^{\ast }}$) из второго определения в двойственный конус из первого определения.

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

Острый выступающий выпуклый конус ${\displaystyle C}$ порождает частичный порядок «${\displaystyle \leqslant }$» на ${\displaystyle V}$, определяемый так, что ${\displaystyle x\leqslant y}$ тогда и только тогда, когда ${\displaystyle y-x\in C}$. (Если конус плоский, то же самое определение даёт просто предпорядок.) Суммы и умножение на положительный скаляр верного неравенства по отношению к этому порядку снова дают верные неравенства. Векторное пространство с таким порядком называется ^[англ.]. Конус

${\displaystyle P=\left\{x:x\in V,x\geqslant 0\right\}.}$

называется положительным конусом.

В качестве примеров можно привести ^[англ.] на вещественных векторах (${\displaystyle \mathbb {R} ^{n}}$) и порядок Лёвнера

Собственный выпуклый конус

Термин собственный (выпуклый) конус определяется различным образом в зависимости от контекста. Он часто означает выступающий выпуклый конус, не содержащий какую-либо гиперплоскость пространства ${\displaystyle V}$, возможно, с другими накладываемыми ограничениями, как, например, топологическую замкнутость (а вследствие этого, конус будет острым), или топологическую открытость (конус будет тупым). Некоторые авторы используют термин «клин» для понятия, которое в этой статье обозначает выпуклый конус, и под термином «конус» понимается то, что в статье называется выступающим острым конусом, или то, что только что было названо собственным выпуклым конусом.

Примеры выпуклых конусов

• Пусть задано замкнутое выпуклое подмножество ${\displaystyle K}$ гильбертова пространства ${\displaystyle V}$, нормальный конус для множества ${\displaystyle K}$ из точки ${\displaystyle x}$ в ${\displaystyle K}$ задаётся формулой.

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

• Пусть задано замкнутое выпуклое подмножество ${\displaystyle K}$ пространства ${\displaystyle V}$, ^[англ.] к множеству ${\displaystyle K}$ из точки ${\displaystyle x}$ задаётся формулой

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

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

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

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

Нормальные и касательные конусы замкнуты и выпуклы. Они являются важными концепциями в области выпуклого программирования, ^[англ.] .

См. также

• Конус (топология)
• Лемма Фаркаша

Связанные комбинации

• Аффинная комбинация
• Выпуклая комбинация
• Линейная комбинация

Примечания

1. Рокафеллар, 1973, с. 30.
2. Рокафеллар, 1973, с. 32.
3. Красносельский, Лифшиц, Соболев, 1985, с. 9.
4. Бурбаки, 1959, с. 30.
5. Зоркальцев, Киселева, 2007.
6. Эдвардс, 1969, с. 194.
7. Stolfi, 1991, с. 139.
8. Панина, 2009.
9. Boyd, Vandenberghe, 2004.
10. Кутателадзе, 2009, с. 1127.
11. Порядковое произведение — это порождённый порядок на прямом произведении частично упорядоченных множеств. Подробнее смотрите в книге Стенли, 1990
12. Определение порядка Лёвнера можно найти в книге Маршалл, Олкин, 1983
13. Шефер, 1971, с. 258.
14. Панагинотопулос, 1989, с. 171.
15. Панагинотопулос, 1989, с. 62.
16. Рокафеллар, 1973, с. 138.
17. Лейхтвейс, 1985, с. 54.

Ссылки

• Nicolas Bourbaki. Topological vector spaces. — Berlin, New York: Springer-Verlag, 1987. — (Elements of mathematics). — ISBN 978-3-540-13627-9.
• Stephen Boyd, Lieven Vandenberghe. Convex Optimization. — Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore: Cambridge University Press, 2004. — С. 51. — ISBN 78-0-521-83378-3.

• Перевод на русский: Н. Бурбаки. Топологические векторные пространства. — Москва: Издательство иностранной литературы, 1959. — (Элементы математики).

• R. T. Rockafellar. Convex analysis. — Princeton, NJ: Princeton University Press, 1970.

• Перевод на русский: Р. Рокафеллар. Выпуклый анализ. — Москва: «Мир», 1973.

• C. Zălinescu. Convex analysis in general vector spaces. — River Edge, NJ,: World Scientific Publishing  Co., Inc, 2002. — С. xx+367. — ISBN 981-238-067-1.
• В. И. Зоркальцев, М. А. Киселева. Системы линейных неравенств (учебное пособие). — Иркутск: ИГУ, 2007. — С. 21 Глава 1.5 Конусы.
• М.А. Красносельский, Е.А. Лифшиц, А.В. Соболев. ПОЗИТИВНЫЕ ЛИНЕЙНЫЕ СИСТЕМЫ – Метод положительных операторов. — «Наука», Главная редакция физико-математической литературы, 1985. — (Теория и методы системного анализа).
• Stolfi. Oriented Projective Geometry: A Framework for Geometric Computations. — San Diego, London: Academic Press, Inc., 1991. — ISBN 0-12-672025-8.
• Moreau J. J. Numerical aspects of the sweeping process. Comput. Methods Appl. Mech. Engrg. 177 (1999) 329—349
• А. Маршалл, И. Олкин. Неравенства: теория мажоризации и её приложения. — М.: «Мир», 1983.
• Р. Стенли. Перечислительная комбинаторика. — М.: «Мир», 1990. — ISBN 5-030001348-2.
• П. Панагинотопулос. Неравенства в механике и их приложения: Выпуклые и невыпуклые функции энергии. — М.: «Мир», 1989. — ISBN 5-03-000498-X.
• К. Лейхтвейс. Выпуклые множества. — Москва: «Наука» Главная редакция физико-математической литературы, 1985. — ISBN 5-03-000498-X.
• Панина Г.Ю. Торические многообразия. Введение в алгебраическую геометрию. — Дубна, 2009.
• Р. Эдвардс. Функциональный анализ: теория и приложения. — М.: «Мир», 1969.
• Х. Шефер. Топологические векторные пространства. — М.: «Мир», 1971.
• С. С. Кутателадзе. Многоцелевые задачи выпуклой геометрии // Сибирский математический журнал. — «Мир», 2009. — Т. 50, вып. 5.