Diskretisierung und numerische Optimierung - Cheatsheet

Diskretisierung von Differentialgleichungen

Definition:

Umwandlung stetiger Differentialgleichungen (DGL) in algebraische Gleichungen für numerische Berechnungen

Details:

• Ziel: Lösung von DGLs mit Computer
• Methoden: Finite Differenzen, Finite Elemente, Finite Volumen
• Finite Differenzen: Approximation der Ableitungen durch Differenzenquotienten
• Finite Elemente: Zerlegung des Gebiets in Elemente, Interpolation der Lösung
• Finite Volumen: Integration der DGL über Kontrollvolumen
• Zeitdiskretisierung: Explizite vs. implizite Verfahren
• Acht auf Stabilität und Konvergenz der numerischen Lösung

Finite-Differenzen-Methode

Definition:

Näherungsverfahren zur Lösung von Differentialgleichungen durch Diskretisierung.

Details:

• Ersetzt Ableitungen durch Differenzquotienten
• Anwendung auf einem diskretem Gitter
• Vorwärtsdifferenzen: \( f'(x) \approx \frac{f(x+h) - f(x)}{h} \)
• Rückwärtsdifferenzen: \( f'(x) \approx \frac{f(x) - f(x-h)}{h} \)
• Zentrale Differenzen: \( f'(x) \approx \frac{f(x+h) - f(x-h)}{2h} \)
• Höhere Genauigkeit durch Reduktion von \(h\)

Newton-Methoden

Definition:

Newton-Methoden nutzen Ableitungen, um Näherungen für Lösungen nichtlinearer Gleichungen/Optimierungsprobleme zu finden. Zentrales Element: Iterationsverfahren.

Details:

• Ziel: Lösung von \(f(x) = 0\) oder Minimierung von \(f(x)\).
• Iteration: \[x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}\]
• Newton-Raphson-Verfahren für Wurzeln und nichtlineare Gleichungen.
• Erweiterung für Vektoren: Newtons Methode für Systeme nichtlinearer Gleichungen \[x_{k+1} = x_k - J_f(x_k)^{-1} f(x_k)\]
• Hessian-Matrix in der Optimierung nötig.
• Quadratische Konvergenz unter bestimmten Bedingungen.
• Anwendung: Numerische Optimierung und Approximation.

Lineare Programmierung (LP)

Definition:

Optimierungsverfahren, bei dem eine lineare Zielfunktion unter linearen Nebenbedingungen maximiert oder minimiert wird.

Details:

• Zielfunktion: z.B. \( c^T x \)
• Nebenbedingungen: z.B. \( Ax \leq b \)
• Methode: Simplex-Algorithmus oder Innere-Punkte-Methoden
• Lösungsmenge: Polyeder

Simplex-Algorithmus

Definition:

Verfahren zur Lösung linearer Optimierungsprobleme in Standardform.

Details:

• Ziel: Maximierung der Zielfunktion \(c^T x\) unter Nebenbedingungen \(Ax \leq b\) und \(x \geq 0\).
• Startet an einer Ecke des zulässigen Bereichs, bewegt sich entlang von Kanten zu benachbarten Ecken.
• Iteriert bis zur optimalen Lösung oder Feststellung der Unbeschränktheit.
• Pivot-Operation wählt die beste Kante basierend auf dem höchsten Gradient.
• In seltenen Fällen exponentielle Laufzeit, meist jedoch polynomiell im Durchschnitt.
• Standardformen: Primal, Dual und Primal-Dual Simplexverfahren.
• Stabilität und Genauigkeit durch numerische Methoden wie z.B. Schreiber-Methoden verbessert.

Konvexitätsbedingungen für Funktionen

Definition:

Bedingungen, die eine Funktion erfüllen muss, um konvex zu sein.

Details:

• Eine Funktion \( f: \mathbb{R}^n \to \mathbb{R} \) ist konvex, wenn für alle \( x, y \in \mathbb{R}^n \) und \( \lambda \in [0,1] \): \[ f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y) \]
• Zweite Ableitung (Hessematrix) \( H \) einer zweimal differenzierbaren Funktion \( f \) muss positiv semidefinit sein: \[ H \geq 0 \]

Bellman'sche Optimalitätsgleichung

Definition:

Die Bellman'sche Optimalitätsgleichung ist eine rekursive Gleichung, die in der Dynamischen Programmierung verwendet wird, um den optimalen Entscheidungsprozess zu bestimmen.

Details:

• Stellt die Grundlage für viele Optimierungsalgorithmen in der Informatik dar.
• Formulierung: \( V(s) = \max_{a} \left \{ R(s, a) + \gamma \sum_{s'} P(s'|s, a) V(s') \right \} \)
• \( V(s) \): Wertfunktion
• \( a \): Aktion
• \( R(s, a) \): Belohnung für Aktion a im Zustand s
• \( \gamma \): Diskontfaktor
• \( P(s'|s, a) \): Übergangswahrscheinlichkeit zum Zustand s' bei Aktion a im Zustand s