Mathematische Optimierung
Mathematische Optimierung sucht das beste Element, gemessen an einem bestimmten Ziel, aus einer Menge realisierbarer Alternativen und liefert die Theorie und Algorithmen dafür.
Definition
Ein Optimierungsproblem besteht darin, eine Zielfunktion über einer durch Nebenbedingungen definierten zulässigen Menge zu minimieren oder zu maximieren; seine Lösung ist ein zulässiger Punkt, an dem die Zielfunktion ihren besten Wert erreicht, gekennzeichnet durch Optimalitätsbedingungen.
Scope
Dieser Bereich umfasst unbeschränkte und beschränkte Optimierung, Konvexität und Dualität, lineare, quadratische und nichtlineare Programmierung, Optimalitätsbedingungen vom Lagrange- und Karush-Kuhn-Tucker-Typ sowie die Algorithmen, von Simplex- und Innere-Punkte-Methoden bis hin zu Gradienten- und Newton-Methoden, die Optima berechnen. Er erstreckt sich durch die optimale Steuerung auf die Optimierung über die Zeit.
Sub-topics
Core questions
- Existiert ein Optimum, und ist es eindeutig oder global?
- Welche Bedingungen kennzeichnen einen optimalen Punkt?
- Wie macht Konvexität ein Problem handhabbar?
- Welche Algorithmen berechnen Lösungen zuverlässig und effizient?
Key theories
- Optimalitätsbedingungen
- Lagrange-Multiplikatoren und die Karush-Kuhn-Tucker-Bedingungen charakterisieren beschränkte Optima durch Stationarität, Zulässigkeit und Komplementarität, indem sie die Bedingung des verschwindenden Gradienten des unbeschränkten Falls verallgemeinern.
- Konvexität und Dualität
- Für konvexe Probleme ist jedes lokale Optimum global, und die Lagrange-Dualität liefert Schranken und Optimalitätsnachweise durch den starken Dualitätssatz.
- Iterative Algorithmen
- Optima werden durch iterative Schemata wie die Simplex- und Innere-Punkte-Methoden für lineare Programme und Gradienten-, Newton- und Quasi-Newton-Methoden für nichtlineare Probleme berechnet, wobei die Konvergenz durch die Problemstruktur bestimmt wird.
Clinical relevance
Optimierung liegt der Operations Research, der Wirtschaft, dem maschinellen Lernen, dem Ingenieurwesen, der Steuerung und der Logistik zugrunde und bietet den Standardrahmen für Ressourcenallokation, Modellanpassung und Entscheidungsfindung unter Nebenbedingungen.
History
Die Optimierung entwickelte sich aus den Lagrange-Multiplikatoren und der Variationsrechnung. Die lineare Programmierung entstand in den 1940er Jahren mit den Arbeiten von Kantorovich und Dantzig und der Simplex-Methode, die Kuhn-Tucker-Bedingungen von 1951 vereinigten die beschränkte Optimierung, und Innere-Punkte-Methoden transformierten die großskalige Berechnung ab den 1980er Jahren.
Key figures
- Joseph-Louis Lagrange
- George Dantzig
- Leonid Kantorovich
- Harold Kuhn
- Albert Tucker
Related topics
Seminal works
- nocedal2006
- boyd2004
- bertsekas1999
Frequently asked questions
- Warum ist Konvexität in der Optimierung so wichtig?
- In einem konvexen Problem ist jedes lokale Minimum automatisch ein globales Minimum, und es gelten leistungsstarke Dualitäts- und algorithmische Garantien. Dies macht konvexe Probleme zuverlässig lösbar, während allgemeine nichtkonvexe Probleme viele lokale Optima aufweisen können und keine effiziente Garantie für das Auffinden des besten Optimums bieten.
- Was sind die Karush-Kuhn-Tucker-Bedingungen?
- Sie sind die notwendigen Bedingungen erster Ordnung für eine Lösung eines beschränkten Optimierungsproblems, die die Lagrange-Multiplikatoren auf Ungleichheitsnebenbedingungen verallgemeinern. Sie kombinieren die Stationarität der Lagrange-Funktion, die Zulässigkeit und eine komplementäre Schlupfbeziehung zwischen Multiplikatoren und aktiven Nebenbedingungen.