Loading AI tools
spezielles Problem der Mathematik Aus Wikipedia, der freien Enzyklopädie
Die quadratische Optimierung oder quadratische Programmierung und der damit eng verbundene Begriff des quadratischen Programms mit quadratischen Restriktionen ist ein spezielles Problem in der mathematischen Optimierung, das sich durch die Einfachheit der auftretenden Funktionen auszeichnet. Quadratische Programme treten zum Beispiel bei der Minimierung von Abstandsfunktionen auf oder als Unterprobleme von komplexeren Optimierungsproblemen.
Es seien reelle -Matrizen, eine symmetrische Matrix, sowie reelle Vektoren und schließlich eine reelle Zahl.
Ein Optimierungsproblem der Form
heißt ein quadratisches Optimierungsproblem oder ein quadratisches Programm (englisch quadratic program, kurz QP).
Ist das Problem von der Form
für symmetrische Matrizen und Serien von Vektoren , so heißt es ein quadratisches Programm mit quadratischen Nebenbedingungen (englisch quadratically constrained quadratic program, kurz QCQP).
Betrachte als Beispiel das Problem
Ein Umschreiben der quadratischen Terme liefert die in der Definition gegebene Darstellung mit Matrix-Vektor-Produkten:
Es handelt sich also um ein quadratisches Programm mit quadratischen Nebenbedingungen. Insbesondere ist es ein konvexes Optimierungsproblem, da alle auftretenden Matrizen positiv definit sind.
Für beliebige Eingabeparameter gibt es das notwendige Optimalitätskriterium, dass wenn ein lokales Minimum eines QPs oder QCQPs ist, dann existieren , so dass ein Fritz-John-Punkt ist und ungleich dem Nullvektor ist. Sind noch zusätzliche gewisse Regularitätsvoraussetzungen wie zum Beispiel die LICQ, die MFCQ oder die Abadie CQ in erfüllt, so gibt es , so dass ein Karush-Kuhn-Tucker-Punkt ist.
Sind die Matrizen alle positiv semidefinit, so handelt es sich um ein konvexes Problem. Als Regularitätsbedingung für die Karush-Kuhn-Tucker-Bedingungen steht somit auch die Slater-Bedingung zur Verfügung, welche die Regularität aller zulässigen Punkte liefert. Des Weiteren ist jedes lokale Minimum ein globales Minimum. Außerdem ist jeder Karush-Kuhn-Tucker-Punkt ohne weitere Regularitätsvoraussetzungen ein globales Minimum und somit ein hinreichendes Optimalitätskriterium.
Betrachtet man das Quadratische Programm, das nur Gleichungsrestriktionen enthält
so ist jeder KKT-Punkt des obigen Problems eine Lösung des linearen Gleichungssystems
Ist positiv semidefinit, so ist die Lösung des Gleichungssystems aufgrund der Konvexität des Problems eine globale Optimallösung des Optimierungsproblems. Lineare Gleichungssysteme der obigen Form werden auch Sattelpunktprobleme genannt, da man sie als Bestimmung des Sattelpunktes der Lagrange-Funktion auffassen kann.
Typische Anwendungsfälle sind:
Als Lösungsmethoden werden verwendet:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.