Optimizacijske metode

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 (nadaljevanje).

• ($\Longleftarrow$) Naj bosta $x, y \in (a, b)$ (brez škode za splošnost privzamemo $x < y$) ter $\lambda \in (0, 1)$. Postavimo $z = (1 - \lambda) x + \lambda y \in (x, y)$. Po Lagrangeevem izreku velja $$ \begin{aligned} \exists \xi_1 &\in (x, z): & {f(z) - f(x) \over z - x} &= f'(\xi_1) \\ \exists \xi_2 &\in (z, y): & {f(y) - f(z) \over y - z} &= f'(\xi_2) \\ \exists \xi_3 &\in (\xi_1, \xi_2): & {f'(\xi_2) - f'(\xi_1) \over \xi_2 - \xi_1} &= f''(\xi_3) \end{aligned} $$ Ker velja $f''(\xi_3) \ge 0$ in $\xi_1 < \xi_2$, sledi $f'(\xi_1) \le f'(\xi_2)$ (tj., funkcija $f'$ narašča, ker je njen odvod nenegativen). Velja torej: $$ \begin{aligned} {f(z) - f(x) \over z - x} &\le {f(y) - f(z) \over y - z} & / \cdot (z - x)(y - z) \\ (y - z)(f(z) - f(x)) &\le (z - x)(f(y) - f(z)) \\ (y - z + z - x) f(z) &\le (y - z) f(x) + (z - x) f(y) \\ (y - x) f(z) &\le (1 - \lambda)(y - x) f(x) + \lambda (y - x) f(y) \\ f((1 - \lambda) x + \lambda y) &\le (1 - \lambda) f(x) + \lambda f(y) \end{aligned} $$

Pri Algebri 1 se naučite: $x \in \mathbb{C}^n \setminus \{0\}$ je lastni vektor matrike $A \in \mathbb{R}^{n \times n}$, če obstaja lastna vrednost $\lambda \in \mathbb{C}$, da velja $Ax = \lambda x$. Matrika $A$ je diagonalizabilna, če obstaja $n$ linearno neodvisnih lastnih vektorjev.

Primer. Matrika $A = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}$ ni diagonalizabilna: $$ \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} y \\ 0 \end{bmatrix} = \lambda \begin{bmatrix} x \\ y \end{bmatrix} \\ \begin{aligned} \lambda &= 0: & y &= 0, & x &\ne 0 \\ \lambda &\ne 0: & y &= 0, & x &= 0 & \text{ni lastni vektor} \end{aligned} $$ Imamo torej samo en linearno neodvisen lastni vektor.

Lastne vrednosti poiščemo kot ničle karakterističnega polinoma $\det(A - \lambda I)$. Lastni vektorji so neničelne rešitve enačbe $(A - \lambda I) x = 0$ za lastne vrednosti $\lambda$.

Realna matrika ima lahko kompleksne lastne vrednosti in lastne vektorje: $$ A = \begin{bmatrix} 0 & 1 \\ -1 & 0 \end{bmatrix} \qquad \begin{vmatrix} -\lambda & 1 \\ -1 & -\lambda \end{vmatrix} = \lambda^2 + 1, \quad \lambda = \pm i $$

Če je $A$ diagonalizabilna matrika, jo lahko zapišemo kot $A = PDP^{-1}$, kjer je $P$ obrnljiva matrika, katere stolpci so linearno neodvisni lastni vektorji, $D$ pa diagonalna matrika z ustreznimi lastnimi vrednostmi na diagonali.

Definicija. Matrika $A \in \mathbb{R}^{n \times n}$ je simetrična, če velja $A^\top = A$.

Izrek. Simetrična matrika $A \in \mathbb{R}^{n \times n}$ ima realne lastne vrednosti in je diagonalizabilna v ortonormirani bazi (tj., lastni vektorji imajo normo $1$ in so drug na drugega pravokotni). Tedaj lahko pišemo $A = UDU^\top$, kjer je $U$ ortogonalna matrika (tj., $U^\top U = I$ oziroma $U^{-1} = U^\top$) z lastnimi vektorji v stolpcih.

Definicija. Naj bo $A \in \mathbb{R}^{n \times n}$ simetrična matrika.

• $A$ je pozitivno semidefinitna ($A \ge 0$), če ima same nenegativne lastne vrednosti.
• $A$ je pozitivno definitna ($A > 0$), če ima same pozitivne lastne vrednosti.
• $A$ je negativno semidefinitna ($A \le 0$), če ima same nepozitivne lastne vrednosti.
• $A$ je negativno definitna ($A < 0$), če ima same negativne lastne vrednosti.
• $A$ je nedefinitna, če ima tako pozitivne kot negativne lastne vrednosti.

Definicija. Naj bo $A = (a_{ij})_{i,j=1}^n \in \mathbb{R}^{n \times n}$ simetrična matrika. Kvadratna forma, ki pripada $A$, je $$ f(x) = x^\top A x = [x_1 \ x_2 \ \dots \ x_n] \begin{bmatrix} a_{11} x_1 + a_{12} x_2 + \dots a_{1n} x_n \\ a_{21} x_1 + a_{22} x_2 + \dots a_{2n} x_n \\ \vdots \\ a_{n1} x_1 + a_{n2} x_2 + \dots a_{nn} x_n \end{bmatrix} = \sum_{i=1}^n \sum_{j=1}^n a_{ij} x_i x_j $$

Primera.

• Kvadratna forma za matriko $A = \begin{bmatrix} 3 & 1 \\ 1 & -2 \end{bmatrix}$ je $f(x_1, x_2) = 3 x_1^2 + 2 x_1 x_2 - 2 x_2^2$.
• Kvadratna forma $f(x_1, x_2, x_3) = 4 x_1^2 - 2 x_1 x_2 + 3 x_1 x_3 - x_2^2 + x_3^2$ ustreza matriki $$ A = \begin{bmatrix} 4 & -1 & {3 \over 2} \\ -1 & -1 & 0 \\ {3 \over 2} & 0 & 1 \end{bmatrix}. $$