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\to \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)\le \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^{\ast })\ge d({\lambda }^{\ast })$ (schwach), $f(x^{\ast })=d({\lambda }^{\ast })$ (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}(-\text{log}(h(x)))$
• 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^{T}x$ unter Nebenbedingungen $Ax\le 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.