Konveks sæt

Et konveks sæt i et affint eller vektorrum er et sæt , hvor alle punkter i segmentet dannet af to punkter i det givne sæt også hører til det givne sæt.

Grænsen for et konveks sæt er altid en konveks kurve . Skæringspunktet mellem alle konvekse sæt, der indeholder en given delmængde A af det euklidiske rum, kaldes det konvekse skrog af A . Dette er det mindste konvekse sæt, der indeholder A .

En konveks funktion er en funktion med reel værdi defineret på et interval med den egenskab, at dens epigraf (sættet af punkter på eller over funktionens graf) er et konveks sæt. Konveks programmering er en delmængde af optimering, der studerer problemet med at minimere konvekse funktioner over konvekse sæt. Den gren af matematik, der er viet til studiet af egenskaberne ved konvekse mængder og konvekse funktioner, kaldes konveks analyse .

Konvekse sæt spiller en vigtig rolle i mange optimeringsproblemer [1] .

Definitioner

Lad være et affint eller vektorrum over feltet af reelle tal . $EN$ $\mathbb {R}$

En mængde kaldes konveksiv , sammen med to vilkårlige punkter , omfatter sættet alle punkter i det segment , der forbinder punkterne og i rummet . Dette segment kan repræsenteres som $K\subset A$ $x,\;y\in K$ $K$ $xy$ $EN$ $x$ $y$

\bigcup \limits _{t\in [0;\;1]}\{x+t\cdot {\overrightarrow {xy}}\}.

Relaterede definitioner

Et sæt af et vektorrum kaldes absolut konveks , hvis det er konveks og afbalanceret . $K$ $V$

Eksempler

Konvekse delmængder af mængden ( sættet af reelle tal) er intervaller fra . $\mathbb {R}$ $\mathbb {R}$
Eksempler på konvekse delmængder i todimensionelt euklidisk rum ( ) er regulære polygoner . $\mathbb {R} ^{2}$
Eksempler på konvekse delmængder i tredimensionelt euklidisk rum ( ) er arkimedeiske faste stoffer og regulære polyedre . $\mathbb {R} ^{3}$
Keppler-Poinsot faste stoffer (almindelige stjernepolyedre) er eksempler på ikke-konvekse sæt.

Egenskaber

Det tomme sæt og al plads er konvekse sæt. Da tomt rum og alt rum også er lukkede sæt , er de også lukkede konvekse sæt.
Sættet af alle konvekse sæt af et lineært rum i forhold til rækkefølgen dannet af inklusionsrelationen er et delvist ordnet sæt, hvor et minimumselement er et tomt sæt og et maksimumelement svarende til hele rummet. Det samme udsagn gælder også for en samling af lukkede konvekse sæt.
Et konveks sæt i et topologisk lineært rum er forbundet og stiforbundet , homotopisk ækvivalent med et punkt.
Med hensyn til tilslutningsmuligheder kan et konveks sæt defineres som følger: et sæt er konveks, hvis dets skæring med en hvilken som helst (virkelig) linje er forbundet.
Lade være et konveks sæt i et lineært rum. Derefter for alle elementer, der tilhører og for alle ikke-negative , sådan at , vektoren $K$ ${\displaystyle u_{1},\;u_{2},\;\ldots ,\;u_{r))$ $K$ ${\displaystyle \lambda _{1},\;\lambda _{2},\;\ldots ,\;\lambda _{r))$ $\lambda _{1}+\lambda _{2}+\ldots +\lambda _{r}=1$ ${\displaystyle w=\sum _{k=1}^{r}\lambda _{k}u_{k))$

tilhører .

K

Vektoren kaldes en konveks kombination af elementer .

w

{\displaystyle u_{1},\;u_{2},\;\ldots ,\;u_{r))

Skæringspunktet for enhver samling af konvekse sæt er et konveks sæt. Da skæringsoperationen også har egenskaberne associativitet og kommutativitet, danner samlingen af konvekse sæt ved skæringsoperationen en kommutativ semigruppe . Denne semigruppe indeholder en enhed svarende til hele rummet. En samling af konvekse sæt er således en monoid ved operationen af skæringspunktet.
Da en familie af konvekse sæt er lukket med hensyn til operationen af skæringspunktet, følger det, at der for enhver delmængde af et lineært rum er et mindste konveks sæt, der indeholder det. Dette sæt er skæringspunktet mellem alle konvekse sæt indeholdende og kaldes det konvekse skrog af . Benævnt med , , og også . $EN$ $EN$ $EN$ $coA$ $co(A)$ $\operatorname {Konv} A$
- Det konvekse skrog på et konveks sæt er det samme som selve sættet.
- Det konvekse skrog af et lukket sæt er et lukket (og konveks) sæt.
- Det konvekse skrog af sættet falder sammen med sættet af alle konvekse lineære kombinationer af vektorer , : $K$ $K$ $u_{1},\;u_{2},\;\ldots ,\;u_{r}\in K$
${\displaystyle w=\sum _{k=1}^{r}\lambda _{k}u_{k))$ , hvor er ikke-negative tal sådan, at . ${\displaystyle \lambda _{1},\;\lambda _{2},\;\ldots ,\;\lambda _{r))$ $\lambda _{1}+\lambda _{2}+\ldots +\lambda _{r}=1$
- Enhver vektor , hvor er en delmængde af det dimensionelle lineære rum , kan repræsenteres som en konveks kombination af ikke mere end vektorer af mængden .
[1] Dette udsagn kaldes Carathéodorys konvekse skrogsætning . $X\in \operatørnavn {Konv} K$ $K$ $n$ ${\displaystyle E^{n))$ $n+1$ $K$

Lad være nogle lukkede konvekse sæt. Så er der en pointe sådan , at for alle

{\displaystyle \Omega \subset E^{n))

X^{*}\in \Omega

X\in \Omega

(X,X^{*})\geqslant (X^{*},X^{*})

. [en]

For et vilkårligt lukket konveks sæt og et punkt, der ikke hører til det , eksisterer der et hyperplan, der adskiller og . [1] Denne sætning kaldes separationssætningen [1] og også støttehyperplansætningen . Støttehyperplansætningen er et specialtilfælde af Hahn-Banach-sætningen om funktionel analyse . $C$ $P$ $C$ $P$
Det følger af støttehyperplansætningen, at for en konveks lukket mængde og et punkt uden for mængden eksisterer der et lukket halvrum (sæt af punkter i rummet, der ligger på den ene side af hyperplanet , inklusive selve hyperplanet) , inklusive og ikke indeholder . Det følger af dette, at alle lukkede konvekse sæt kan dannes ved skæringer af lukkede halvrum. $C$ $C$ $P$ $H$ $C$ $P$
Hellys sætning : Antag, at i en endelig familie af konvekse delmængder , er skæringspunktet mellem nogen af dem ikke-tomt. Så er skæringspunktet mellem alle delmængder fra denne familie ikke-tomt. $\mathbb {R} ^{d}$ $d+1$
Ethvert konveks sæt af enhedsareal i kan være fuldstændig indesluttet i en eller anden trekant af område 2 [2] . $\mathbb {R} ^{2}$
Krein-Milman-sætningen . En konveks kompakt i et lokalt konveks rum falder sammen med lukningen af det konvekse skrog af sættet af dets yderpunkter . $K$ $L$ $E(K)$

Variationer og generaliseringer

Uden ændringer er definitionen også gyldig for affine mellemrum over en vilkårlig udvidelse af feltet af reelle tal.

Algoritmer

Dykstras algoritme - at finde et punkt fra skæringspunktet mellem konvekse sæt.

Se også

Litteratur

Yaglom IM , Boltyansky VG Konvekse figurer . - M. - L. : GTTI, 1951. - 343 s. - (Den matematiske cirkels bibliotek, nummer 4). (Russisk)
Leuchtweiss, K. Konvekse sæt. - M. : Nauka, 1985. - 336 s.
Polovinkin E. S. , Balashov M. V. . Elementer af konveks og stærkt konveks analyse. -M.: FIZMATLIT, 2004. - 416 s. —ISBN 5-9221-0499-3. .
Timorin V. A. Kombinatorik af konvekse polyedre . - M .: MTSNMO , 2002. - 16 s. — ISBN 5-94057-024-0 . .
Demyanov V.F. , Malozemov V.N. Introduktion til minimax. - Moskva: Hovedudgaven af den fysiske og matematiske litteratur fra Nauka-forlaget, 1972. - 368 s.

Noter

↑ 1 2 3 4 5 Demyanov, Malozemov, 1972 .
↑ Weisstein, Eric W. Triangle Circumscribing på Wolfram MathWorld- webstedet .