11 - Optimierung von Funktionen

Optimierung von Funktionen mit einer Variablen

Lokale und globale Extrema

Eine Funktion $f: (a,b) \rightarrow \mathbb{R}$ besitzt im Punkt $x_0 \in (a,b)$ ein lokales Minimum, wenn es ein $c > 0$ gibt, sodass $$f(x_0) \leq f(x) \,\,\, \text{für alle} \,\,\, x \,\,\, \text{mit} \,\,\, |x-x_0|<c.$$ $x_0$ ist ein globales Minimum, wenn $f(x_0) \leq f(x)$ für alle $x \in (a,b)$. Der Punkt $x_0 \in (a,b)$ ist ein lokales Maximum, wenn es ein $c > 0$ gibt, sodass $$f(x_0) \geq f(x) \,\,\, \text{für alle} \,\,\, x \,\,\, \text{mit} \,\,\, |x-x_0|<c.$$ $f$ hat in $x_0$ ein globales Maximum, wenn $f(x_0) \geq f(x)$ für alle $x \in (a,b)$.

Notwendiges Kriterium

Wenn $x_0 \in (a,b)$ ein lokales Extremum ist, dann gilt $f'(x_0)=0$. Ein Punkt $x$ mit $f'(x)=0$ heißt stationärer Punkt.

Hinreichendes Kriterium 1. Ordnung

Sei $x_0 \in (a,b)$ ein stationärer Punkt von $f(x)$. Wechselt das Vorzeichen von $f'(x)$ in $x_0$ ...

... von $-$ nach $+$, dann ist $x_0$ ein lokales Minimum.
... von $+$ nach $-$, dann ist $x_0$ ein lokales Maximum.

Hinreichendes Kriterium 2. Ordnung

Sei $x_0 \in (a,b)$ ein stationärer Punkt von $f(x)$.

Ist $f''(x_0) > 0$, dann ist $x_0$ ein lokales Minimum.
Ist $f''(x_0) < 0$, dann ist $x_0$ ein lokales Maximum.

Eine Funktion $f(x)$ ist konvex auf $(a,b)$, wenn alle Verbindungsstrecken von zwei Punkten auf dem Graphen mit $x$-Koordinaten in $(a,b)$ oberhalt des Graphen verlaufen. Verlaufen diese immer unterhalb des Graphen, nennt man $f(x)$ konkav.

Die Funktion $f(x)$ sei zweimal differenzierbar. Gilt $f''(x) > 0$ für alle $x \in (a,b)$, dann ist $f(x)$ in $(a,b)$ konvex. Gilt $f''(x) < 0$ für alle $x \in (a,b)$, dann ist $f(x)$ in $(a,b)$ konkav.

Optimierung von Funktionen mit mehreren Variablen

Sei $f: D \rightarrow \mathbb{R}, D \subset \mathbb{R}^n,$ eine Funktion. Ein Punkt $\textbf{x}_0$ heißt lokales Minimum von $f$, wenn es ein $c > 0$ gibt, sodass $f(\textbf{x}_0) \leq f(\textbf{x})$ für alle $\textbf{x}$ mit $||\textbf{x} - \textbf{x}_0|| \leq c$. Ist der Punkt $\textbf{x}_0$ ein lokales Minimum der Funktion $- f(\textbf{x})$, dann heißt $\textbf{x}_0$ lokales Maximum von $f$. In beiden Fällen wird $\textbf{x}_0$ lokales Extremum von $f$ genannt.

Ein Punkt $\textbf{x} \in \mathbb{R}^n$ mit $\text{grad} f(\textbf{x}) = \textbf{0}$ heißt stationärer Punkt.

Ein Punkt $\textbf{x}_0 \in D$ heißt innerer Punkt der Menge $D$, wenn ein $c > 0$ existiert, sodass alle Punkte $\textbf{x}$ mit $||\textbf{x} - \textbf{x}_0|| < c$ auch in der Menge $D$ liegen.

Notwendiges und hinreichendes Kriterium für ein Extremum

Wenn $\textbf{x}_0 \in D$ ein innerer Punkt von $D$ und ein lokales Extremum der Funktion $f: D \rightarrow \mathbb{R}$ ist, dann gilt $\text{grad}f(\textbf{x}_0) = 0$.

Eine symmetrische $(n \times n)$-Matrix $\textbf{A}$ heißt positiv definit, wenn $\textbf{x}'\textbf{Ax} > 0$ für alle $\textbf{x} \neq 0$. Gilt nur $\textbf{x}'\textbf{Ax} \geq 0$ für alle $\textbf{x} \neq 0$, dann nennt man $\textbf{A}$ positiv semidefinit. Wenn $-\textbf{A}$ positiv (semi-)definit ist, dann heißt $\textbf{A}$ negativ (semi-)definit. Ist $\textbf{A}$ weder positiv noch negativ definit, nennt man $\textbf{A}$ indefinit.

Eine $(n \times n)$-Matrix $\textbf{A}$ ist genau dann positiv definit, wenn alle Determinanten $\text{det}(\textbf{A}_i)$ der Teilmatrizen $\textbf{A}_i$, die aus den ersten $i$ Zeilen und Spalten bestehen, positiv sind.
Eine $(2 \times 2)$-Matrix $\textbf{A} = \left(\begin{array}{cc} a & b \\ c & d \end{array}\right)$ ist insbesondere genau dann positiv definit, wenn $a > 0$ und $\text{det}(\textbf{A}) = ad - bc > 0$ gilt.

Sei $f: D \rightarrow \mathbb{R}$ zweimal stetig differenzierbar und $\textbf{x}_0$ ein stationärer Punkt, der innerer Punkt von $D$ ist. Dann gilt:

$\textbf{x}_0$ ist ein lokales Minimum, wenn $\textbf{H}_f(\textbf{x}_0)$ positiv definit ist.
$\textbf{x}_0$ ist ein lokales Maximum, wenn $\textbf{H}_f(\textbf{x}_0)$ negativ definit ist. (Man prüfe die negative Matrix $-\textbf{H}_f(\textbf{x}_0)$ auf positive Definitheit.)
$\textbf{x}_0$ ist ein Sattelpunkt, wenn $\textbf{H}_f(\textbf{x}_0)$ indefinit ist.

Optimierung unter Nebenbedingungen

In einem restringierten Optimierungsproblem sollen die Extrema einer Funktion $f: D \rightarrow \mathbb{R}, D \subset \mathbb{R}^n$, unter den $m$ Nebenbedingungen $$g_1(\textbf{x}) = 0, g_2(\textbf{x}) = 0, \ldots, g_m(\textbf{x}) = 0$$ gefunden werden.

Seien die Funktionen $f, g_1,\ldots,g_m: D \rightarrow \mathbb{R}$ stetig differenzierbar und $\textbf{x}_0$ ein lokales Extremum von $f(\textbf{x})$ unter den Nebenbedingungen $g_i(\textbf{x}) = 0$, $i = 1,\ldots,m$. Weiter habe die $(m \times n)$-Jakobi-Matrix $$g'(\textbf{x}_0) = \left(\begin{array}{ccc} \frac{\partial g_1(\textbf{x}_0)}{\partial x_1} & \cdots & \frac{\partial g_1(\textbf{x}_0)}{\partial x_n}\\ \vdots & & \vdots \\ \frac{\partial g_m(\textbf{x}_0)}{\partial x_1} & \cdots & \frac{\partial g_m(\textbf{x}_0)}{\partial x_n}\end{array}\right)$$ der partiellen Ableitungen der $g_i$ nach $x_1,\ldots,x_n$ vollen Rang $m$. Dann existieren eindeutige Zahlen $\lambda_1,\ldots,\lambda_m \in \mathbb{R}$, sodass für die Funktion $F: D \rightarrow \mathbb{R}$, $$F(\textbf{x},\lambda_1,\ldots,\lambda_m) = f(\textbf{x}) + \sum_{i=1}^m \, \lambda_i g_i(\textbf{x})$$ gilt, dass $$\text{grad}F(\textbf{x}_0,\lambda_1,\ldots,\lambda_m) = \text{grad} f(\textbf{x}_0) + \sum_{i=1}^m \, \lambda_i\text{grad} g_i(\textbf{x}_0) = \textbf{0}.$$ Die Funktion $F$ heißt Lagrange-Funktion und die $\lambda_i$ Lagrange-Multiplikatoren.