Első házifeladat

Toffalini Leonardo 2023.09.20.

1.15 Bizonyítsuk be, hogy minden politóp zárt.

(politóp: véges sok pont konvex burka)

Egyel erősebb állítást fogunk belátni, be fogjuk látni hogy minden politóp kompakt.

Elég találni egy kompakt halmazt és egy folytonos függvényt, ami a kompakt halmazból egy politópot képez, mivel tudjuk, hogy kompakt halmaz folytonos képe is kompakt.

Legyen $H$ a véges sok pontot tartalmazó halmaz, ekkor jelölje $conv(H)$ a politópot.
$conv(H)=\{{\sum }_{i=1}^n{\alpha }_i{x}_i:\forall i:{\alpha }_i\ge 1,{\sum }_{i=1}^n{\alpha }_i=1\}$
Legyen $S=\{\alpha \in {\mathbb{R}}^n:\forall i:{\alpha }_i\ge 1,{\sum }_{i=1}^n{\alpha }_i=1\}$.

$S=\{\alpha \in {\mathbb{R}}^n:\forall i:{\alpha }_i\ge 1\}\cup \{\alpha \in {\mathbb{R}}^n:{\sum }_{i=1}^n{\alpha }_i=1\}$

Látható, hogy $S$ két kompakt halmaz metszete, tehát maga $S$ is kompakt.
Most találnunk kell egy $g:S\to {\mathbb{R}}^n$ függvényt ami folytonos és képe a politóp.
$g(\alpha )={\sum }_{i=1}^n{\alpha }_i{x}_i$
Ez a függvény folytonos és az $S$ halmazt képzi a $conv(H)$ halmazba.

Ezzel beláttuk az állítást, mivel találtunk egy folytonos függvényt ami egy kompakt halmazt képez a politópba, tehát a politóp is kompakt.

1.12 Lássuk be a következőt

Adott az $Ax\le b,x\ge 0$ egyenlőtlenség rendszer egy $x_0$ megoldása. Bizonyítsuk be, hogy ha az $x_0$ vektor nem nulla (azaz pozitív) komponenseihez tartozó $A$-beli oszlopok összefüggenek, akkor olyan megoldás is van, melynek kevesebb a nem nulla komponense.

$A=[a_1,\dots ,a_k],x_0=[x_1,\dots ,x_k{]}^T$
Ezekre tudjuk, hogy $A{x}_0\le b$ .
Legyen: $A^{\prime }=\left[\frac{a_1}{{\beta }_1},\dots ,\frac{a_k}{{\beta }_k}\right],x_0^{\prime }=\left[{\beta }_1{x}_1,\dots ,{\beta }_k{x}_k\right]$ úgy, hogy $\forall i:{\beta }_i{x}_i\ge 1$, ha $x_i\ne 0$.
Úgy módosítottuk, hogy megmaradjon $A{x}_0$ értéke, mivel $A{x}_0=A^{\prime }{x}_0^{\prime }$.

$A{x}_0=A^{\prime }{x}_0^{\prime }={\sum }_{i=1}^k{x}_i{a}_i={\sum }_{i\in I}{x}_i{a}_i\le b$
$I=\left\{i\in \{1,\dots ,k\}:x_i\ne 0\right\}=\{i_1,\dots ,i_l\}$
Tudjuk, hogy $\{a_i:i\in I\}$ összefüggő, tehát $\exists {\alpha }_1,\dots ,{\alpha }_l\in \mathbb{R}$ úgy, hogy ${\sum }_{i\in I}{\alpha }_i{a}_i=0$.
Ekkor rendezve $a_m$-re: $a_m={\sum }_{i\in I,i\ne m}-\frac{{\alpha }_i}{{\alpha }_m}{a}_i$
$A^{\prime }{x}_0^{\prime }={\sum }_{i\in I}{x}_i{a}_i={\sum }_{i\in I,i\ne m}{x}_i{a}_i-{\sum }_{i\in I,i\ne m}\frac{{\alpha }_i}{{\alpha }_m}{a}_i{x}_m={\sum }_{i\in I}\left(x_i-x_m\frac{{\alpha }_i}{{\alpha }_m}\right)a_i=Ay$
Ahol $[y{]}_i:=\left(x_i-x_m\frac{{\alpha }_i}{{\alpha }_m}\right)$, tehát $y_m=0$. Ezért $y$-nak több nulla komponense van mint $x_0$-nak.

Már csak azt kell belátni, hogy $\forall i:y_i\ge 0$.
Válasszuk $m$-et úgy hogy ${\alpha }_m=ma{x}_{i\in I}{\alpha }_i$.
Mivel az elején átalakítottuk $x_0$ vektort $x_0^{\prime }$ vektorrá úgy, hogy minden koordinátája legalább $1$, így valóban $\forall i:y_i\ge 0$.