Konveks kegle

En konveks kegle i lineær algebra er en delmængde af et vektorrum over et ordnet felt , der er lukket under lineære kombinationer med positive koefficienter.

Definition

En delmængde af et vektorrum er en konveks kegle, hvis den hører til for alle positive skalarer og nogen af . $C$ $V$ $\alpha x+\beta y$ $C$ $\alfa ,\beta$ $x,y$ $C$

Definitionen kan skrives mere kortfattet: for alle positive tal . $\alpha C+\beta C=C$ $\alfa ,\beta$

Begrebet er meningsfuldt for ethvert vektorrum, hvor begrebet en "positiv" skalar eksisterer, såsom rummet over rationelle , algebraiske eller (oftest) reelle tal.

Det tomme sæt, mellemrummet og ethvert lineært underrum af rummet (inklusive det trivielle underrum { 0 }), er konvekse kegler efter denne definition. Andre eksempler er mængden af alle produkter med et positivt tal af en vilkårlig vektor fra , eller den positive orthant af rummet (sættet af alle vektorer, der har positive koordinater). $V$ $V$ $v$ $V$ $\mathbb {R} ^{n}$

Et mere generelt eksempel er mængden af alle vektorer , således at a er en positiv skalar og er et element i en konveks delmængde af rummet . Især hvis er et normeret vektorrum , og er en åben (hv. lukket) kugle i , som ikke indeholder 0, giver denne konstruktion en åben (hhv. lukket ) konveks cirkulær kegle . $\lambda x$ $\lambda$ $x$ $x$ $V$ $V$ $x$ $V$

Skæringspunktet mellem to konvekse kegler i det samme vektorrum er igen en konveks kegle, men foreningen er det måske ikke. [1] Klassen af konvekse kegler er lukket under enhver lineær afbildning . Især hvis er en konveks kegle, så konveks kegle og dens modsætning , og er det største lineære underrum indeholdt i [2] . Sådan et underrum kaldes et blad . [3] $C$ $-C$ $C\cap -C$ $C$

Konvekse kegler og lineære kegler

Hvis er en konveks kegle, så for enhver positiv skalar og enhver vektor fra vektoren ligger i . Det følger heraf, at en konveks kegle er et specialtilfælde af en lineær kegle . $C$ $\alfa$ $x$ $C$ $\alpha x=(\alpha /2)x+(\alpha /2)x$ $C$ $C$

Alternative definitioner

Det følger af ovenstående, at en konveks kegle kan defineres som en lineær kegle, der er lukket under konvekse kombinationer eller blot under addition . Mere kort er et sæt en konveks kegle, hvis og kun hvis og for enhver positiv skalar . [fire] $C$ $\alpha C=C$ $C+C=C$ $\alfa$

Det skal også bemærkes, at sætningen "positive scalarer " i definitionen af en konveks kegle kan erstattes med "ikke-negative scalarer , der ikke samtidigt er nul". $\alfa ,\beta$ $\alfa ,\beta$

Egenskaber for en konveks kegle

Skæringspunktet mellem et hvilket som helst antal konvekse kegler er igen en konveks kegle. Således danner konvekse kegler en lukket familie (ved drift af kryds).
Det koniske skrog er den mindste konvekse kegle, der indeholder det givne sæt. $\operatørnavn {pos}(X)$

Stumpe og skarpe kegler

Ifølge ovenstående definitioner, hvis er en konveks kegle, så er det også en konveks kegle. En konveks kegle siges at være skarp eller stump , afhængigt af om nulvektoren 0 tilhører den eller ej [5] . Nogle gange bruger de udtrykkene spidse og følgelig stumpe [4] [6] . $C$ ${\displaystyle C\cup \{0\))$

Stumpe kegler kan udelukkes fra definitionen af en konveks kegle ved at erstatte ordene "ikke-negative" med "positive" i de betingelser, der er pålagt . Udtrykket " skarp " bruges ofte i en anden betydning - for lukkede kegler, der ikke indeholder hele linjer (det vil sige et ikke-trivielt underrum af det omgivende rum), det vil sige det, der kaldes en "fremspringende" kegle nedenfor. $\alfa ,\beta$

Udstående (skarpe) kegler

En konveks kegle siges at være flad , hvis den indeholder en vektor, der ikke er nul, og dens modsætning , og ellers rager frem [6] . Udstående kogler kaldes ofte også akutte . $x$ $-x$

En stump konveks kegle er altid en udstående kegle, men det modsatte er ikke altid sandt. En konveks kegle stikker ud, hvis og kun hvis . Det vil sige, hvis og kun hvis ikke indeholder et ikke-trivielt lineært underrum . $C$ ${\displaystyle C\cap -C\subseteq \{0\))$ $C$ $V$

Polyedriske kegler

I 1935 beviste G. Weyl ækvivalensen af følgende to definitioner af en polyedrisk kegle :

En polyhedral kegle er et sæt lineære kombinationer med ikke-negative koefficienter af et fast endeligt sæt af vektorer . Disse vektorer kaldes keglegeneratorer . $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))$
En polyhedral kegle er et skæringspunkt mellem et endeligt sæt af (lukkede) halvrum, hvis understøttende hyperplan passerer gennem origo. Tilsvarende kan man tale om et sæt af løsninger til et endeligt sæt af homogene lineære uligheder.

Rationelle polyedriske kegler

En polyedrisk kegle kaldes rationel , hvis alle dens generatorer har heltalskoordinater.

Halve mellemrum

Et hyperplan (lineært) af et rum er det størst mulige rigtige lineære underrum af et rum . Et åbent (hv. lukket ) halvrum af et rum er en delmængde af rummet defineret af betingelsen (hhv. ), hvor er enhver lineær funktion af skalarer i dets felt. Hyperplanet defineret af ligningen er det afgrænsende hyperplan for . $V$ $V$ $V$ $H$ $V$ $L(x)>0$ $L(x)\geqslant 0$ $L$ $V$ $L(v)=0$ $H$

Halvrum (åbne eller lukkede) er konvekse kegler. Imidlertid skal enhver konveks kegle , der ikke er hele rummet , være indeholdt i et lukket halvrum af rummet . Faktisk er en topologisk lukket konveks kegle skæringspunktet mellem alle lukkede halvrum, der indeholder den. Et lignende udsagn gælder for en topologisk åben konveks kegle. $C$ $V$ $H$ $V$

Det perfekte halvrum af et rum defineres rekursivt som følger: hvis det har dimension nul, så er det mængden , ellers er det det åbne halvrum af rummet sammen med det perfekte halvrum af det afgrænsende hyperplan for [ 7] . Med andre ord er dette en analog af begrebet et flag for halve mellemrum. $V$ $V$ $\{0\}$ $H$ $V$ $H$

Ethvert perfekt halvrum er udragende, og desuden er enhver udragende kegle indeholdt i et perfekt halvrum. Med andre ord er perfekte halve mellemrum maksimalt udragende kegler (ved inklusion). Det kan påvises, at enhver akut fremspringende kegle (uanset om den er topologisk lukket eller åben) er skæringspunktet mellem alle perfekte halvrum, der indeholder den.

Udsnit og projektion af konvekse sæt

Plansektion

Et affint hyperplan af et rum er en hvilken som helst delmængde af et rum af formen , hvor er en vektor i og er en (lineær) hyperplan. $V$ $V$ $v+H$ $v$ $V$ $H$

Følgende påstand følger af inklusionsegenskaben i halve rum. Lade være en åben halvplads i og , Hvor er en grænse hyperplan og er enhver vektor i . Lade være en lineær kegle indeholdt i . Så er en konveks kegle, hvis og kun hvis mængden er en konveks delmængde af hyperplanet (det vil sige et sæt, der er lukket under konvekse kombinationer ). $Q$ $V$ $A=H+v$ $H$ $Q$ $v$ $Q$ $C$ $Q$ $C$ $C'=C\cap A$ $EN$

Som en konsekvens af dette resultat har alle egenskaber af konvekse sæt i et affint rum en analog for konvekse kegler indeholdt i et fast åbent halvrum.

Sfærisk sektion

Hvis der gives en norm | • | i rummet definerer vi enhedssfæren i som sættet $V$ $V$

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

Hvis værdierne | • | er skalarer i , så er en linjekegle i en konveks kegle, hvis og kun hvis dens sfæriske snit (sættet af dens vektorer med enhedsnorm ) er en konveks delmængde i følgende betydning: for alle to vektorer med alle vektorer på den korteste vej fra i på ligge i . $V$ $C$ $V$ $C\cap S$ $S$ $u,v\in C$ $u\neq -v$ $u$ $v$ $S$ $C$

Den dobbelte kegle

Lad være en konveks kegle i et rigtigt vektorrum med skalært produkt . Den dobbelte kegle k er sættet [8] [9] $C\subset V$ $V$ $C$

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

Det er også en konveks kegle. Hvis det falder sammen med dets dual, kaldes det selv-dual . $C$ $C$

En anden almindelig definition af den dobbelte kegle for er en kegle i dobbelt rum : $C\subset V$ $C^{\ast }$ $V^{\ast }$

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

Med andre ord, hvis er det dobbelte rum i rummet , så er den dobbelte kegle sæt lineære funktioner, der er ikke-negative på keglen . Hvis vi accepterer, at det er et kontinuerligt dobbeltrum , så er dette sæt af kontinuerlige lineære funktioner, der er ikke-negative på . [10] En sådan definition kræver ikke tilstedeværelsen af et indre produkt i rummet . $V^{\ast }$ $V$ $C$ $V^{\ast }$ $C$ $V$

I finit-dimensionelle rum er begge definitioner af den dobbelte kegle i det væsentlige ækvivalente, da ethvert indre produkt er forbundet med en lineær isomorfi (ikke-degenereret lineær kortlægning) fra til , og denne isomorfi tager den dobbelte kegle (til ) fra den anden definition til den dobbelte kegle fra den første definition. $V^{\ast }$ $V$ $V^{\ast }$

Delvis rækkefølge defineret af en konveks kegle

En skarpt fremspringende konveks kegle genererer en delordre " " på , defineret på en sådan måde , at hvis og kun hvis . (Hvis keglen er flad, giver den samme definition bare forudbestillingen .) Summer og multiplikation med en positiv skalar af den rigtige ulighed i forhold til den rækkefølge giver igen de rigtige uligheder. Et vektorrum med en sådan rækkefølge kaldes et ordnet vektorrum . Kegle $C$ $\leqslant$ $V$ $x \leqslant y$ $yx\in C$

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

kaldes en positiv kegle [6] .

Eksempler inkluderer det ordinære produkt [11] på reelle vektorer ( ) og Löwner-ordenen [12] $\mathbb {R} ^{n}$

Korrekt konveks kegle

Begrebet egentlig ( konveks ) kegle defineres på forskellige måder afhængigt af konteksten. Det betyder ofte en fremspringende konveks kegle, der ikke indeholder noget hyperplan af rummet , måske med andre begrænsninger pålagt, såsom topologisk lukning (og derfor vil keglen være skarp), eller topologisk åbenhed (keglen vil være stump) [13] . Nogle forfattere bruger udtrykket "kile" om det, der i denne artikel omtales som en konveks kegle, og udtrykket "kegle" refererer til det, der i artiklen omtales som en fremspringende skarp kegle, eller hvad der lige er blevet kaldt en egentlig konveks kegle. $V$

Eksempler på konvekse kegler

Lad en lukket konveks delmængde af Hilbert-rummet gives , den normale kegle for et sæt fra et punkt til er givet af en formel. [2] $K$ $V$ $K$ $x$ $K$

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

Lad en lukket konveks delmængde af rummet være givet , tangentkeglen til mængden fra et punkt er givet ved formlen [14] $K$ $V$ $K$ $x$

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

Lad en lukket konveks delmængde af Hilbertrummet være givet , den ydre normalkegle til mængden fra punkt til er givet af formlen [15] $K$ $V$ $K$ $x$ $K$

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

Givet en lukket konveks delmængde af et Hilbert-rum , kan tangentkeglen til mængden i et punkt fra defineres som den polære kegle til den ydre normalkegle : [16] [17] $K$ $V$ $K$ $x$ $K$ $N_{K}(x)$

Normale og tangentkegler er lukkede og konvekse. De er vigtige begreber inden for konveks programmering , variationsmæssige uligheder .

Se også

Relaterede kombinationer

Noter

↑ Rockafellar, 1973 , s. tredive.
↑ 1 2 Rockafellar, 1973 , s. 32.
↑ Krasnoselsky, Lifshits, Sobolev, 1985 , s. 9.
↑ 1 2 Bourbaki, 1959 , s. tredive.
↑ Zorkaltsev, Kiseleva, 2007 .
↑ 1 2 3 Edwards, 1969 , s. 194.
↑ Stolfi, 1991 , s. 139.
↑ Panina, 2009 .
↑ Boyd, Vandenberghe, 2004 .
↑ Kutateladze, 2009 , s. 1127.
↑ Et ordinært produkt er en genereret ordre på et direkte produkt af delvist bestilte sæt. Se Stanley, 1990 for detaljer.
↑ En definition af Löwner orden kan findes i Marshall, Olkin, 1983
↑ Schäfer, 1971 , s. 258.
↑ Panaginotopoulos, 1989 , s. 171.
↑ Panaginotopoulos, 1989 , s. 62.
↑ Rockafellar, 1973 , s. 138.
↑ Leuchtweis, 1985 , s. 54.