Kupera joukko

Konveksi joukko affiinissa tai vektoriavaruudessa on joukko , jossa kaikki kahdesta tietyn joukon pisteen muodostaman janan pisteet kuuluvat myös annettuun joukkoon.

Konveksin joukon raja on aina kupera käyrä . Kaikkien konveksien joukkojen leikkauskohtaa, jotka sisältävät tietyn euklidisen avaruuden osajoukon A , kutsutaan A : n kuperaksi rungoksi . Tämä on pienin kupera joukko, joka sisältää A:n .

Konveksi funktio on reaaliarvoinen funktio , joka on määritetty aikavälille, jolla on ominaisuus, että sen epigrafi (funktion kuvaajan tai sen yläpuolella olevien pisteiden joukko) on kupera joukko. Konveksi ohjelmointi on optimoinnin osajoukko, joka tutkii ongelmaa minimoida kuperat funktiot kuperien joukkojen yli. Matematiikan haaraa, joka on omistettu konveksien joukkojen ja konveksien funktioiden ominaisuuksien tutkimukselle, kutsutaan konveksianalyysiksi .

Konveksilla joukoilla on tärkeä rooli monissa optimointiongelmissa [1] .

Määritelmät

Antaa olla affiininen tai vektoriavaruus todellisten lukujen kentän yli . $A$ $\mathbb {R}$

Joukkoa kutsutaan konveksiksi , yhdessä minkä tahansa kahden pisteen kanssa joukko sisältää kaikki pisteitä yhdistävän janan pisteet avaruudessa . Tämä segmentti voidaan esittää muodossa $K\subset A$ $x,\;y\in K$ $K$ $xy$ $A$ $x$ $y$

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

Aiheeseen liittyvät määritelmät

Vektoriavaruuden joukkoa kutsutaan ehdottoman kuperaksi , jos se on kupera ja tasapainoinen . $K$ $V$

Esimerkkejä

Joukon kuperat osajoukot (reaalilukujen joukko ) ovat väliä . $\mathbb {R}$ $\mathbb {R}$
Esimerkkejä kuperista osajoukoista kaksiulotteisessa euklidisessa avaruudessa ( ) ovat säännölliset polygonit . $\mathbb {R} ^{2}$
Esimerkkejä konvekseista osajoukoista kolmiulotteisessa euklidisessa avaruudessa ( ) ovat Archimedean solids ja säännölliset polyhedrat . $\mathbb {R} ^{3}$
Keppler-Poinsot-kiintoaineet (säännölliset tähtipolyhedrat) ovat esimerkkejä ei-kuperista joukoista.

Ominaisuudet

Tyhjä joukko ja kaikki tila ovat kuperia joukkoja. Koska tyhjä tila ja kaikki tila ovat myös suljettuja joukkoja , ne ovat myös suljettuja kuperajoukkoja.
Lineaarisen avaruuden konveksien joukkojen joukko inkluusiorelaation muodostaman järjestyksen suhteen on osittain järjestetty joukko , jossa minimialkio on tyhjä joukko ja maksimialkio yhtä suuri kuin koko avaruus. Sama väite pätee myös suljettujen kuperajoukkojen joukolle.
Topologisessa lineaariavaruudessa oleva konveksi joukko on yhdistetty ja polkukytketty, mikä vastaa homotooppisesti pistettä.
Konnektiivisuuden kannalta kupera joukko voidaan määritellä seuraavasti: joukko on konveksi, jos sen leikkauspiste minkä tahansa (todellisen) suoran kanssa on yhdistetty.
Antaa olla kupera joukko lineaarisessa avaruudessa. Sitten kaikille elementeille , jotka kuuluvat ja kaikille ei-negatiivisille , Niin että , vektori $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))$

kuuluu .

K

Vektoria kutsutaan kuperaksi elementtien yhdistelmäksi .

w

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

Minkä tahansa kupera joukkojen joukon leikkauspiste on kupera joukko. Koska leikkausoperaatiolla on myös assosiatiivisuuden ja kommutatiivisuuden ominaisuuksia, muodostaa leikkausoperaation konveksien joukkojen kokoelma kommutatiivisen puoliryhmän . Tämä puoliryhmä sisältää yksikön, joka vastaa koko avaruutta. Siten joukko kuperia joukkoja on monoidi leikkausoperaation mukaan.
Koska konveksien joukkojen perhe on suljettu leikkausoperaation suhteen, tästä seuraa, että mille tahansa lineaarisen avaruuden osajoukolle on pienin konveksi joukko, joka sisältää sen. Tämä joukko on kaikkien kuperoiden, jotka sisältävät joukon, leikkauspiste , ja sitä kutsutaan kuperaksi rungoksi . Merkitään , , ja myös . $A$ $A$ $A$ $coA$ $co(A)$ $\operaattorin nimi {Conv} A$
- Kuperan joukon kupera runko on sama kuin itse joukko.
- Suljetun joukon kupera runko on suljettu (ja kupera) joukko.
- Joukon kupera runko osuu yhteen kaikkien konveksien lineaaristen vektorien yhdistelmien joukon kanssa : $K$ $K$ $u_{1},\;u_{2},\;\ldots ,\;u_{r}\in K$
${\displaystyle w=\sum _{k=1}^{r}\lambda _{k}u_{k))$ , missä ovat ei-negatiiviset luvut siten, että . ${\displaystyle \lambda _{1},\;\lambda _{2},\;\ldots ,\;\lambda _{r))$ $\lambda _{1}+\lambda _{2}+\ldots +\lambda _{r}=1$
- Mikä tahansa vektori , jossa on -ulotteisen lineaariavaruuden osajoukko , voidaan esittää kuperana yhdistelmänä enintään joukon vektoreista .
[1] Tätä väitettä kutsutaan Carathéodoryn kuperaksi rungon lauseeksi . $X\in \operatorname {Conv} K$ $K$ $n$ $E^{n}$ $n+1$ $K$

Olkoon jokin suljettu kupera joukko. Sitten on sellainen asia , että kaikille

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

X^{*}\in \Omega

X\in \Omega

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

. [yksi]

Mielivaltaiselle suljetulle kuperalle joukolle ja siihen kuulumattomalle pisteelle on olemassa hypertaso, joka erottaa ja . [1] Tätä lausetta kutsutaan erottelulauseeksi [1] ja myös tukihypertasolauseeksi . Tukihypertasolause on funktionaalisen analyysin Hahn–Banachin teoreeman erikoistapaus . $C$ $P$ $C$ $P$
Tukihypertasolauseesta seuraa, että kuperalle suljetulle joukolle ja joukon ulkopuolella olevalle pisteelle on olemassa suljettu puoliavaruus (avaruuden pisteiden joukkoa, jotka sijaitsevat hypertason toisella puolella , mukaan lukien itse hypertaso) . ei sisällä . Tästä seuraa, että kaikki suljetut kuperat joukot voidaan muodostaa suljettujen puoliavaruuksien leikkauspisteillä. $C$ $C$ $P$ $H$ $C$ $P$
Hellyn lause : Oletetaan, että konveksien osajoukkojen äärellisessä perheessä minkä tahansa niistä leikkauspiste on ei-tyhjä. Tällöin kaikkien tämän perheen osajoukkojen leikkauspiste on ei-tyhjä. $\mathbb {R} ^{d}$ $d+1$
Mikä tahansa kupera yksikköpinta- alan joukko in voidaan sulkea kokonaan johonkin pinta-alan 2 kolmioon [2] . $\mathbb {R} ^{2}$
Krein-Milmanin lause . Paikallisesti kuperassa tilassa oleva kupera kompakti osuu yhteen sen ääripisteiden joukon kuperan rungon sulkeutumisen kanssa . $K$ $L$ $E(K)$

Muunnelmia ja yleistyksiä

Ilman muutoksia määritelmä pätee myös affiineille reaalilukukentän mielivaltaisen laajennuksen yli.

Algoritmit

Dykstran algoritmi - pisteen löytäminen kuperajoukkojen leikkauspisteestä.

Katso myös

Kirjallisuus

Yaglom IM , Boltyansky VG Kuperat hahmot . - M. - L. : GTTI, 1951. - 343 s. - (Matematiikan ympyrän kirjasto, numero 4). (Venäjän kieli)
Leuchtweiss, K. Kupera sarja. - M .: Nauka, 1985. - 336 s.
Polovinkin E.S. , Balashov M.V .. Konveksin ja vahvasti kuperan analyysin elementit. -M.: FIZMATLIT, 2004. - 416 s. —ISBN 5-9221-0499-3. .
Timorin V. A. Kuperan polyhedran kombinatoriikka . - M. : MTSNMO , 2002. - 16 s. — ISBN 5-94057-024-0 . .
Demyanov V.F. , Malozemov V.N. Minimaxin esittely. - Moskova: Nauka-kustantamon fyysisen ja matemaattisen kirjallisuuden pääpainos, 1972. - 368 s.

Muistiinpanot

↑ 1 2 3 4 5 Demjanov, Malozemov, 1972 .
↑ Weisstein, Eric W. Triangle Circumscribing Wolfram MathWorld -verkkosivustolla .