Optimizacijske metode

Trditev. Naj bo $K \subseteq \mathbb{R}^n$ konveksna množica ter $f: K \to \mathbb{R}$ konveksna funkcija in $g: \operatorname{conv}(f(K)) \to \mathbb{R}$ naraščajoča konveksna funkcija. Potem je kompozitum $g \circ f$ konveksna funkcija.

Dokaz. $$ \begin{aligned} f((1 - \lambda) x + \lambda y) &\le (1 - \lambda) f(x) + \lambda f(y) && \text{$f$ konveksna} \\ g(f((1 - \lambda) x + \lambda y)) &\le g((1 - \lambda) f(x) + \lambda f(y)) && \text{$g$ naraščajoča} \\ &\le (1 - \lambda) (g \circ f)(x) + \lambda (g \circ f)(y) && \text{$g$ konveksna} \end{aligned} $$

Neprimeri.

• Produkt konveksnih funkcij ni nujno konveksna funkcija: $f(x) = x$, $g(x) = -x$, $(f \cdot g)(x) = -x^2$.
• Kompozitum konveksnih funkcij ni nujno konveksna funkcija: $f(x) = x^2$, $g(x) = -x$, $(g \circ f)(x) = -x^2$.
• Slika konveksne množice s konveksno funkcijo ni nujno konveksna množica: $$ \begin{aligned} f:&\ [0, 1] \to \mathbb{R} \\ f(x) &= \begin{cases} 0 & \text{če } 0 \le x < 1 \\ 1 & \text{če } x = 1 \end{cases} \\ f([0, 1]) &= \{0, 1\} \end{aligned} $$

Konveksne funkcije in optimizacija

Definicija. Naj bo $A \subseteq \mathbb{R}^n$ in $f: A \to \mathbb{R}$. Funkcija $f$ ima v točki $x^\ast \in A$:

• globalni maksimum, če $\forall x \in A: f(x) \le f(x^\ast)$;
• globalni minimum, če $\forall x \in A: f(x) \ge f(x^\ast)$;
• lokalni maksimum, če $\exists \epsilon > 0 \ \forall x \in A: (\Vert x - x^\ast \Vert < \epsilon \Rightarrow f(x) \le f(x^\ast))$; in
• lokalni minimum, če $\exists \epsilon > 0 \ \forall x \in A: (\Vert x - x^\ast \Vert < \epsilon \Rightarrow f(x) \ge f(x^\ast))$.

Trditev. Naj bo $K \subseteq \mathbb{R}^n$ konveksna množica ter $f: K \to \mathbb{R}$ konveksna funkcija. Če ima $f$ v $x^\ast \in K$ lokalni minimum, ima v $x^\ast$ tudi globalni minimum.

Dokaz. Naj bo $\epsilon > 0$ tak, da velja $\forall x \in K: (\Vert x - x^\ast \Vert < \epsilon \Rightarrow f(x) \ge f(x^\ast))$. Če $x^\ast$ ni globalni minimum, potem obstaja tak $y \in K$, da velja $f(y) < f(x^\ast)$. Tedaj za vsak $\lambda \in (0, 1]$ velja $$ f((1 - \lambda) x^\ast + \lambda y) \le (1 - \lambda) f(x^\ast) + \lambda f(y) < (1 - \lambda) f(x^\ast) + \lambda f(x^\ast) = f(x^\ast) . $$ Za dovolj majhen $\lambda$ je $(1 - \lambda) x^\ast + \lambda y$ poljubno blizu $x^\ast$: $$ \Vert (1 - \lambda) x^\ast + \lambda y - x^\ast \Vert = \Vert \lambda (y - x^\ast) \Vert = \lambda \Vert y - x^\ast \Vert < \epsilon, \text{ če } \lambda < {\epsilon \over \Vert y - x^\ast \Vert} $$ Torej: če je $\lambda \in \left(0, {\epsilon \over \Vert y - x^\ast \Vert}\right)$, je $\Vert (1 - \lambda) x^\ast + \lambda y - x^\ast \Vert < \epsilon$ in tedaj $f((1 - \lambda) x^\ast + \lambda y) \ge f(x^\ast)$, protislovje.

Preverjanje konveksnosti po definiciji je v splošnem težko. Večinoma je lažje preverjati konveksnost z odvodi.

Naj bo $f: (a, b) \to \mathbb{R}$ konveksna funkcija. Njen graf potem leži nad vsako tangento (kriterij 1. odvoda), torej $f(y) \ge f(x) + (y-x) f'(x)$ za vsaka $x, y \in (a, b)$.

Primer. Naj bo $f(x) = x^2$. Preverimo, ali za vsaka $x, y \in \mathbb{R}$ velja $$ y^2 \stackrel{?}{\ge} x^2 + (y-x) \cdot 2x . $$ Res: $$ y^2 - x^2 - 2xy + 2x^2 = y^2 - 2xy + x^2 = (x-y)^2 \ge 0. $$

Smerni koeficienti tangent na graf konveksne funkcije $f$ naraščajo - njen odvod $f'$ je torej naraščajoča funkcija, torej $f''(x) \ge 0$ za vsak $x \in (a, b)$ (kriterij 2. odvoda).

Primer. Naj bo $f(x) = x^2$. Potem je $f''(x) = 2 \ge 0$.

Izrek (kriterij 1. odvoda). Naj bo $K \subseteq \mathbb{R}^n$ odprta konveksna množica, ter $f: K \to \mathbb{R}$ funkcija, ki ima vse parcialne odvode ${\partial f \over \partial x_i}$ ($1 \le i \le n$) - te zapišemo v gradient $\nabla f(x) = \left({\partial f \over \partial x_i}\right)_{i=1}^n$. Potem je funkcija $f$ konveksna natanko tedaj, ko za vsaka $x, y \in K$ velja $f(y) \ge f(x) + (\nabla f(x))^\top (y - x)$.

Dokaz.

• ($\Longleftarrow$) Naj bodo $x, y \in K$ in $\lambda \in [0, 1]$ poljubni ter pišimo $z := (1 - \lambda) x + \lambda y$. Potem velja: $$ \begin{aligned} f(x) &\ge f(z) + (\nabla f(z))^\top (x - z) &&/ \cdot (1 - \lambda) \\ f(y) &\ge f(z) + (\nabla f(z))^\top (y - z) &&/ \cdot \lambda \\ \hline (1 - \lambda) f(x) + \lambda f(y) &\ge f(z) + (\nabla f(z))^\top ((1 - \lambda) x + \lambda y - z) \\ &= f((1 - \lambda) x + \lambda y) \end{aligned} $$ Funkcija $f$ je torej konveksna.

• ($\Longrightarrow$) Za fiksna $x, y \in K$ je $g_{x, y}(\lambda) = f((1 - \lambda) x + \lambda y)$ funkcija v $\lambda$ - zanima nas njen odvod pri $\lambda = 0$. Funkcija $g_{x, y}$ je definirana na $(-\epsilon, 1]$ za nek $\epsilon > 0$: $$ \Vert (1 - \lambda) x + \lambda y - x \Vert = \Vert \lambda y - \lambda x \Vert = |\lambda| \Vert y - x \Vert < \delta, $$ kjer je množica $K(x, \delta) = \{y \in \mathbb{R}^n \mid \Vert x - y \Vert \le \delta\}$ (tj., krogla s središčem v $x$ in polmerom $\delta$) vsebovana v $K$. Imamo torej $\epsilon := {\delta \over \Vert y - x \Vert}$. Izračunajmo $g'_{x, y}(\lambda)$. $$ \begin{aligned} g'_{x, y}(\lambda) &= {d \over d \lambda} f((1 - \lambda) x + \lambda y) \\ &= {d \over d \lambda} f((1 - \lambda) x_1 + \lambda y_1, \dots, (1 - \lambda) x_n + \lambda y_n) \\ &= {\partial f \over \partial x_1}((1 - \lambda) x + \lambda y) \cdot (y_1 - x_1) + \dots + {\partial f \over \partial x_n}((1 - \lambda) x + \lambda y) \cdot (y_n - x_n) \\ &= (\nabla f((1 - \lambda) x + \lambda y))^\top (y - x) \end{aligned} $$ Velja torej $g'_{x, y}(0) = (\nabla f(x))^\top (y - x)$. Po definiciji odvoda nadalje velja $$ \begin{aligned} g'_{x, y}(0) &= \lim_{\lambda \to 0} {g_{x, y}(\lambda) - g_{x, y}(0) \over \lambda} \\ &= \lim_{\lambda \to 0} {f((1 - \lambda) x + \lambda y) - f(x) \over \lambda} \\ &= \lim_{\lambda \searrow 0} {f((1 - \lambda) x + \lambda y) - f(x) \over \lambda} \\ &\le \lim_{\lambda \searrow 0} {(1 - \lambda) f(x) + \lambda f(y) - f(x) \over \lambda} & \text{(ker $\lambda > 0$)} \\ &= f(y) - f(x). \end{aligned} $$ Velja torej $f(y) \ge f(x) + (\nabla f(x))^\top (y - x)$.

Izrek (kriterij 2. odvoda za funkcije ene spremenljivke). Naj bo $f: (a, b) \to \mathbb{R}$ dvakrat odvedljiva funkcija. Potem je funkcija $f$ konveksna natanko tedaj, ko za vsak $x \in (a, b)$ velja $f''(x) \ge 0$.

Dokaz (prvi del).

• ($\Longrightarrow$) Naj bo $x \in (a, b)$ in $h > 0$ tak, da $x \pm h \in (a, b)$. Zaradi konveksnosti funkcije $f$ potem velja: $$ f(x) = f\left({1 \over 2} (x + h) + {1 \over 2} (x - h)\right) \le {1 \over 2} f(x + h) + {1 \over 2} f(x - h) $$ Z dvakratno uporabo L'Hôpitalovega pravila potem izpeljemo $$ 0 \le \lim_{h \to 0} {f(x + h) + f(x - h) - 2f(x) \over h^2} = \lim_{h \to 0} {f'(x + h) - f'(x - h) \over 2h} = \lim_{h \to 0} {f''(x + h) + f''(x - h) \over 2} = f''(x). $$