Predavanje 25.4.
Definicija. Naj bo $A$ konveksna množica. Točka $a \in A$ je ekstremna točka, če velja $\forall x, y \in A \ \forall \lambda \in (0, 1): (a = (1 - \lambda) x + \lambda y) \Rightarrow x = y = a$ (tj., $a$ ne leži v notranjosti nobene daljice med različnima točkama iz $A$).
Primeri. Ekstremne točke so prikazane z rdečo barvo.
V zadnjem primeru ni ekstremnih točk.
Definicija. Množica $A \ne \emptyset$ je afina, če velja $\forall x, y \in A \ \forall \lambda \in \mathbb{R}: (1 - \lambda) x + \lambda y \in A$ (tj., vsaka premica med različnima točkama iz $A$ je vsebovana v $A$).
Definicija. Vektor $\lambda_1 x_1 + \lambda_2 x_2 + \dots + \lambda_n x_n$, kjer je $\lambda_1 + \lambda_2 + \dots + \lambda_n = 1$, je afina kombinacija vektorjev $x_1, x_2, \dots, x_n$.
Trditev. Naj bo $A \subseteq \mathbb{R}^m$ neprazna množica. Sledeče trditve so ekvivalentne.
- Množica $A$ je afina.
- Vsaka afina kombinacija točk iz $A$ je v $A$.
- $\exists v \in \mathbb{R}^m$, $\exists V \le \mathbb{R}^m$ linearen podprostor: $A = v + V = \{v + x \mid x \in V\}$.
Opomba. Primeri afinih množic so premica v $\mathbb{R}^m$, ravnina v $\mathbb{R}^m$, ... - rečemo jim tudi afini podprostori. Definiramo lahko tudi dimenzijo afinega podprostora.
Dokaz.
(1. $\Rightarrow$ 2.) Naj bo $x = \lambda_1 x_1 + \lambda_2 x_2 + \dots + \lambda_n x_n$ afina kombinacija vektorjev $x_1, x_2, \dots, x_n \in A$. Naredimo indukcijo na $n$.
- $n = 1$: $x = 1 \cdot x_1 = x_1 \in A$.
- $n = 2$: po definiciji.
- $n > 2$: brez škode za splošnost vzamemo $\lambda_n \ne 1$ - tedaj naj bo $$ y := {\lambda_1 x_1 + \lambda_2 x_2 + \dots + \lambda_{n-1} x_{n-1} \over 1 - \lambda_n} . $$ Ker je ${\lambda_1 \over 1 - \lambda_n} + {\lambda_2 \over 1 - \lambda_n} + \dots + {\lambda_{n-1} \over 1 - \lambda_n} = 1$, je $y$ afina kombinacija vektorjev $x_1, x_2, \dots, x_{n-1} \in A$. Po indukcijski predpostavki je $y \in A$, torej je tudi $x = (1 - \lambda_n) y + \lambda_n x_n \in A$.
(2. $\Rightarrow$ 3.) Naj bo $v \in A$ poljuben vektor. Potem je $V := A - v$ linearen podprostor, saj za vsake $x, y \in A$ ter $\mu, \nu \in \mathbb{R}$ velja $$ \begin{aligned} \mu (x - v) + \nu (y - v) &= \mu x + \nu y - \mu v - \nu v \\ &= \mu x + \nu y + (1 - \mu - \nu) v - v \in V, \end{aligned} $$ saj $x, y, v \in A$ ter $\mu + \nu + (1 - \mu - \nu) = 1$. Velja torej $A = V + v$.
(3. $\Rightarrow$ 1.) Poljubna vektorja iz $A$ lahko zapišemo kot $x+v$ in $y+v$, kjer $x, y \in V$. Za poljuben $\lambda \in \mathbb{R}$ velja $$ (1 - \lambda) (x + v) + \lambda (y + v) = (1 - \lambda) x + \lambda y + v \in A. $$
Konveksni stožci in Farkaseva lema
Definicija. Množica $A \subseteq \mathbb{R}^m$ je konveksen stožec, če velja $\forall x, y \in A \ \forall \lambda, \mu \ge 0: \lambda x + \mu y \in A$.
Opomba. Če za vsaka $x, y \in A$ velja
- $\forall \lambda, \mu: \lambda x + \mu y \in A$, potem je $A$ linearen podprostor;
- $\forall \lambda, \mu \ge 0: \lambda x + \mu y \in A$, potem je $A$ konveksen stožec;
- $\forall \lambda, \mu: (\lambda + \mu = 1 \Rightarrow \lambda x + \mu y \in A)$, potem je množica $A$ afina; in
- $\forall \lambda, \mu \ge 0: (\lambda + \mu = 1 \Rightarrow \lambda x + \mu y \in A)$, potem je množica $A$ konveksna.
Vsak konveksen stožec je konveksna množica; obratno ne velja.
Definicija. Množica $$ S(a_1, a_2, \dots, a_n) := \{\lambda_1 a_1 + \lambda_2 a_2 + \dots \lambda_n a_n \mid \lambda_1, \lambda_2, \dots, \lambda_n \ge 0\} $$ je konveksen stožec, napet na vektorjih $a_1, a_2, \dots, a_n$.
Trditev. Množica $S(a_1, a_2, \dots, a_n)$ je konveksen stožec.
Dokaz. Naj bodo $\lambda, \lambda_1, \dots, \lambda_n, \mu, \mu_1, \dots, \mu_n \ge 0$. Potem velja $$ \lambda (\lambda_1 a_1 + \dots + \lambda_n a_n) + \mu (\mu_1 a_1 + \dots + \mu_n a_n) = (\lambda \lambda_1 + \mu \mu_1) a_1 + \dots + (\lambda \lambda_n + \mu \mu_n) a_n \in S(a_1, \dots, a_n), $$ saj $\lambda \lambda_i + \mu \mu_i \ge 0$ ($1 \le i \le n$).
Primeri.
$S(a_1)$:
$S(a_1, a_2)$:
$S(a_1, a_2, a_3)$:
Definicija. Naj bo $A \subseteq \mathbb{R}^m$. Množici $$ A^\ast := \{x \in \mathbb{R}^m \mid \forall a \in A: a^\top x \ge 0\} $$ (tj., množici vektorjev, ki tvorijo ostri kot z vsemi vektorji iz $A$) pravimo dualni stožec množice $A$.
Trditev. Dualni stožec $A^\ast$ množice $A$ je konveksen stožec.
Dokaz. Vzemimo poljubne $x, y \in A^\ast$ in $\lambda, \mu \ge 0$. Potem za vsak $a \in A$ velja $$ a^\top (\lambda x + \mu y) = \lambda \, a^\top x + \mu \, a^\top y \ge 0, $$ torej $\lambda x + \mu y \in A^\ast$.
Trditev. $A \subseteq A^{\ast\ast}$.
Opomba. V splošnem ne velja $A = A^{\ast\ast}$ (npr. če $A$ ni konveksen stožec).
Dokaz. Vzemimo poljuben $x \in A$. Potem za vsak $y \in A^\ast$ velja $x^\top y \ge 0$, torej velja tudi $x \in A^{\ast\ast}$.
Izrek (Farkaseva lema - geometrijska oblika). $S^{\ast\ast}(a_1, a_2, \dots, a_n) = S(a_1, a_2, \dots, a_n)$.
Dokaz.
- ($\supseteq$) Po prejšnji trditvi.
($\subseteq$) Naj bo $A = [a_1 \, a_2 \, \dots \, a_n]$ matrika s stolpci $a_1, a_2, \dots, a_n$ in $b \in S^{\ast\ast}(a_1, a_2, \dots, a_n)$. Definirajmo linearni program $\Pi$ in njegov dual $\Pi'$:
$\Pi$: $\Pi'$: $$\begin{aligned} \max \ 0^\top x \\[1ex] \text{p.p.} \quad A x &= b \\ x &\ge 0 \end{aligned}$$ $$\begin{aligned} \min \ b^\top y \\[1ex] \text{p.p.} \quad A^\top y &\ge 0 \\ \phantom{} \end{aligned}$$ Ker je $y = 0$ dopustna rešitev $\Pi'$, je ta dopusten; pokazali bomo, da je tudi omejen. Naj bo $y$ dopustna rešitev za $\Pi'$, torej velja $A^\top y \ge 0$ oziroma $$ \forall i \in \{1, 2, \dots, n\}: \ a_i^\top y \ge 0. $$ Potem za poljubne $\lambda_1, \lambda_2, \dots, \lambda_n \ge 0$ velja $$ (\lambda_1 a_1 + \lambda_2 a_2 + \dots + \lambda_n a_n)^\top y = \lambda_1 \, a_1^\top y + \lambda_2 \, a_2^\top y + \dots + \lambda_n \, a_n^\top y \ge 0 $$ Vektor $y$ torej tvori ostri kot z vsemi vektorji iz $S(a_1, a_2, \dots, a_n)$ in zato $y \in S^\ast(a_1, a_2, \dots, a_n)$. Ker velja $b \in S^{\ast\ast}(a_1, a_2, \dots, a_n)$, sledi $b^\top y \ge 0$, torej je $\Pi'$ omejen in zato optimalen. Po krepkem izreku o dualnosti je tudi $\Pi$ optimalen, torej $\exists x \ge 0: Ax = b$ oziroma $$ \exists x_1, x_2, \dots, x_n \ge 0: \ x_1 a_1 + x_2 a_2 + \dots + x_n a_n = b, $$ iz česar sledi $b \in S(a_1, a_2, \dots, a_n)$.
Opomba. Farkasevo lemo se da dokazati tudi neposredno, krepki izrek o dualnosti sledi iz nje. Imamo torej ekvivalenco Farkas $\Leftrightarrow$ KID.
Farkaseva lema - algebraična oblika. $$ \exists x \ge 0: \ Ax = b \ \Longleftrightarrow \ \forall y: \ (A^\top y \ge 0 \Rightarrow b^\top y \ge 0) $$
Dokaz. Naj bodo $a_1, a_2, \dots, a_n$ stolpci matrike $A$. Potem je izjava ekvivalentna izjavi $b \in S(a_1, a_2, \dots, a_n) \Longleftrightarrow b \in S^{\ast\ast}(a_1, a_2, \dots, a_n)$, ki sledi iz geometrijske oblike Farkaseve leme.
Primer. Ali obstaja nenegativna rešitev sistema linearnih enačb $Ax = b$? Če obstaja, jo zapišemo. Če ne obstaja, poiščemo $y$, da velja $A^\top y \ge 0$, $b^\top y < 0$.
$$ \begin{aligned} x_1 - x_2 + 2 x_3 &= 1 & / \cdot 1 \\ -x_1 - x_2 + x_3 &= 2 & / \cdot (-1) \\ \hline 2 x_1 + x_3 &= -1 \end{aligned} $$
Dokažimo, da zgornji sistem nima nenegativnih rešitev. $$ A = \begin{bmatrix} 1 & -1 & 2 \\ -1 & -1 & 1 \end{bmatrix}, \quad b = \begin{bmatrix} 1 \\ 2 \end{bmatrix}, \quad y = \begin{bmatrix} 1 \\ -1 \end{bmatrix} \\ A^\top y = \begin{bmatrix} 1 & -1 \\ -1 & -1 \\ 2 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ -1 \end{bmatrix} = \begin{bmatrix} 2 \\ 0 \\ 1 \end{bmatrix} \ge 0, \quad b^\top y = -1 < 0 $$
Ustrezen $x$ oziroma $y$ lahko poiščemo s simpleksno metodo.