Predavanje 26.4.
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)$
- $\exists x \ge 0: \ Ax \le b \ \Longleftrightarrow \ \forall y \ge 0: \ (A^\top y \ge 0 \Rightarrow b^\top y \ge 0)$
- $\exists x: \ Ax = b \ \Longleftrightarrow \ \forall y: \ (A^\top y = 0 \Rightarrow b^\top y \ge 0)$
- $\exists x: \ Ax \le b \ \Longleftrightarrow \ \forall y \ge 0: \ (A^\top y = 0 \Rightarrow b^\top y \ge 0)$
Dokaz. Obravnavamo linearna programa:
$\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}$$ $\Pi$: $\Pi'$: $$\begin{aligned} \max \ 0^\top x \\[1ex] \text{p.p.} \quad A x &\le b \\ x &\ge 0 \end{aligned}$$ $$\begin{aligned} \min \ b^\top y \\[1ex] \text{p.p.} \quad A^\top y &\ge 0 \\ y &\ge 0 \end{aligned}$$ $\Pi$: $\Pi'$: $$\begin{aligned} \max \ 0^\top x \\[1ex] \text{p.p.} \quad A x &= b \end{aligned}$$ $$\begin{aligned} \min \ b^\top y \\[1ex] \text{p.p.} \quad A^\top y &= 0 \end{aligned}$$ $\Pi$: $\Pi'$: $$\begin{aligned} \max \ 0^\top x \\[1ex] \text{p.p.} \quad A x &\le b \\ \phantom{} \end{aligned}$$ $$\begin{aligned} \min \ b^\top y \\[1ex] \text{p.p.} \quad A^\top y &= 0 \\ y &\ge 0 \end{aligned}$$
V vseh primerih ekvivalenco dokažemo tako:
- ($\Longrightarrow$) Sledi iz šibkega izreka o dualnosti.
- ($\Longleftarrow$) Dualni linearni program $\Pi'$ ima dopustno rešitev $y = 0$, po predpostavki pa je to tudi optimalna rešitev. Po krepkem izreku o dualnosti je tudi $\Pi$ optimalen, torej ima dopustno rešitev.
Primera.
Pokažimo, da linearni program nima dopustne rešitve. $$ \begin{aligned} x_1 - x_2 &\le -1 & / \cdot 1 \\ -x_1 - x_2 &\le -3 & / \cdot 3 \\ 2 x_1 + x_2 &\le 2 & / \cdot 4 \\ x_1, x_2 &\ge 0 \\ \hline 6 x_1 &\le -2 \end{aligned} $$
$$ A = \begin{bmatrix} 1 & -1 \\ -1 & -1 \\ 2 & 1 \end{bmatrix}, \quad b = \begin{bmatrix} -1 \\ -3 \\ 2 \end{bmatrix}, \quad y = \begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix} \ge 0 \\ A^\top y = \begin{bmatrix} 6 \\ 0 \end{bmatrix} \ge 0, \quad b^\top y = -2 < 0 $$
Enakovredna izjava: $\exists x: \ Ax = b \ \Longleftrightarrow \ \forall y: \ (A^\top y = 0 \Rightarrow b^\top y = 0)$.
Pri linearni algebri $\lnot \exists x: \ Ax = b$ dokazujemo z Gaussovo eliminacijo.
$$ \begin{aligned} x_1 - 2 x_2 &= 3 & / \cdot 1 \\ -x_1 + 2 x_2 &= 1 & / \cdot 1 \\ \hline 0 &= 4 \end{aligned} $$
$$ A = \begin{bmatrix} 1 & -2 \\ -1 & 2 \end{bmatrix}, \quad b = \begin{bmatrix} 3 \\ 1 \end{bmatrix}, \quad y = \begin{bmatrix} 1 \\ 1 \end{bmatrix} \ge 0 \\ A^\top y = \begin{bmatrix} 0 \\ 0 \end{bmatrix}, \quad b^\top y = 4 $$
Opomba. Ekvivalentna trditev Farkasevi lemi: $$ b \not\in S(a_1, a_2, \dots, a_n) \Longleftrightarrow b \not\in S^{\ast\ast}(a_1, a_2, \dots, a_n). $$ Torej ($\Longrightarrow$): če $b$ ni v konveksnem stožcu, napetem na $a_1, a_2, \dots, a_n$, potem $b$ ne tvori ostrega kota z $y \in S^\ast(a_1, a_2, \dots, a_n)$ - med $b$ in $S(a_1, a_2, \dots, a_n)$ je tako neka hiperravnina.
Konveksne funkcije
Konveksne funkcije so "obrnjene navzgor", npr $f(x) = x^2$.
Definicija. Naj bo $K \subseteq \mathbb{R}^n$ konveksna množica. Funkcija $f : K \to \mathbb{R}$ je konveksna, če velja $$ \forall x, y \in K \ \forall \lambda \in [0, 1]: f((1 - \lambda) x + \lambda y) \le (1 - \lambda) f(x) + \lambda f(y) $$ Torej: graf funkcije leži pod zveznicami točk na grafu.
Funkcija $f : K \to \mathbb{R}$ je konkavna, če velja $$ \forall x, y \in K \ \forall \lambda \in [0, 1]: f((1 - \lambda) x + \lambda y) \ge (1 - \lambda) f(x) + \lambda f(y) $$ Torej: $f$ je konkavna $\Longleftrightarrow$ $-f$ je konveksna.
Funkcija $f : K \to \mathbb{R}$ je strogo konveksna, če velja $$ \forall x, y \in K \ \forall \lambda \in (0, 1): f((1 - \lambda) x + \lambda y) < (1 - \lambda) f(x) + \lambda f(y) $$
Funkcija $f : K \to \mathbb{R}$ je strogo konkavna, če velja $$ \forall x, y \in K \ \forall \lambda \in (0, 1): f((1 - \lambda) x + \lambda y) > (1 - \lambda) f(x) + \lambda f(y) $$
Primeri.
Množica $K \subseteq \mathbb{R}$ je konveksna natanko tedaj, ko je množica $K$ interval. Trdimo: $f(x) = x^2$ je konveksna funkcija (za vsak interval $K$). $$ f((1 - \lambda) x + \lambda y) \stackrel{?}{\le} (1 - \lambda) f(x) + \lambda f(y) \\[2ex] \begin{aligned} & ((1 - \lambda) x + \lambda y)^2 - ((1 - \lambda) x^2 + \lambda y^2) \\ &= (1 - \lambda)^2 x^2 + 2(1 - \lambda) \lambda xy + \lambda^2 y^2 - (1 - \lambda) x^2 - \lambda y^2 \\ &= (1 - \lambda)(1 - \lambda - 1) x^2 + 2(1 - \lambda) \lambda xy + \lambda (\lambda - 1) y^2 \\ &= -\lambda(1 - \lambda) (x^2 - 2xy + y^2) = -\lambda(1 - \lambda) (x - y)^2 \le 0 \end{aligned} $$
Afina funkcija $f(x_1, x_2, \dots, x_n) = a_1 x_1 + a_2 x_2 + \dots + a_n x_n + b$ (ali $f(x) = a^\top x + b$) je konveksna: $$ \begin{aligned} f((1 - \lambda) x + \lambda y) &= a^\top ((1 - \lambda) x + \lambda y) + b \\ &= (1 - \lambda) a^\top x + \lambda a^\top y + (1 - \lambda) b + \lambda b \\ &= (1 - \lambda) f(x) + \lambda f(y) \end{aligned} $$ Funkcija $f$ je tudi konkavna. Da se dokazati, da je funkcija konveksna in konkavna natanko tedaj, ko je afina.
Norma $\Vert \cdot \Vert : \mathbb{R}^n \to \mathbb{R}$ (npr. dolžina vektorja $\Vert x \Vert = \sqrt{x^\top x} = \sqrt{x_1^2 + x_2^2 + \dots + x_n^2}$) je funkcija s sledečimi lastnostmi:
- $\Vert x \Vert \ge 0$, $\Vert x \Vert = 0 \Rightarrow x = 0$
- $\Vert \lambda x \Vert = \vert \lambda \vert \Vert x \Vert$
- $\Vert x + y \Vert \le \Vert x \Vert + \Vert y \Vert$ (trikotniška neenakost)
Norma je konveksna: $$ \Vert (1 - \lambda) x + \lambda y \Vert \le \Vert (1 - \lambda) x \Vert + \Vert \lambda y \Vert = (1 - \lambda) \Vert x \Vert + \lambda \Vert y \Vert $$
Trditev. Naj bo $K \subseteq \mathbb{R}^n$ konveksna množica ter $f, g: K \to \mathbb{R}$ konveksni funkciji. Potem velja sledeče.
- Če $c \ge 0$, potem je $c \cdot f$ konveksna funkcija.
- Funkcija $f + g$ je konveksna.
- Če je funkcija $f$ afina, je slika $f(K)$ konveksna množica.
Dokaz.
- $(c \cdot f)((1 - \lambda) x + \lambda y) \le c ((1 - \lambda) f(x) + \lambda f(y)) = ((1 - \lambda) (c \cdot f)(x) + \lambda (c \cdot f)(y))$
- $$ \begin{aligned} (f + g)((1 - \lambda) x + \lambda y) &= f((1 - \lambda) x + \lambda y) + g((1 - \lambda) x + \lambda y) \\ &\le (1 - \lambda) f(x) + \lambda f(y) + (1 - \lambda) g(x) + \lambda g(y) \\ &= (1 - \lambda) (f + g)(x) + \lambda (f + g)(y) \end{aligned} $$
- Funkcija $f(x) = a^\top x + b$ je konveksna in konkavna, za $x, y \in K$ velja $f(x), f(y) \in f(K)$. Ker je $(1 - \lambda) x + \lambda y \in K$, velja $$ (1 - \lambda) f(x) + \lambda f(y) = f((1 - \lambda) x + \lambda y) \in f(K). $$