Optimizacijske metode

Trditev.

• $A \ge 0 \Longleftrightarrow \forall x \in \mathbb{R}^n: \ x^\top A x \ge 0$,
• $A >0 \Longleftrightarrow \forall x \in \mathbb{R}^n \setminus \{0\}: \ x^\top A x > 0$,
• $A \le 0 \Longleftrightarrow \forall x \in \mathbb{R}^n: \ x^\top A x \le 0$,
• $A < 0 \Longleftrightarrow \forall x \in \mathbb{R}^n \setminus \{0\}: \ x^\top A x < 0$,
• $A$ je nedefinitna natanko tedaj, ko $x^\top A x$ doseže tako pozitivne kot negativne vrednosti.

Dokaz. Vzemimo $x \in \mathbb{R}^n$ in diagonalizirajmo $A = UDU^\top$. Če je $x = 0$, potem je $x^\top A x = 0$. Sicer pišimo $\tilde{x} = U^\top x$, posledično velja tudi $x = U \tilde{x}$. Potem velja $$ x^\top A x = x^\top UDU^\top x = \tilde{x}^\top D \tilde{x} = \sum_{i=1}^n \lambda_i \tilde{x}_i^2. $$ Matrika $A$ ima tako vse lastne vrednosti nenegativne/pozitivne/nepozitivne/negativne natanko tedaj, ko je za vsak $x \in \mathbb{R}^n \setminus \{0\}$ zgornja vrednost $\ge/>/\le/< 0$.

Primer. Naj bo $A$ simetrična matrika dimenzij $2 \times 2$: $$ A = \begin{bmatrix} a & b \\ b & c \end{bmatrix} $$ Potem velja: $$ \begin{alignedat}{8} A \ge 0 \quad &\Leftrightarrow &\quad \lambda_1, \lambda_2 &\ge 0 \quad \Leftrightarrow &\quad \lambda_1 + \lambda_2 &\ge 0 &\quad &\Leftrightarrow &\quad \operatorname{tr} A &=&\ a + c &\ge 0 \\ &&&& \lambda_1 \lambda_2 &\ge 0 &&& \det A &=&\ ac - b^2 &\ge 0 \\[2ex] A > 0 \quad &\Leftrightarrow &\quad \lambda_1, \lambda_2 &> 0 \quad \Leftrightarrow &\quad \lambda_1 + \lambda_2 &> 0 &\quad &\Leftrightarrow &&&\ a + c &> 0 &\quad &\Leftrightarrow & a &> 0 \\ &&&& \lambda_1 \lambda_2 &> 0 &&&&& ac - b^2 &> 0 &&& ac - b^2 &> 0 \\[2ex] A \le 0 \quad &\Leftrightarrow &\quad \lambda_1, \lambda_2 &\le 0 \quad \Leftrightarrow &\quad \lambda_1 + \lambda_2 &\le 0 &\quad &\Leftrightarrow &&&\ a + c &\le 0 \\ &&&& \lambda_1 \lambda_2 &\ge 0 &&&&& ac - b^2 &\ge 0 \\[2ex] A < 0 \quad &\Leftrightarrow &\quad \lambda_1, \lambda_2 &< 0 \quad \Leftrightarrow &\quad \lambda_1 + \lambda_2 &< 0 &\quad &\Leftrightarrow &&&\ a + c &< 0 &\quad &\Leftrightarrow & a &< 0 \\ &&&& \lambda_1 \lambda_2 &> 0 &&&&& ac - b^2 &> 0 &&& ac - b^2 &> 0 \\[2ex] A \text{ nedefinitna} \quad &\Leftrightarrow &\quad \lambda_1 &> 0 \quad \Leftrightarrow &\quad \lambda_1 \lambda_2 &< 0 &\quad &\Leftrightarrow &&& ac - b^2 &< 0 \\ && \lambda_2 &< 0 \end{alignedat} $$

Definicija. Glavne poddeterminante matrike $A = (a_{ij})_{i,j=1}^n \in \mathbb{R}^{n \times n}$ so vrednosti $\det (a_{ij})_{i,j=1}^\ell$ ($1 \le \ell \le n$).

Trditev. Naj bo $A \in \mathbb{R}^{n \times n}$ simetrična matrika. Potem velja:

• $A > 0$ natanko tedaj, ko so vse glavne poddeterminante pozitivne.
• $A < 0$ natanko tedaj, ko glavne poddeterminante alternirajo med negativnimi in pozitivnimi vrednostmi.

Definicija. Naj bo $\Omega \subseteq \mathbb{R}^n$ odprta množica in $f: \Omega \to \mathbb{R}$ funkcija, za katero obstajajo vsi drugi parcialni odvodi ${\partial^2 f \over \partial x_j \partial x_i}$ ($1 \le i, j \le n$). Hessejeva matrika funkcije $f$ je $H_f(x) = \left({\partial^2 f \over \partial x_j \partial x_i}(x)\right)_{i,j=1}^n$.

Če so vsi drugi parcialni odvodi zvezni ($f \in \mathcal{C}^2(\Omega)$), velja $\forall i, j: {\partial^2 f \over \partial x_j \partial x_i} = {\partial^2 f \over \partial x_i \partial x_j}$, torej je $H_f(x)$ simetrična.

Izrek (kriterij 2. odvoda). Naj bo $K \subseteq \mathbb{R}^n$ odprta konveksna množica, ter $f: K \to \mathbb{R}$ funkcija iz $\mathcal{C}^2(K)$. Potem je funkcija $f$ konveksna natanko tedaj, ko za vsak $x \in K$ velja $H_f(x) \ge 0$.

Dokaz. Trdimo, da je funkcija $f$ konveksna natanko tedaj, ko za vsaka $x, y \in K$ obstaja tak $\epsilon$, da je funkcija $h_{x,y}: (-\epsilon, 1+\epsilon) \to \mathbb{R}$, $h_{x,y}(t) = f((1 - t) x + ty)$ konveksna in $h_{x,y} \in \mathcal{C}^2(-\epsilon, 1+\epsilon)$. Dokažimo najprej to trditev.

• ($\Longrightarrow$) Ker je množica $K$ odprta, obstaja tak $\epsilon$, da je funkcija z zgornjim predpisom dobro definirana. Ker velja $f \in \mathcal{C}^2(K)$, velja tudi $h_{x,y} \in \mathcal{C}^2(-\epsilon, 1+\epsilon)$. Dokažimo še, da je $h_{x,y}$ konveksna funkcija. Vzemimo torej poljubne $s, t \in (-\epsilon, 1+\epsilon)$ in $\lambda \in [0, 1]$. Ker je $f$ konveksna, velja: $$ \begin{aligned} f((1 - \lambda)((1 - t) x + ty) + \lambda ((1 - s) x + sy)) &\le (1 - \lambda) f((1 - t) x + ty) + \lambda f((1 - s) x + sy) \\ f((1 - (1 - \lambda) t - \lambda s) x + ((1 - \lambda) t + \lambda s) y) &\le (1 - \lambda) f((1 - t) x + ty) + \lambda f((1 - s) x + sy) \\ h_{x,y}((1 - \lambda) t + \lambda s) &\le (1 - \lambda) h_{x,y}(t) + \lambda h_{x,y}(s) \end{aligned} $$

• ($\Longleftarrow$) Ker je za vsaka $x, y \in K$ funkcija $h_{x,y}$ konveksna, za vsak $\lambda \in [0, 1]$ velja: $$ \begin{aligned} h_{x,y}(\lambda) = h_{x,y}((1 - \lambda) \cdot 0 + \lambda \cdot 1) &\le (1 - \lambda) h_{x,y}(0) + \lambda h_{x,y}(1) \\ f((1 - \lambda) x + \lambda y) &\le (1 - \lambda) f(x) + \lambda f(y) \end{aligned} $$ Funkcija $f$ je torej konveksna.

Za poljubna $x, y \in K$ lahko torej zapišemo: $$ \begin{aligned} h_{x,y}(t) &= f((1 - t) x + ty) \\ &= f((1 - t) x_1 + ty_1, \dots, (1 - t) x_n + ty_n) \\[2ex] h'_{x,y}(t) &= {\partial f \over \partial x_1}((1 - t) x + ty) \cdot (y_1 - x_1) + \dots + {\partial f \over \partial x_n}((1 - t) x + ty) \cdot (y_n - x_n) \\ &= (\nabla f((1 - t) x + ty))^\top (y - x) \\[2ex] h''_{x,y}(t) &= {\partial^2 f \over \partial x_1 \partial x_1}((1 - t) x + ty) \cdot (y_1 - x_1)(y_1 - x_1) + \dots + {\partial^2 f \over \partial x_n \partial x_1}((1 - t) x + ty) \cdot (y_n - x_n)(y_1 - x_1) \\ &+ \dots \\ &+ {\partial^2 f \over \partial x_1 \partial x_n}((1 - t) x + ty) \cdot (y_1 - x_1)(y_n - x_n) + \dots + {\partial^2 f \over \partial x_n \partial x_n}((1 - t) x + ty) \cdot (y_n - x_n)(y_n - x_n) \\ &= \sum_{i=1}^n \sum_{j=1}^n {\partial^2 f \over \partial x_j \partial x_i}((1 - t) x + ty) \cdot (y_j - x_j)(y_i - x_i) \\ &= (y - x)^\top H_f((1 - t) x + ty) (y - x) \end{aligned} $$ Velja torej: $$ \forall x, y \in K \ \forall t \in [0, 1]: h''_{x,y}(t) \ge 0 \iff \forall x, y \in K \ \forall t \in [0, 1]: H_f((1 - t) x + ty) \ge 0 \iff \forall x \in K: H_f(x) \ge 0 $$

Opomba. Taylorjev razvoj funkcije več spremenljivk lahko zapišemo kot $$ f(y) = f(x) + (\nabla f(x))^\top (y - x) + {1 \over 2} (y - x)^\top H_f(x) (y - x) + \text{členi višjega reda} $$ Če je v $x$ lokalni minimum, potem velja $H_f(x) \ge 0$, $\nabla f(x) = 0$. Če velja $H_f(x) > 0$ in $\nabla f(x) = 0$, potem je v $x$ lokalni minimum.

Iz dokazov za kriterij 2. odvoda lahko ugotovimo, da če za vsak $x \in K$ velja $H_f(x) > 0$, potem je $f$ strogo konveksna. Obratno ne velja v splošnem (npr. $f(x) = x^4$).

Trditev. Naj bo $K \subseteq \mathbb{R}^n$ konveksna množica, ter $f: K \to \mathbb{R}$ strogo konveksna funkcija. Če je $x^\ast \in K$ globalni maksimum funkcije $f$, potem je $x^\ast$ ekstremna točka za $K$.

Dokaz. Predpostavimo, da $x^\ast$ ni ekstremna točka, torej obstajajo $x, y \in K, \ x \ne y$ ter $\lambda \in (0, 1)$, da velja $x^\ast = (1 - \lambda) x + \lambda y$. Potem velja $$ f(x^\ast) = f((1 - \lambda) x + \lambda y) < (1 - \lambda) f(x) + \lambda f(y) \le (1 - \lambda) f(x^\ast) + \lambda f(x^\ast) = f(x^\ast), $$ protislovje.

Neprimer. Naj bo $K = [-1, 1] \times \mathbb{R}$ in $f: K \to \mathbb{R}$, $f(x, y) = x^2$. Funkcija $f$ je konveksna, saj velja $H_f(x, y) = \begin{bmatrix} 2 & 0 \\ 0 & 0 \end{bmatrix} \ge 0$ (lastni vrednosti sta $0$ in $2$), a ni strogo konveksna, saj za vse $\lambda \in (0, 1)$ velja $$ 1 = f(1, \lambda) = f((1 - \lambda) (1, 0) + \lambda (1, 1)) = (1 - \lambda) f(1, 0) + \lambda f(1, 1) = 1 $$ Globalni maksimumi funkcije $f$ so doseženi v točkah iz $\{-1, 1\} \times \mathbb{R}$. Množica $K$ nima ekstremnih točk.

Konveksne funkcije in vezani ekstremi

Naj bo $\Omega \subseteq \mathbb{R}^n$ odprta množica. Problem vezanih ekstremov z neenačbami (VEN) definiramo kot $$ \begin{aligned} \max / \min \ f(x) \\[1ex] \text{p.p.} \quad x &\in \Omega \\ g_1(x) &\le 0 \\ g_2(x) &\le 0 \\ &\vdots \\ g_m(x) &\le 0 \end{aligned} $$ Množica dopustnih rešitev je torej $$ D = \{x \in \Omega \mid \forall i \in \{1, 2, \dots, m\}: g_i(x) \le 0\}. $$

Primer. Iščemo maksimum in minimum funkcije $f(x, y) = 2x^3 + 4x^2 + y^2 - 2xy$ v območju med $y = 4$ in $y = x^2$.

Imamo torej: $$ \begin{aligned} \Omega &= \mathbb{R}^2 \\ y &\le 4 & y - 4 &\le 0 \\ y &\ge x^2 & x^2 - y &\le 0 \end{aligned} $$