Mulţime convexă

O multime convexa intr-un spatiu afin sau vectorial este o multime in care toate punctele segmentului format din oricare doua puncte ale multimii date apartin si ele multimii date.

Limita unei mulțimi convexe este întotdeauna o curbă convexă . Intersecția tuturor mulțimilor convexe care conțin o submulțime dată A a spațiului euclidian se numește învelișul convex al lui A. Aceasta este cea mai mică mulțime convexă care conține A .

O funcție convexă este o funcție cu valoare reală definită pe un interval cu proprietatea că epigraful său (setul de puncte de pe sau deasupra graficului funcției) este o mulțime convexă. Programarea convexă este un subset de optimizare care studiază problema minimizării funcțiilor convexe peste mulțimi convexe. Ramura matematicii dedicata studiului proprietatilor multimilor convexe si functiilor convexe se numeste analiza convexa .

Mulțimile convexe joacă un rol important în multe probleme de optimizare [1] .

Definiții

Fie un spațiu afin sau vectorial peste câmpul numerelor reale . $A$ $\mathbb {R}$

O mulțime se numește convexif , împreună cu oricare două puncte , mulțimea include toate punctele segmentului care leagă punctele și în spațiu . Acest segment poate fi reprezentat ca $K\subset A$ $x,\;y\în K$ $K$ $X y$ $A$ $X$ $y$

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

Definiții înrudite

O mulțime a unui spațiu vectorial se numește absolut convexă dacă este convexă și echilibrată . $K$ $V$

Exemple

Submulțimile convexe ale mulțimii (mulțimea numerelor reale) sunt intervale de la . $\mathbb {R}$ $\mathbb {R}$
Exemple de submulțimi convexe din spațiul euclidian bidimensional ( ) sunt poligoane regulate . $\mathbb {R} ^{2}$
Exemple de submulțimi convexe în spațiul euclidian tridimensional ( ) sunt solidele arhimediene și poliedrele regulate . $\mathbb {R} ^{3}$
Solidele Keppler-Poinsot (poliedre stelare obișnuite) sunt exemple de mulțimi neconvexe.

Proprietăți

Mulțimea goală și tot spațiul sunt mulțimi convexe. Deoarece spațiul gol și tot spațiul sunt, de asemenea , mulțimi închise , ele sunt și mulțimi convexe închise.
Mulțimea tuturor mulțimilor convexe ale unui spațiu liniar în raport cu ordinea formată de relația de includere este o mulțime parțial ordonată cu un element minim fiind o mulțime goală și un element maxim egal cu întregul spațiu. Aceeași afirmație este valabilă și pentru o colecție de mulțimi convexe închise.
O mulțime convexă într-un spațiu liniar topologic este conectată și conectată în cale , echivalent homotopic cu un punct.
Din punct de vedere al conectivității, o mulțime convexă poate fi definită după cum urmează: o mulțime este convexă dacă intersecția sa cu orice linie (reală) este conectată.
Fie o mulțime convexă într-un spațiu liniar. Apoi, pentru orice elemente aparținând și pentru toate nenegative , astfel încât , vectorul $K$ $u_{1},\;u_{2},\;\ldots ,\;u_{r)$ $K$ $\lambda _{1},\;\lambda _{2},\;\ldots,\;\lambda _{r)$ $\lambda _{1}+\lambda _{2}+\ldots +\lambda _{r}=1$ $w=\sum _{k=1}^{r}\lambda _{k}u_{k)$

aparține .

K

Vectorul se numește o combinație convexă de elemente .

w

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

Intersecția oricărei colecții de mulțimi convexe este o mulțime convexă. Deoarece operația de intersecție are și proprietățile de asociativitate și comutativitate, colecția de mulțimi convexe prin operația de intersecție formează un semigrup comutativ . Acest semigrup conține o unitate egală cu întregul spațiu. Astfel, o colecție de mulțimi convexe este un monoid prin operația de intersecție.
Deoarece o familie de mulțimi convexe este închisă în raport cu operația de intersecție, rezultă că pentru orice submulțime a unui spațiu liniar există o cea mai mică mulțime convexă care o conține. Această mulțime este intersecția tuturor mulțimilor convexe care conțin și se numește corpul convex al . Notat cu , , și, de asemenea, . $A$ $A$ $A$ $coA$ $co(A)$ $\operatorname {Conv} A$
- Carcasa convexă a unei mulțimi convexe este aceeași cu setul în sine.
- Corpul convex al unei mulțimi închise este o mulțime închisă (și convexă).
- Învelișul convex al mulțimii coincide cu mulțimea tuturor combinațiilor liniare convexe de vectori : $K$ $K$ $u_{1},\;u_{2},\;\ldots ,\;u_{r}\in K$
$w=\sum _{k=1}^{r}\lambda _{k}u_{k)$ , unde sunt numere nenegative astfel încât . $\lambda _{1},\;\lambda _{2},\;\ldots,\;\lambda _{r)$ $\lambda _{1}+\lambda _{2}+\ldots +\lambda _{r}=1$
- Orice vector , unde este o submulțime de spațiu liniar dimensional , poate fi reprezentat ca o combinație convexă de nu mai mult de vectori ai mulțimii .
[1] Această afirmație se numește teorema carcasei convexe a lui Carathéodory . $X\in \operatorname {Conv} K$ $K$ $n$ $E^{n)$ $n+1$ $K$

Să fie o mulțime convexă închisă. Apoi există un punct astfel încât pentru toți

\Omega \subset E^{n)

X^{*}\in \Omega

X\in \Omega

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

. [unu]

Pentru o mulțime convexă închisă arbitrară și un punct care nu îi aparține , există un hiperplan care separă și . [1] Această afirmație se numește teorema separării [1] și, de asemenea , teorema hiperplanului suport . Teorema hiperplanului suport este un caz special al teoremei Hahn-Banach de analiză funcțională . $C$ $P$ $C$ $P$
Din teorema hiperplanului de susținere rezultă că pentru o mulțime închisă convexă și un punct în afara mulțimii , există un semi -spațiu închis (seturi de puncte din spațiu care se află pe o parte a hiperplanului , inclusiv hiperplanul însuși) , inclusiv și neconținând . De aici rezultă că toate mulțimile convexe închise pot fi formate prin intersecții de semi-spații închise. $C$ $C$ $P$ $H$ $C$ $P$
Teorema lui Helly : Să presupunem că într-o familie finită de submulțimi convexe , intersecția oricăreia dintre ele este nevidă. Atunci intersecția tuturor submulților din această familie nu este goală. $\mathbb {R} ^{d}$ $d+1$
Orice set convex de unitate de suprafață în poate fi complet închis într-un triunghi de zonă 2 [2] . $\mathbb {R} ^{2}$
Teorema Krein-Milman . O compactă convexă într-un spațiu local convex coincide cu închiderea carcasei convexe a mulțimii punctelor sale extreme . $K$ $L$ $E(K)$

Variații și generalizări

Fără modificări, definiția este valabilă și pentru spații afine peste o extensie arbitrară a câmpului numerelor reale.

Algoritmi

Algoritmul lui Dykstra - găsirea unui punct de la intersecția mulțimilor convexe.

Vezi și

Literatură

Yaglom IM , Boltyansky VG Cifre convexe . - M. - L. : GTTI, 1951. - 343 p. - (Biblioteca cercului matematic, numărul 4). (Rusă)
Leuchtweiss, K. Mulțimi convexe. - M. : Nauka, 1985. - 336 p.
Polovinkin E. S. , Balashov M. V. . Elemente de analiză convexă și puternic convexă. -M.: FIZMATLIT, 2004. - 416 p. —ISBN 5-9221-0499-3. .
Timorin V. A. Combinatoria poliedrelor convexe . - M. : MTSNMO , 2002. - 16 p. — ISBN 5-94057-024-0 . .
Demyanov V.F. , Malozemov V.N. Introducere în minimax. - Moscova: Ediția principală a literaturii fizice și matematice a editurii Nauka, 1972. - 368 p.

Note

↑ 1 2 3 4 5 Demyanov, Malozemov, 1972 .
^ Weisstein , Eric W. Triangle Circumscribing pe site- ul Wolfram MathWorld .