Optimierung für Ingenieure mit Praktikum - Cheatsheet

Simplex-Verfahren

Definition:

Algorithmus zur Lösung linearer Optimierungsprobleme (LP). Iterativer Prozess zur Maximierung oder Minimierung einer linearen Zielfunktion bei gegebenen linearen Einschränkungen.

Details:

• Startpunkt: Basislösung
• Zielfunktion: \ Z = c^Tx
• Schrittweise Verbesserung: Durch Wechsel der Basis
• Schrittwahl: Pivot-Operation
• Abbruchbedingung: Wenn keine Verbesserungen mehr möglich sind
• Endresultat: Optimale Lösung, falls vorhanden
• Bedeutung der Schlupfvariablen für die Optimierung

Dualitätstheorie in der linearen Optimierung

Definition:

Die Dualitätstheorie in der linearen Optimierung stellt eine Beziehung zwischen einem linearen Optimierungsproblem (Primärproblem) und einem zugehörigen Dualproblem her.

Details:

• Jedes lineare Optimierungsproblem kann ein Dualproblem haben.
• Das Primärproblem und das Dualproblem liefern dieselbe optimale Zielfunktionsbewertung unter bestimmten Bedingungen, bekannt als starker Dualitätssatz.
• Mathematische Formulierung für ein Primärproblem (in Standardform):
  • Minimiere: \(c^T x\)
  • unter Nebenbedingungen: \(Ax = b\), \(x \geq 0\)
• Dualproblem:
  • Maximiere: \(b^T y\)
  • unter Nebenbedingungen: \(A^T y \leq c\)
• Schwache Dualität: Der Zielfunktionswert des Dualproblems ist immer kleiner oder gleich dem des Primärproblems.
• Starke Dualität: Im Optimum sind die Werte beider Probleme gleich (\(x\) und \(y\) sind jeweils optimal).
• Komplementärschlupf-Bedingungen: Für optimale Lösungen \(x^*\) und \(y^*\) gilt \( (c - A^T y^*)^T x^* = 0 \).

Newton-Verfahren zur Lösung nichtlinearer Optimierungsprobleme

Definition:

Newton-Verfahren (Newton-Raphson-Methode) ist ein iteratives Verfahren zur Lösung nichtlinearer Gleichungssysteme.

Details:

• Verwendet die Taylor-Reihe zur Approximation der Funktion.
• Aktualisierung der Lösung erfolgt durch: \[ x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)} \]
• Schnelle Konvergenz in der Nähe einer Lösung, allerdings keine Garantie für Konvergenz.
• Initialer Startwert und zweite Ableitung (Hesse-Matrix) notwendig.
• Hesse-Matrix kann in großen Dimensionen schwer zu berechnen sein, daher Verwendung von Quasi-Newton-Methoden möglich.
• Anwendung in Optimierungsproblemen durch Minimierung der Kostenfunktion.

Branch-and-Bound-Verfahren in der ganzzahligen Optimierung

Definition:

Algorithmus zur Lösung von ganzzahligen Optimierungsproblemen durch systematische Enumeration und Schrankenbildung.

Details:

• Aufteilung des Problems in Teilprobleme durch Branching
• Nutzung von Schranken (Bounds), um Teilprobleme frühzeitig auszuschließen
• Führungsstruktur: Entscheidungsbaum
• Finden einer zulässigen Lösung -> Obere Schranke
• Lösen des Relaxationsproblems -> Untere Schranke
• Endbedingung: Aktuelle obere Schranke ≤ Aktuelle untere Schranke

Bellman-Gleichung in der dynamischen Programmierung

Definition:

Bellman-Gleichung: zentrale Rekursionsgleichung in der dynamischen Programmierung, hilft optimale Entscheidungen zu treffen.

Details:

• Definiert durch: \(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
• \(\gamma\): Diskontfaktor
• \(P(s'|s,a)\): Übergangswahrscheinlichkeit

Modellierung und Implementierung von Optimierungsproblemen mit Software

Definition:

Modellierung und Implementierung von Optimierungsproblemen mit Software: Formulierung mathematischer Modelle, Auswahl geeigneter Algorithmen und Umsetzung in Software zur Lösung von Optimierungsaufgaben.

Details:

• Formulierung: Definition der Zielfunktion und Restriktionen.
• Algorithmen: Auswahl basierend auf Problemtyp (z.B. lineare, nichtlineare, ganzzahlige oder kombinatorische Optimierung).
• Implementierung: Verwendung spezieller Software oder Programmiersprachen (z.B. MATLAB, Python mit Bibliotheken wie PuLP, Gurobi).
• Validierung: Testen und Validieren des Modells mit echten Daten.
• Iterativer Prozess: Ständige Anpassung und Verbesserung des Modellierungsansatzes.

Lagrange-Multiplikatoren in der nichtlinearen Optimierung

Definition:

Methode zur Lösung von Optimierungsproblemen mit Nebenbedingungen.

Details:

• Finde Extrema der Funktion f(x, y, ...) unter der Bedingung g(x, y, ...) = 0 mithilfe eines neuen Parameters \( \lambda \) (Lagrange-Multiplikator).
• Lagrange-Funktion: \[ L(x, y, ..., \lambda) = f(x, y, ...) - \lambda g(x, y, ...) \]
• Setze die partiellen Ableitungen der Lagrange-Funktion nach x, y, ..., \( \lambda \) gleich null: \[ \frac{\partial L}{\partial x}, \frac{\partial L}{\partial y}, ..., \frac{\partial L}{\partial \lambda} = 0 \]
• Löse das entstehende Gleichungssystem zur Bestimmung der kritischen Punkte und der Lagrange-Multiplikatoren.