Oddělování konvexních množin
Oddělitelnost množin
Definice 2.3.1 (Oddělitelnost množin)
Neprázdné množiny X1,X2 se nazývají
-
oddělitelné, jestliže existuje p∈Rn∖{0} takové, že
⟨p,x1⟩≥⟨p,x2⟩
pro každé x1∈X1,x2∈X2.
-
vlastně oddělitelné, jestliže jsou oddělitelné a zároveň existují body x1∗∈X1,x2∗∈X2 takové, že
⟨p,x1∗⟩>⟨p,x2∗⟩
-
silně oddělitelné, jestliže existuje p∈Rn∖{0} takové, že
x1∈x1inf⟨p,x1⟩>x2∈X2sup⟨p,x2⟩,
je-li navíc β∈[supx2∈X2⟨p,x2⟩,infx1∈X1⟨p,x1⟩], nadrovina
Hp,β:={x∈Rn∣⟨p,x⟩=β}
se nazývá oddělující narovinou množin X1 a X2.
Ve vyjádření {x∈Rn∣⟨p,x⟩=β} značí p normálový vektor nadroviny a β její posunutí
Definice 2.3.2 (Projekce bodu)
Nechť X⊆Rn je neprázdná množina a x∈Rn. Bod x∗∈X nazveme projekcí bodu x na množinu X a označíme ΠX(x), jestliže
∥ΠX(x)−x∥≤∥y−x∥
pro každé y∈X.
Věta 2.3.4
Neprázdné konvexní množiny X1,X2∈Rn jsou silně oddělitelné právě tehdy, když mají nenulovou vzdálenost, tj.
ρ(X1,X2):=x1∈X1,x2∈X2inf∥x1−x2∥>0,
což je ekvivalentní s podmínkou 0∈/X1−X2.
Pod kompaktní množinou myslíme množinu, která je ohraničená (má konečný průměr) a uzavřená (obsahuje svou hranici).
Pokud jsou množiny X1,X2⊆Rn neprázdné, konvexní a disjunktní a navíc BÚNO je X1 ohraničená a X2 kompaktní, tak jsou množiny silně oddělitelné.
Požadavek kompaktnosti množiny X2 vynechat nelze, viz protipříklad dvou hyperbol (obrázek je pouze ilustrativní)
Věta 2.3.5a (Geometrický popis konvexních množin)
Libovolná uzavřená konvexní množina X⊆Rn je řešením (nekonečné) soustavy neostrých lineárních rovnic.
Geometricky: každá uzavřená konvexní množina X⫋Rn je průnikem uzavřených poloprostorů, konkrétně všech uzavřených poloprostorů obsahujících X

Opěrné nadroviny
Definice 2.3.6 (Opěrná nadrovina)
Nechť X⊆Rn je neprázdná množina a nechť a∈∂X:=X∖intX. Nadrovina Hp,β se nazývá
-
opěrnou nadrovinou množiny X v bodě a, jestliže
⟨p,x⟩≥β=⟨p,a⟩
pro každé x∈X
-
vlastní opěrnou nadrovinou množiny X, jestliže je opěrnou nadrovinou množiny X a zároveň existuje x∗∈X takové, že
⟨p,x∗⟩>β
Jinak řečeno množina musí ležet pouze v jednom z poloprostorů určených opěrnou nadrovinou.
Věta 2.3.7 (Existenci opěrné nadroviny)
Nechť X⊆Rn je neprázdná konvexní množina a nechť a∈r∂X⊆∂X. Pak v bodě a existuje vlastní opěrná nadrovina množiny X.
Pro relativní vnitřek riX množiny X a její vnitřek platí intX⊆riX a tedy jistě
X∖riX=r∂X⊆∂X=X∖intX
Podmínky oddělitelnosti
Věta 2.3.7a (Oddělitelnost množin)
Nechť X1,X2⊆Rn jsou neprázdné, konvexní a disjunktní množiny. Pak pro tyto množiny existuje oddělující nadrovina.
Věta 2.3.8
Neprázdné konvexní množiny X1,X2⊆Rn jsou vlastně oddělitelné právě tehdy, když riX1∩riX2=∅.
Věta 2.3.9 (Farkas & Minkowski)
Nechť A∈Rm×n a b∈Rm. Potom je právě jeden z následujících systémů rovnic a nerovnic řešitelný:
Ax=b,x≥0,(2.3.5)
ATy≥0,⟨y,b⟩<0(2.3.6)
Jinak řečeno soustava (2.3.5) má řešení právě tehdy, když pro všechna y∈Rm platí ATy≥0 a zároveň ⟨y,b⟩≥0
Ještě jinak můžeme větu formulovat tak, že buď b leží v konvexním kuželu cone{ai}i=1n nebo jsou b a konvexní kužel silně oddělitelné.

Z této věty pak plynou tzv. věty o alternativě, které můžeme najít například v lineárním programování.
Tvrzení Věty 2.3.9 můžeme také napsat jako:
Jestliže systém
f0(x):=⟨a0,x⟩<0,fi(x):=⟨ai,x⟩≤0,i∈{1,…,m}
nemá pro daná a0,…,am∈Rm řešení na Rn, pak existují čísla y1,…,ym≥0 taková, že
a0+i=1∑myiai=0,tj. f0(x)+i=1∑myifi(x)=0
pro každé x∈Rn.
Toto plyne z toho, že pokud v (2.3.9) položíme b=a0 a A=−(a1,…,am) (a zaměníme-li x a y), pak podle předpokladu nemá systém ATx≥0&⟨x,a0⟩<0 řešení. A tedy dostáváme, že systém Ay=a0,y≥0 řešení mít musí.
Věta 2.3.12 (Fan & Glicksburg & Hoffman)
Nechť množina X⊆Rn je konvexní, funkce f1,…,fk:X→R jsou konvexní a funkce fk+1,…,fm afinní, tj. pro j∈{k+1,…,m} máme fj=⟨aj,x⟩+βj pro vhodná aj∈Rn a βj∈R. Jestliže systém nerovností a rovností
fi(x)<0,fj(x)=0,i∈{1,…,k}j∈{k+1,…,m}}(2.3.8)
nemá řešení na X, pak existují takové konstanty
y1,…,yk≥0&yk+1,…,ym∈R
že pro alespoň jedno l∈{1,…,m} je yl=0 a pro všechna x∈X platí
i=1∑myifi(x)≥0(2.3.9)
nebo
Následující věta udává podmínky, které zajišťují kladnost jistého význačného yi (BÚNO i=0) ve vztahu (2.3.9). Po vydělení vztahu (2.3.9) tímto yi dostaneme BÚNO yi=1.
Věta 2.3.13 (Podmínky regularity)
Nechť množina X⊆Rn je konvexní a funkce f0,…,fm:X→R jsou konvexní. Jestliže systém nerovností
f0(x)<0,(2.3.10)
fi(x)<0,i∈{1,…,m}(2.3.11)
nemá řešení na X a podsystém (2.3.11) má řešení na X, pak existují y1,…,ym≥0 taková, že pro všechna x∈X platí
f0(x)+i=1∑myifi(x)≥0(2.3.12)