Projektseminar Optimierung - Cheatsheet

Definition und Eigenschaften von Konvexität

Definition:

Eine Menge ist konvex, wenn für je zwei Punkte in der Menge das gesamte Liniensegment zwischen diesen Punkten auch in der Menge liegt.

Details:

• Formale Definition: Eine Menge \(C\) ist konvex, wenn für alle \(x, y \in C\) und alle \( \lambda \in [0,1] \) gilt: \( \lambda x + (1 - \lambda)y \in C \).
• Eigenschaft: Bei einer konvexen Funktion \(f\) ist der Bereich unterhalb des Graphen immer eine konvexe Menge.
• Mathematische Notation: Eine Funktion \(f: \mathbb{R}^n \rightarrow \mathbb{R}\) ist konvex, wenn für alle \(x, y \in \mathrm{dom}(f)\) und alle \( \lambda \in [0,1] \) gilt: \[f(\lambda x + (1 - \lambda) y) \leq \lambda f(x) + (1 - \lambda) f(y).\]

Lagrange-Multiplikatoren und duale Probleme

Definition:

Anwendung der Lagrange-Multiplikatoren zur Lösung von Optimierungsproblemen mit Nebenbedingungen und Verbindung zu dualen Problemen.

Details:

• Lagrange-Funktion: \[ \mathcal{L}(x, \lambda) = f(x) + \lambda^T g(x) \] , wobei \( f \) die Zielfunktion und \( g \) die Nebenbedingungen sind.
• Karush-Kuhn-Tucker (KKT) Bedingungen: Notwendige Bedingungen für Optimalität bei nichtlinearen Problemen.
• Dualitätstheorie: Jedes primale Optimierungsproblem kann einem dualen Problem zugeordnet werden.
• Schwache und starke Dualität: \( f(x^*) \geq d(\lambda^*) \) (schwach), \( f(x^*) = d(\lambda^*) \) (stark, unter bestimmten Bedingungen).
• Anwendungen: Lösungen von Optimierungsaufgaben in der Ökonomie, Maschinenbau, etc.

Simplex-Verfahren für lineare Programmierung

Definition:

Das Simplex-Verfahren iteriert über Ecken der zulässigen Menge, um die optimale Lösung eines linearen Programms zu finden.

Details:

• Start mit einer zulässigen Basislösung
• Bestimme eine ein- und ausgehende Variable
• Schrittweise Verbesserung der Zielfunktion
• Überprüfe, ob eine optimale Lösung erreicht ist
• Falls nicht, wiederhole den Prozess

Innere-Punkte-Verfahren

Definition:

Innere-Punkte-Verfahren (Interior-Point Method) wird zur Lösung von Optimierungsproblemen verwendet und bewegt sich durch das Innere der zulässigen Menge.

Details:

• Ziel: Minimierung von konvexen Funktionen über konvexe Mengen
• Benutzt Barrieremethoden: \( \text{min } f(x) + \frac{1}{t} \big( - \text{log} (h(x)) \big) \)
• Algorithmus: Zentralpfad folgen durch sukzessive Lösung von Näherungsproblemen
• Initialisierungspunkt: Muss im Inneren der Zulässigkeitsmenge liegen
• Effizient bei großen, spärlich besetzten Problemen
• KKT-Bedingungen: Erfüllt bei Konvergenz
• Verwendet Newton-Verfahren für System von Gleichungen

Heuristische und Metaheuristische Ansätze

Definition:

Optimierungsmethoden, die genutzt werden, um zufriedenstellende Lösungen für schwierige Probleme zu finden, wo exakte Methoden zu aufwendig sind.

Details:

• Heuristiken: Einfache, oft problem-spezifische Verfahren für schnelle, aber möglicherweise suboptimale Lösungen.
• Metaheuristiken: Generische, problemunabhängige Strategien, um Heuristiken zu steuern und zu verbessern.
• Beispiele Heuristiken: Greedy-Algorithmen, lokale Suche.
• Beispiele Metaheuristiken: Genetische Algorithmen, Simulierte Abkühlung, Tabu-Suche, Ameisenalgorithmus.
• Anwendung: Probleme mit großer Lösungsraum, wie z. B. das Rucksackproblem, das Traveling-Salesman-Problem (TSP).
• Ziel: Zeit- und ressourceneffiziente Annäherung an optimale Lösung.
• Vorteil Metaheuristiken: Flexibilität und Anwendbarkeit auf verschiedene Problemtypen.
• \textbf{Formeln}: Keine spezifischen Formeln, jedoch oft iterative Algorithmen genutzt.

Optimierung in der Produktionsplanung

Definition:

Optimierung in der Produktionsplanung zielt darauf ab, Produktionsprozesse durch mathematische Modelle und Algorithmen zu optimieren.

Details:

• Ziel: Minimierung von Kosten, Maximierung von Effizienz
• Typische Probleme: Losgrößenplanung, Maschinenbelegungsplanung, Materialbedarfsplanung
• Modelle: Lineare Programmierung (LP), Gemischt-Ganzzahlige Lineare Programmierung (MILP)
• Formel: Zielfunktion \ minimiere/maximiere \(c^Tx\) unter Nebenbedingungen \(Ax \leq b\)
• Software: Solver wie CPLEX, Gurobi
• Heuristiken: Genetische Algorithmen, Simulated Annealing

Optimierung in der Telekommunikation

Definition:

Optimierung in der Telekommunikation bezieht sich auf die Anwendung mathematischer Methoden zur Verbesserung der Effizienz, Kapazität und Leistung von Telekommunikationssystemen.

Details:

• Ziel: Maximierung der Netzwerkleistung und Minimierung der Kosten
• Wichtige Methoden: Lineare und nichtlineare Optimierung, Ganzzahlige Programmierung
• Anwendungsbereiche: Netzwerkdesign, Ressourcenallokation, Verkehrsmanagement
• Kritische Kennzahlen: Latenz, Durchsatz, Kapazität
• Formeln: Kostenfunktion \ (C(x) = \sum c_i x_i\), Kapazitätsbeschränkung \ (\sum x_i \leq K\)

Ergebnisanalyse und Validierung

Definition:

Prozess zur Überprüfung und Bewertung der Ergebnisse optimierter Modelle.

Details:

• Ergebnisbewertung: Überprüfen, ob die Ergebnisse die ursprünglichen Ziele erfüllen.
• Gütemaße: Verwendung von Metriken wie Fehlermaße (\textit{MSE}, \textit{MAE}) und Genauigkeit.
• Validierung: Testen der Modelle auf Datensätzen, die nicht für das Training verwendet wurden.
• Cross-Validation: Aufteilung der Daten in Trainings- und Validierungssets, häufig in k-Folds.
• Robustheit: Überprüfung der Stabilität der Ergebnisse gegenüber Variationen im Datensatz.
• Overfitting-Vermeidung: Sicherstellen, dass das Modell nicht zu spezifisch auf Trainingsdaten angepasst ist und auf neuen Daten gut generalisiert.
• Dokumentation: Ergebnisdarstellung und Interpretation der Resultate.