Konvexní sada

Konvexní množina v afinním nebo vektorovém prostoru je množina , ve které do dané množiny patří i všechny body úsečky tvořené libovolnými dvěma body dané množiny.

Hranicí konvexní množiny je vždy konvexní křivka . Průsečík všech konvexních množin obsahujících danou podmnožinu A euklidovského prostoru se nazývá konvexní obal A . Toto je nejmenší konvexní množina obsahující A .

Konvexní funkce je funkce s reálnou hodnotou definovaná na intervalu s tou vlastností, že její epigraf (množina bodů na grafu funkce nebo nad ním) je konvexní množina. Konvexní programování je podmnožinou optimalizace, která studuje problém minimalizace konvexních funkcí oproti konvexním množinám. Odvětví matematiky věnované studiu vlastností konvexních množin a konvexních funkcí se nazývá konvexní analýza .

Konvexní množiny hrají důležitou roli v mnoha optimalizačních problémech [1] .

Definice

Dovolit být afinní nebo vektorový prostor nad polem reálných čísel . $A$ $\mathbb {R}$

Množina se nazývá konvexní , spolu s libovolnými dvěma body množina zahrnuje všechny body úsečky , která body spojuje, a v prostoru . Tento segment může být reprezentován jako $K\subset A$ $x,\;y\in K$ $K$ $xy$ $A$ $X$ $y$

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

Související definice

Množina vektorového prostoru se nazývá absolutně konvexní , pokud je konvexní a vyvážená . $K$ $PROTI$

Příklady

Konvexní podmnožiny množiny (množina reálných čísel) jsou intervaly od . $\mathbb {R}$ $\mathbb {R}$
Příklady konvexních podmnožin ve dvourozměrném euklidovském prostoru ( ) jsou pravidelné mnohoúhelníky . $\mathbb {R} ^{2}$
Příklady konvexních podmnožin v trojrozměrném euklidovském prostoru ( ) jsou Archimedova tělesa a pravidelné mnohostěny . $\mathbb {R} ^{3}$
Tělesa Keppler-Poinsot (pravidelné hvězdicové mnohostěny) jsou příklady nekonvexních množin.

Vlastnosti

Prázdná množina a veškerý prostor jsou konvexní množiny. Protože prázdný prostor a veškerý prostor jsou také uzavřené množiny , jedná se také o uzavřené konvexní množiny.
Množina všech konvexních množin lineárního prostoru vzhledem k řádu tvořenému inkluzní relací je částečně uspořádaná množina , přičemž minimálním prvkem je prázdná množina a maximálním prvkem je celý prostor. Totéž platí také pro kolekci uzavřených konvexních množin.
Konvexní množina v topologickém lineárním prostoru je spojena a propojena cestou , homotopicky ekvivalentní bodu.
Z hlediska konektivity lze konvexní množinu definovat následovně: množina je konvexní, pokud je její průsečík s libovolnou (skutečnou) přímkou spojen.
Dovolit být konvexní soubor v lineárním prostoru. Potom pro všechny prvky patřící do a pro všechny nezáporné , jako je , vector $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))$

patří k .

K

Vektor se nazývá konvexní kombinace prvků .

w

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

Průsečíkem jakékoli kolekce konvexních množin je konvexní množina. Protože operace průniku má také vlastnosti asociativnosti a komutativnosti, sbírka konvexních množin pomocí operace průniku tvoří komutativní pologrupu . Tato pologrupa obsahuje jednotku rovnou celému prostoru. Kolekce konvexních množin je tedy operací průniku monoidem .
Protože rodina konvexních množin je z hlediska operace průniku uzavřená, vyplývá z toho, že pro jakoukoli podmnožinu lineárního prostoru existuje nejmenší konvexní množina, která ji obsahuje. Tato množina je průsečíkem všech konvexních množin obsahujících , a nazývá se konvexní obal . Označuje se , , a také . $A$ $A$ $A$ $coA$ $co(A)$ $\operatorname {Conv} A$
- Konvexní trup konvexní sady je stejný jako samotná sada.
- Konvexní trup uzavřeného souboru je uzavřený (a konvexní) soubor.
- Konvexní obal množiny se shoduje s množinou všech konvexních lineárních kombinací vektorů , : $K$ $K$ $u_{1},\;u_{2},\;\ldots ,\;u_{r}\in K$
${\displaystyle w=\sum _{k=1}^{r}\lambda _{k}u_{k))$ , kde jsou nezáporná čísla taková, že . ${\displaystyle \lambda _{1},\;\lambda _{2},\;\ldots ,\;\lambda _{r))$ $\lambda _{1}+\lambda _{2}+\ldots +\lambda _{r}=1$
- Jakýkoli vektor , kde je podmnožina -rozměrného lineárního prostoru , může být reprezentován jako konvexní kombinace ne více než vektorů množiny .
[1] Toto tvrzení se nazývá Carathéodoryho věta o konvexním trupu . $X\in \operatorname {Conv} K$ $K$ $n$ ${\displaystyle E^{n))$ $n+1$ $K$

Nechť je nějaká uzavřená konvexní množina. Pak je tu bod takový , že pro všechny

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

X^{*}\in \Omega

X\in \Omega

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

. [jeden]

Pro libovolnou uzavřenou konvexní množinu a bod do ní nepatřící existuje nadrovina oddělující a . [1] Toto tvrzení se nazývá separační teorém [1] a také podpůrný teorém o nadrovině . Věta o podpůrné nadrovině je speciálním případem Hahn–Banachovy věty funkcionální analýzy . $C$ $P$ $C$ $P$
Z podpůrné věty o nadrovině vyplývá, že pro konvexní uzavřenou množinu a bod mimo množinu existuje uzavřený poloprostor (množiny bodů v prostoru, které leží na jedné straně nadroviny , včetně samotné nadroviny) , včetně a neobsahující . Z toho vyplývá, že všechny uzavřené konvexní množiny mohou být tvořeny průniky uzavřených poloprostorů. $C$ $C$ $P$ $H$ $C$ $P$
Hellyho věta : Předpokládejme, že v konečné rodině konvexních podmnožin je průsečík kterékoli z nich neprázdný. Pak je průsečík všech podmnožin z této rodiny neprázdný. $\mathbb {R} ^{d}$ $d+1$
Libovolná konvexní množina jednotkové plochy v může být zcela uzavřena v nějakém trojúhelníku plochy 2 [2] . $\mathbb {R} ^{2}$
Krein-Milmanova věta . Konvexní kompakt v lokálně konvexním prostoru se shoduje s uzavřením konvexního trupu množiny jeho krajních bodů . $K$ $L$ $E(K)$

Variace a zobecnění

Beze změn platí definice i pro afinní prostory nad libovolným rozšířením oboru reálných čísel.

Algoritmy

Dykstrův algoritmus - nalezení bodu z průsečíku konvexních množin.

Viz také

Literatura

Yaglom IM , Boltyansky VG Konvexní postavy . - M. - L. : GTTI, 1951. - 343 s. - (Knihovna matematického kroužku, číslo 4). (Ruština)
Leuchtweiss, K. Konvexní množiny. - M. : Nauka, 1985. - 336 s.
Polovinkin E. S. , Balashov M. V. . Prvky konvexní a silně konvexní analýzy. -M.: FIZMATLIT, 2004. - 416 s. —ISBN 5-9221-0499-3. .
Timorin V. A. Kombinatorika konvexních mnohostěnů . - M. : MTSNMO , 2002. - 16 s. — ISBN 5-94057-024-0 . .
Demjanov V.F. , Malozemov V.N. Úvod do minimaxu. - Moskva: Hlavní vydání fyzikální a matematické literatury nakladatelství Nauka, 1972. - 368 s.

Poznámky

↑ 1 2 3 4 5 Demjanov, Malozemov, 1972 .
↑ Weisstein, Eric W. Triangle Circumifying na webu Wolfram MathWorld .