Domború halmaz

Konvex halmaz egy affin vagy vektortérben olyan halmaz , amelyben az adott halmaz bármely két pontja által alkotott szakasz minden pontja is az adott halmazhoz tartozik.

A konvex halmaz határa mindig egy konvex görbe . Az euklideszi tér adott A részhalmazát tartalmazó összes konvex halmaz metszéspontját A konvex burának nevezzük . Ez a legkisebb konvex halmaz, amely A -t tartalmaz .

A konvex függvény egy valós értékű függvény , amelyet egy intervallumon definiálunk azzal a tulajdonsággal, hogy az epigráfja (a függvény grafikonján vagy felette lévő pontok halmaza) konvex halmaz. A konvex programozás az optimalizálás egy részhalmaza, amely a konvex függvények konvex halmazok feletti minimalizálásának problémáját vizsgálja. A matematikának a konvex halmazok és konvex függvények tulajdonságainak vizsgálatával foglalkozó ágát konvex elemzésnek nevezzük .

A konvex halmazok számos optimalizálási feladatban fontos szerepet játszanak [1] .

Definíciók

Legyen affin vagy vektortér a valós számok mezője felett . $A$ $\mathbb {R}$

Egy halmazt konvexinak nevezünk , tetszőleges két ponttal együtt a halmaz tartalmazza a pontokat összekötő szakasz összes pontját a térben . Ezt a szegmenst úgy ábrázolhatjuk $K\subset A$ $x,\;y\in K$ $K$ $xy$ $A$ $x$ $y$

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

Kapcsolódó definíciók

Egy vektortér halmazát abszolút konvexnek nevezzük , ha konvex és kiegyensúlyozott . $K$ $V$

Példák

A halmaz konvex részhalmazai (a valós számok halmaza) a -tól kezdődő intervallumok . $\mathbb {R}$ $\mathbb {R}$
A kétdimenziós euklideszi térben ( ) lévő konvex részhalmazokra példák a szabályos sokszögek . $\mathbb {R} ^{2}$
Konvex részhalmazok a háromdimenziós euklideszi térben ( ) az archimédeszi testek és a szabályos poliéderek . $\mathbb {R} ^{3}$
A Keppler-Poinsot testek (szabályos csillagpoliéderek) a nem konvex halmazok példái.

Tulajdonságok

Az üres halmaz és a teljes tér konvex halmazok. Mivel az üres tér és az összes tér is zárt halmazok , ezek is zárt konvex halmazok.
Egy lineáris tér összes konvex halmazának halmaza a befogadási reláció által alkotott sorrendhez képest egy részlegesen rendezett halmaz , amelynek minimális eleme üres halmaz, maximum eleme pedig a teljes térrel egyenlő. Ugyanez az állítás érvényes zárt konvex halmazok gyűjteményére is.
A topologikus lineáris térben lévő konvex halmaz össze van kötve és útkapcsolatban van , homotopikusan ekvivalens egy ponttal.
A konvex halmaz a konvexitás szempontjából a következőképpen definiálható: egy halmaz akkor konvex, ha a metszéspontja bármely (valós) egyenessel összefügg.
Legyen konvex halmaz egy lineáris térben. Ezután minden olyan elemre, amely a -hoz tartozik, és minden nem negatívra , úgy, hogy a vektor $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))$

tartozik hozzá .

K

A vektort elemek konvex kombinációjának nevezzük .

w

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

A konvex halmazok bármely gyűjteményének metszéspontja egy konvex halmaz. Mivel a metszésműveletnek az asszociativitási és kommutativitási tulajdonságai is vannak, a metszésművelet által a konvex halmazok gyűjteménye kommutatív félcsoportot alkot . Ez a félcsoport a teljes térrel egyenlő egységet tartalmaz. Így a konvex halmazok gyűjteménye a metszés művelete alapján monoid .
Mivel a konvex halmazok családja zárt a metszés művelete szempontjából, ebből következik, hogy a lineáris tér bármely részhalmazához van egy legkisebb konvex halmaz, amely tartalmazza azt. Ez a halmaz az összes olyan konvex halmaz metszéspontja, amely tartalmazza a -t , és konvex burának nevezzük . Jelölése , , és szintén . $A$ $A$ $A$ $coA$ $co(A)$ $\operatorname {Conv} A$
- A konvex halmaz domború héja megegyezik magával a halmazzal.
- A zárt halmaz domború teste zárt (és konvex) halmaz.
- A halmaz konvex héja egybeesik az összes konvex lineáris vektorkombináció halmazával , : $K$ $K$ $u_{1},\;u_{2},\;\ldots ,\;u_{r}\in K$
${\displaystyle w=\sum _{k=1}^{r}\lambda _{k}u_{k))$ , ahol olyan nemnegatív számok vannak, hogy . ${\displaystyle \lambda _{1},\;\lambda _{2},\;\ldots ,\;\lambda _{r))$ $\lambda _{1}+\lambda _{2}+\ldots +\lambda _{r}=1$
- Bármely vektor , ahol a -dimenziós lineáris tér egy részhalmaza, ábrázolható a halmaz legfeljebb vektorainak konvex kombinációjaként .
[1] Ezt az állítást Carathéodory konvex héjtételének nevezik . $X\in \operatorname {Conv} K$ $K$ $n$ ${\displaystyle E^{n))$ $n+1$ $K$

Legyen valamilyen zárt konvex halmaz. Aztán van egy pont , hogy mindenki számára

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

X^{*}\in \Omega

X\in \Omega

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

. [egy]

Egy tetszőleges zárt konvex halmazhoz és egy nem hozzá tartozó ponthoz létezik egy hipersík, amely elválasztja és -t . [1] Ezt az állítást elválasztási tételnek [1] és támaszhipersík-tételnek is nevezik . A támaszhipersík-tétel a funkcionális elemzés Hahn–Banach-tételének speciális esete . $C$ $P$ $C$ $P$
A támogatási hipersík tételből következik, hogy egy konvex zárt halmazhoz és egy halmazon kívüli ponthoz létezik zárt féltér (a térben lévő pontok halmazai, amelyek a hipersík egyik oldalán helyezkednek el , beleértve magát a hipersíkot is) , beleértve a nem tartalmaz . Ebből következik, hogy zárt félterek metszéspontjaival minden zárt konvex halmaz alkotható. $C$ $C$ $P$ $H$ $C$ $P$
Helly tétele : Tegyük fel, hogy a konvex részhalmazok véges családjában bármelyik metszéspontja nem üres. Ekkor a család összes részhalmazának metszéspontja nem üres. $\mathbb {R} ^{d}$ $d+1$
Bármely konvex egységnyi területhalmaz teljesen bezárható valamilyen 2 -es területű háromszögbe [2] . $\mathbb {R} ^{2}$
A Krein-Milman tétel . A lokálisan konvex térben konvex kompakt egybeesik a szélső pontjai halmazának konvex testének záródásával . $K$ $L$ $E(K)$

Változatok és általánosítások

A definíció minden változtatás nélkül érvényes a valós számok mezőjének tetszőleges kiterjesztése feletti affin terekre is.

Algoritmusok

Dykstra algoritmusa - pont keresése a konvex halmazok metszéspontjából.

Lásd még

Irodalom

Yaglom IM , Boltyansky VG Konvex figurák . - M. - L. : GTTI, 1951. - 343 p. - (A matematikai kör könyvtára, 4. szám). (Orosz)
Leuchtweiss, K. Konvex halmazok. - M. : Nauka, 1985. - 336 p.
Polovinkin E. S. , Balashov M. V. . A konvex és erősen konvex elemzés elemei. -M.: FIZMATLIT, 2004. - 416 p. —ISBN 5-9221-0499-3. .
Timorin V. A. Konvex poliéderek kombinatorikája . - M. : MTSNMO , 2002. - 16 p. — ISBN 5-94057-024-0 . .
Demyanov V.F. , Malozemov V.N. A minimax bemutatása. - Moszkva: A Nauka kiadó fizikai és matematikai szakirodalmának főkiadása, 1972. - 368 p.

Jegyzetek

↑ 1 2 3 4 5 Demyanov, Malozemov, 1972 .
↑ Weisstein, Eric W. Triangle Circumscribing a Wolfram MathWorld weboldalán .