Konvexní kužel

Konvexní kužel v lineární algebře je podmnožinou vektorového prostoru nad uspořádaným polem , který je uzavřen pod lineárními kombinacemi s kladnými koeficienty.

Definice

Podmnožina vektorového prostoru je konvexní kužel , pokud patří k libovolnému kladnému skaláru a libovolnému z . $C$ $PROTI$ $\alpha x+\beta y$ $C$ $\alpha ,\beta$ $x, y$ $C$

Definici lze napsat stručněji: pro libovolná kladná čísla . $\alpha C+\beta C=C$ $\alpha ,\beta$

Pojem je smysluplný pro jakékoli vektorové prostory, ve kterých existuje pojem „pozitivní“ skalár, jako je prostor nad racionálními , algebraickými nebo (nejčastěji) reálnými čísly.

Prázdná množina, prostor a jakýkoli lineární podprostor prostoru (včetně triviálního podprostoru { 0 }) jsou podle této definice konvexní kužely. Dalšími příklady jsou množina všech součinů kladným číslem libovolného vektoru z , nebo kladný orthant prostoru (množina všech vektorů, které mají kladné souřadnice). $PROTI$ $PROTI$ $proti$ $PROTI$ $\mathbb {R} ^{n}$

Obecnějším příkladem je soubor všech vektorů takový, že a je kladný skalární a je prvkem nějaké konvexní podmnožiny prostoru . Konkrétně, pokud je normovaný vektorový prostor a je otevřená (resp. uzavřená) koule v , která neobsahuje 0, tato konstrukce dává otevřený (resp. uzavřený ) konvexní kruhový kužel . $\lambda x$ $\lambda$ $X$ $X$ $PROTI$ $PROTI$ $X$ $PROTI$

Průsečík dvou konvexních kuželů ve stejném vektorovém prostoru je opět konvexní kužel, ale sjednocení nemusí být. [1] Třída konvexních kuželů je uzavřena pod libovolným lineárním zobrazením . Zvláště, jestliže je konvexní kužel, pak konvexní kužel a jeho opak , a je největším lineárním podprostorem obsaženým v [2] . Takový podprostor se nazývá čepel . [3] $C$ $-C$ $C\cap -C$ $C$

Konvexní kužely a lineární kužely

Jestliže je konvexní kužel, pak pro jakýkoli kladný skalár a jakýkoli vektor z vektoru leží v . Z toho plyne, že konvexní kužel je speciální případ lineárního kužele . $C$ $\alpha$ $X$ $C$ $\alpha x=(\alpha /2)x+(\alpha /2)x$ $C$ $C$

Alternativní definice

Z výše uvedeného vyplývá, že konvexní kužel lze definovat jako lineární kužel, který je uzavřen pod konvexními kombinacemi nebo jednoduše pod sčítáním . Stručně řečeno, množina je konvexní kužel tehdy a pouze tehdy a pro jakýkoli kladný skalár . [čtyři] $C$ $\alpha C=C$ $C+C=C$ $\alpha$

Je třeba také poznamenat, že výraz „pozitivní skaláry “ v definici konvexního kužele lze nahradit výrazem „nezáporné skaláry , které nejsou současně nulové“. $\alpha ,\beta$ $\alpha ,\beta$

Vlastnosti konvexního kužele

Průsečík libovolného počtu konvexních kuželů je opět konvexní kužel. Konvexní kužely tedy tvoří uzavřenou rodinu (operací průniku).
Kónický trup je nejmenší konvexní kužel obsahující danou sadu. $\operatorname {pos} (X)$

Tupé a ostré kužely

Podle výše uvedených definic, pokud je konvexní kužel, pak je to také konvexní kužel. O konvexním kuželu se říká, že je ostrý nebo tupý , v závislosti na tom, zda k němu patří nulový vektor 0 nebo ne [5] . Někdy používají výrazy zahrocené a podle toho i tupé [4] [6] . $C$ ${\displaystyle C\cup \{0\))$

Tupé kužely lze z definice konvexního kužele vyloučit nahrazením slov „nezáporný“ výrazem „pozitivní“ v podmínkách uložených na . Termín " ostrý " se často používá v jiném smyslu - pro uzavřené kužely, které neobsahují úplné linie (tedy netriviální podprostor okolního prostoru), tedy to, co se níže nazývá "vyčnívající" kužel. $\alpha ,\beta$

Vyčnívající (ostré) kužely

O konvexním kuželu se říká, že je plochý , pokud obsahuje nějaký nenulový vektor a jeho opak , a jinak vyčnívající [6] . Vyčnívající čípky se často také nazývají akutní . $X$ $-X$

Tupý konvexní kužel je vždy vyčnívající kužel, ale opak není vždy pravdou. Konvexní kužel vyčnívá právě tehdy, když . Tedy tehdy a jen tehdy , když neobsahuje netriviální lineární podprostor . $C$ ${\displaystyle C\cap -C\subseteq \{0\))$ $C$ $PROTI$

Polyedrické kužely

V roce 1935 G. Weyl dokázal ekvivalenci následujících dvou definic mnohostěnného kužele :

Polyhedrální kužel je soubor lineárních kombinací s nezápornými koeficienty pevné konečné sady vektorů . Tyto vektory se nazývají kuželové generátory . $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))$
Polyedrický kužel je průsečíkem konečné množiny (uzavřených) poloprostorů, jejichž nosná nadrovina prochází počátkem. Ekvivalentně lze hovořit o množině řešení konečné množiny homogenních lineárních nerovnic.

Racionální mnohostěnné kužely

Polyedrický kužel se nazývá racionální , pokud všechny jeho generátory mají celočíselné souřadnice.

Poloviční mezery

Nadrovina (lineární) prostoru je největší možný vlastní lineární podprostor prostoru . Otevřený (resp. uzavřený ) poloprostor prostoru je podmnožinou prostoru definovaného podmínkou (resp. ), kde je libovolná lineární funkce skalárů v jeho poli. Nadrovina definovaná rovnicí je hraniční nadrovinou pro . $PROTI$ $PROTI$ $PROTI$ $H$ $PROTI$ $L(x)>0$ $L(x)\geqslant 0$ $L$ $PROTI$ $L(v)=0$ $H$

Poloprostory (otevřené nebo uzavřené) jsou konvexní kužely. Avšak jakýkoli konvexní kužel , který není celým prostorem, musí být obsažen v nějakém uzavřeném poloprostoru prostoru . Ve skutečnosti je topologicky uzavřený konvexní kužel průsečíkem všech uzavřených poloprostorů, které jej obsahují. Podobné tvrzení platí pro topologicky otevřený konvexní kužel. $C$ $PROTI$ $H$ $PROTI$

Dokonalý poloprostor prostoru je definován rekurzivně takto: pokud má rozměr nula, pak je to množina , jinak je to otevřený poloprostor prostoru spolu s dokonalým poloprostorem ohraničující nadroviny pro [ 7] . Jinými slovy, toto je analogie pojmu příznak pro poloviční mezery. $PROTI$ $PROTI$ $\{0\}$ $H$ $PROTI$ $H$

Každý dokonalý poloprostor vyčnívá a navíc jakýkoli vyčnívající kužel je obsažen v dokonalém poloprostoru. Jinými slovy, dokonalé poloprostory jsou maximální vyčnívající kužely (začleněním). Lze ukázat, že jakýkoli akutní vyčnívající kužel (bez ohledu na to, zda je topologicky uzavřený nebo otevřený) je průsečíkem všech dokonalých poloprostorů, které jej obsahují.

Řez a projekce konvexních množin

Řez rovinou

Afinní nadrovina prostoru je jakákoli podmnožina prostoru tvaru , kde je vektor v a je (lineární) nadrovina. $PROTI$ $PROTI$ $v+H$ $proti$ $PROTI$ $H$

Následující tvrzení vyplývá z vlastnosti inclusion v polovičních mezerách. Dovolit být otevřený poloprostor v a , Kde je hraniční nadrovina a je libovolný vektor v . Dovolit být lineární kužel obsažený v . Pak je konvexní kužel právě tehdy, když je množina konvexní podmnožinou nadroviny (tj. množina, která je uzavřena pod konvexními kombinacemi ). $Q$ $PROTI$ $A=H+v$ $H$ $Q$ $proti$ $Q$ $C$ $Q$ $C$ $C'=C\cap A$ $A$

V důsledku tohoto výsledku mají všechny vlastnosti konvexních množin v afinním prostoru analogii pro konvexní kužely obsažené v pevném otevřeném poloprostoru.

Kulový řez

Pokud je uvedena norma | • | v prostoru definujeme jednotkovou sféru v jako množinu $PROTI$ $PROTI$

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

Pokud hodnoty | • | jsou skaláry v , pak je přímkový kužel v konvexním kuželem právě tehdy, když jeho sférický řez (množina jeho vektorů s jednotkovou normou ) je konvexní podmnožinou v následujícím smyslu: pro libovolné dva vektory se všemi vektory na nejkratší cestě ze v na ležet v . $PROTI$ $C$ $PROTI$ $C\cap S$ $S$ $u,v\in C$ $u\neq -v$ $u$ $proti$ $S$ $C$

Dvojitý kužel

Dovolit být konvexní kužel v reálném vektorovém prostoru se skalárním součinem . Dvojitý kužel k je množina [8] [9] $C\subset V$ $PROTI$ $C$

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

Je to také konvexní kužel. Pokud se shoduje s jeho duálem, nazývá se self-dual . $C$ $C$

Další běžnou definicí duálního kužele je kužel v duálním prostoru : $C\subset V$ $C^{\ast }$ $V^{\ast }$

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

Jinými slovy, jestliže je duální prostor prostoru , pak duální kužel je množina lineárních funkcí, které jsou na kuželu nezáporné . Pokud připustíme, že je to spojitý duální prostor , pak je to množina spojitých lineárních funkcí, které jsou nezáporné na . [10] Taková definice nevyžaduje přítomnost vnitřního produktu v prostoru . $V^{\ast }$ $PROTI$ $C$ $V^{\ast }$ $C$ $PROTI$

V konečnorozměrných prostorech jsou obě definice duálního kužele v podstatě ekvivalentní, protože jakýkoli vnitřní součin je spojen s lineárním izomorfismem (nedegenerovaným lineárním zobrazením) od do , a tento izomorfismus přebírá duální kužel (do ) z druhé definice. k duálnímu kuželu z první definice. $V^{\ast }$ $PROTI$ $V^{\ast }$

Částečné pořadí definované konvexním kuželem

Ostrý vyčnívající konvexní kužel generuje částečnou objednávku " " on , definovanou tak , že tehdy a jen tehdy . (Pokud je kužel plochý, stejná definice dává pouze předřád .) Součty a násobení kladným skalárem pravé nerovnosti vzhledem k tomuto řádu opět dávají správné nerovnosti. Vektorový prostor s takovým uspořádáním se nazývá uspořádaný vektorový prostor . Kužel $C$ $\leqslant$ $PROTI$ $x \leqslant y$ $yx\in C$

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

se nazývá kladný kužel [6] .

Příklady zahrnují ordinální součin [11] na reálných vektorech ( ) a Löwnerův řád [12] $\mathbb {R} ^{n}$

Správný konvexní kužel

Pojem vlastní ( konvexní ) kužel je definován různými způsoby v závislosti na kontextu. Často to znamená vyčnívající konvexní kužel, který neobsahuje žádnou nadrovinu prostoru , možná s dalšími omezeními, jako je topologická uzavřenost (a proto bude kužel ostrý) nebo topologická otevřenost (kužel bude tupý) [13] . Někteří autoři používají termín „klín“ pro to, co je v tomto článku označováno jako konvexní kužel, a termín „kužel“ označuje to, co je v článku označováno jako vyčnívající ostrý kužel nebo to, co bylo právě nazváno řádným kuželem. konvexní kužel. $PROTI$

Příklady konvexních kuželů

Nechť je dána uzavřená konvexní podmnožina Hilbertova prostoru , normální kužel pro množinu z bodu do je dán vzorcem. [2] $K$ $PROTI$ $K$ $X$ $K$

N_{K}(x)=\left\{p\in V\;:\;\forall x^{*}\in K,\langle p,xx^{*}\rangle \geqslant 0\ že jo\}.

Nechť je dána uzavřená konvexní podmnožina prostoru , tečný kužel k množině z bodu je dán vzorcem [14] $K$ $PROTI$ $K$ $X$

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

Nechť je dána uzavřená konvexní podmnožina Hilbertova prostoru , vnější normálový kužel k množině od bodu do je dán vzorcem [15] $K$ $PROTI$ $K$ $X$ $K$

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

Vzhledem k uzavřené konvexní podmnožině Hilbertova prostoru lze tečný kužel k množině v bodě od definovat jako polární kužel k vnějšímu normálnímu kuželu : [16] [17] $K$ $PROTI$ $K$ $X$ $K$ $N_{K} (x)$

Normální a tečné kužely jsou uzavřené a konvexní. Jsou to důležité pojmy v oblasti konvexního programování , variačních nerovností .

Viz také

Související kombinace

Poznámky

↑ Rockafellar, 1973 , str. třicet.
↑ 1 2 Rockafellar, 1973 , str. 32.
↑ Krasnoselsky, Lifshits, Sobolev, 1985 , s. 9.
↑ 1 2 Bourbaki, 1959 , str. třicet.
↑ Zorkaltsev, Kiseleva, 2007 .
↑ 1 2 3 Edwards, 1969 , str. 194.
↑ Stolfi, 1991 , str. 139.
↑ Panina, 2009 .
↑ Boyd, Vandenberghe, 2004 .
↑ Kutateladze, 2009 , s. 1127.
↑ Pořadový produkt je vygenerovaná objednávka na přímém součinu částečně uspořádaných sad. Podrobnosti viz Stanley, 1990 .
↑ Definici Löwnerova řádu lze nalézt v Marshall, Olkin, 1983
↑ Schaefer, 1971 , s. 258.
↑ Panaginotopoulos, 1989 , s. 171.
↑ Panaginotopoulos, 1989 , s. 62.
↑ Rockafellar, 1973 , str. 138.
↑ Leuchtweis, 1985 , str. 54.

Odkazy

Nicholas Bourbaki. Topologické vektorové prostory. - Berlín, New York: Springer-Verlag , 1987. - (Základy matematiky). — ISBN 978-3-540-13627-9 .
Stephen Boyd, Lieven Vandenberghe. Konvexní optimalizace. - Cambridge, New York, Melbourne, Madrid, Kapské Město, Singapur: Cambridge University Press, 2004. - S. 51. - ISBN 78-0-521-83378-3.

Překlad do ruštiny: N. Bourbaki. Topologické vektorové prostory. - Moskva: Nakladatelství zahraniční literatury, 1959. - (Základy matematiky).

RT Rockafellar. Konvexní analýza . — Princeton, NJ: Princeton University Press, 1970.

Překlad do ruštiny: R. Rockafellar. Konvexní analýza. - Moskva: Mir, 1973.

C. Zălinescu. Konvexní analýza v obecných vektorových prostorech. - River Edge, NJ: World Scientific Publishing Co., Inc, 2002. - str. xx+367. - ISBN 981-238-067-1 .
V. I. Zorkaltsev, M. A. Kiseleva. Soustavy lineárních nerovnic (učebnice). - Irkutsk: IGU, 2007. - S. 21 Kapitola 1.5 Kužele.
M.A. Krasnoselsky, E.A. Lifshitz, A.V. Sobolev. POZITIVNÍ LINEÁRNÍ SYSTÉMY – Metoda pozitivních operátorů. - "Nauka", Hlavní vydání fyzikální a matematické literatury, 1985. - (Teorie a metody systémové analýzy).
Stolfi. Orientovaná projektivní geometrie: Rámec pro geometrické výpočty. - San Diego, Londýn: Academic Press, Inc., 1991. - ISBN 0-12-672025-8 .
Moreau JJ Numerické aspekty procesu zametání. Počítat. MethodsAppl. Mech. Engrg. 177 (1999) 329-349 https://web.archive.org/web/20150616073514/http://www.continuousphysics.com/ftp/pub/test/files/physics/papers/moreau.99.pdf
A. Marshall, I. Olkin. Nerovnice: majorizační teorie a její aplikace. - M .: "Mir", 1983.
R. Stanley. Enumerativní kombinatorika. - M. : "Mir", 1990. - ISBN 5-030001348 -2.
P. Panaginotopoulos. Nerovnice v mechanice a jejich aplikace: Konvexní a nekonvexní funkce energie. - M. : "Mir", 1989. - ISBN 5-03-000498-X .
K. Leuchtweiss. Konvexní sady. - Moskva: "Nauka" Hlavní vydání fyzikální a matematické literatury, 1985. - ISBN 5-03-000498-X .
Panina G.Yu. Torické odrůdy. Úvod do algebraické geometrie. — Dubna, 2009.
R. Edwards. Funkční analýza: teorie a aplikace. - M .: "Mir", 1969.
H. Schaefer. Topologické vektorové prostory. - M .: "Mir", 1971.
S. S. Kutateladze. Víceúčelové problémy konvexní geometrie // Siberian Mathematical Journal. - "Mir", 2009. - V. 50 , no. 5 .