www.wikidata.de-de.nina.az

Quadratische Optimierung Die quadratische Optimierung oder quadratische Programmierung und der damit eng verbundene Begr

Quadratische Optimierung

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.

Definition Bearbeiten

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).

Spezialfälle Bearbeiten

  • Jedes lineare Optimierungsproblem ist ein quadratisches Optimierungsproblem. Setze dazu .
  • Jedes quadratische Optimierungsproblem ist ein quadratisches Programm mit quadratischen Nebenbedingungen. Dazu setzt man und ordnet die Vektoren zeilenweise zur Matrix an.
  • Sind alle auftretenden Matrizen positiv semidefinit, so sind quadratische Programme und quadratische Programme mit quadratischen Nebenbedingungen konvexe Optimierungsprobleme.
  • Unter gewissen Umständen kann ein SOCP auch als quadratisches Programm mit quadratischen Nebenbedingungen formuliert werden.

Beispiel Bearbeiten

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.

Optimalitätskriterien Bearbeiten

Allgemeiner Fall Bearbeiten

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.

Für konvexe Probleme Bearbeiten

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.

Quadratische Programme mit Gleichungsrestriktionen Bearbeiten

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.

Anwendungen Bearbeiten

Typische Anwendungsfälle sind:

  • Methode der kleinsten Quadrate mit oder ohne Nebenbedingungen an die zu bestimmenden Parameter.
  • Bestimmen des minimalen Abstandes zweier Mengen, die Polyeder sind (und damit lineare Ungleichungsrestriktionen erzeugen) oder Schnitte von Ellipsoiden sind (und damit quadratische Ungleichungsrestriktionen erzeugen).
  • Als Teilproblem zur Lösung eines größeren Optimierungsproblems zum Beispiel mittels des SQP-Verfahrens (Sequential Quadratic Programming)

Lösungsmethoden Bearbeiten

Als Lösungsmethoden werden verwendet:

Literatur Bearbeiten

  • C. Geiger, C. Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben. Springer, 2002, ISBN 3-540-42790-2 (eingeschränkte Vorschau in der Google-Buchsuche).
  • Stephen Boyd, Lieven Vandenberghe: Convex Optimization. Cambridge University Press, 2004, ISBN 978-0-521-83378-3 (online).
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 Inhaltsverzeichnis 1 Definition 2 Spezialfalle 3 Beispiel 4 Optimalitatskriterien 4 1 Allgemeiner Fall 4 2 Fur konvexe Probleme 4 3 Quadratische Programme mit Gleichungsrestriktionen 5 Anwendungen 6 Losungsmethoden 7 LiteraturDefinition BearbeitenEs seien E G R m n displaystyle E G in mathbb R m times n nbsp reelle m n displaystyle m times n nbsp Matrizen Q R n n displaystyle Q in mathbb R n times n nbsp eine symmetrische Matrix c x R n displaystyle c x in mathbb R n nbsp sowie f h R m displaystyle f h in mathbb R m nbsp reelle Vektoren und schliesslich d R displaystyle d in mathbb R nbsp eine reelle Zahl Ein Optimierungsproblem der Form Minimiere s x 1 2 x T Q x c T x d unter den Nebenbedingungen E x f G x h displaystyle begin aligned text Minimiere amp s x tfrac 1 2 x T Qx c T x d text unter den Nebenbedingungen amp Ex leq f amp Gx h end aligned nbsp heisst ein quadratisches Optimierungsproblem oder ein quadratisches Programm englisch quadratic program kurz QP Ist das Problem von der Form Minimiere s x 1 2 x T Q x c T x d unter den Nebenbedingungen 1 2 x T P i x r i T x f i 0 i 1 m G x h displaystyle begin aligned text Minimiere amp s x tfrac 1 2 x T Qx c T x d amp text unter den Nebenbedingungen amp tfrac 1 2 x T P i x r i T x f i leq 0 amp i 1 dots m amp Gx h amp end aligned nbsp fur symmetrische Matrizen P i 1 i m displaystyle P i 1 leq i leq m nbsp und Serien von Vektoren r i i f i i displaystyle r i i f i i nbsp so heisst es ein quadratisches Programm mit quadratischen Nebenbedingungen englisch quadratically constrained quadratic program kurz QCQP Spezialfalle BearbeitenJedes lineare Optimierungsproblem ist ein quadratisches Optimierungsproblem Setze dazu Q 0 displaystyle Q 0 nbsp Jedes quadratische Optimierungsproblem ist ein quadratisches Programm mit quadratischen Nebenbedingungen Dazu setzt man P i 0 displaystyle P i 0 nbsp und ordnet die Vektoren r i displaystyle r i nbsp zeilenweise zur Matrix E displaystyle E nbsp an Sind alle auftretenden Matrizen Q P i displaystyle Q P i nbsp positiv semidefinit so sind quadratische Programme und quadratische Programme mit quadratischen Nebenbedingungen konvexe Optimierungsprobleme Unter gewissen Umstanden kann ein SOCP auch als quadratisches Programm mit quadratischen Nebenbedingungen formuliert werden Beispiel BearbeitenBetrachte als Beispiel das Problem min x 1 1 T 2 2 u d N x 1 2 4 x 2 2 1 0 x 1 x 2 1 displaystyle begin aligned min amp left Vert x 1 1 T right Vert 2 2 amp text u d N amp tfrac x 1 2 4 x 2 2 1 leq 0 amp amp x 1 x 2 geq 1 amp end aligned nbsp Ein Umschreiben der quadratischen Terme liefert die in der Definition gegebene Darstellung mit Matrix Vektor Produkten min 1 2 x T 2 0 0 2 x 2 2 x 2 u d N 1 2 x T 0 5 0 0 2 x 1 0 1 1 x 1 0 displaystyle begin aligned min amp tfrac 1 2 x T bigl begin smallmatrix 2 amp 0 0 amp 2 end smallmatrix bigr x 2 2 x 2 amp text u d N amp tfrac 1 2 x T bigl begin smallmatrix 0 5 amp 0 0 amp 2 end smallmatrix bigr x 1 leq 0 amp amp 1 1 x 1 leq 0 amp end aligned nbsp Es handelt sich also um ein quadratisches Programm mit quadratischen Nebenbedingungen Insbesondere ist es ein konvexes Optimierungsproblem da alle auftretenden Matrizen positiv definit sind Optimalitatskriterien BearbeitenAllgemeiner Fall Bearbeiten Fur beliebige Eingabeparameter gibt es das notwendige Optimalitatskriterium dass wenn x displaystyle x nbsp ein lokales Minimum eines QPs oder QCQPs ist dann existieren m l z displaystyle mu lambda z nbsp so dass z x m l displaystyle z x mu lambda nbsp ein Fritz John Punkt ist und z m l displaystyle z mu lambda nbsp ungleich dem Nullvektor ist Sind noch zusatzliche gewisse Regularitatsvoraussetzungen wie zum Beispiel die LICQ die MFCQ oder die Abadie CQ in x displaystyle x nbsp erfullt so gibt es m l displaystyle mu lambda nbsp so dass x m l displaystyle x mu lambda nbsp ein Karush Kuhn Tucker Punkt ist Fur konvexe Probleme Bearbeiten Sind die Matrizen Q P i displaystyle Q P i nbsp alle positiv semidefinit so handelt es sich um ein konvexes Problem Als Regularitatsbedingung fur die Karush Kuhn Tucker Bedingungen steht somit auch die Slater Bedingung zur Verfugung welche die Regularitat aller zulassigen Punkte liefert Des Weiteren ist jedes lokale Minimum ein globales Minimum Ausserdem ist jeder Karush Kuhn Tucker Punkt ohne weitere Regularitatsvoraussetzungen ein globales Minimum und somit ein hinreichendes Optimalitatskriterium Quadratische Programme mit Gleichungsrestriktionen Bearbeiten Betrachtet man das Quadratische Programm das nur Gleichungsrestriktionen enthalt min 1 2 x T Q x c T x d u d N G x h displaystyle begin aligned min amp tfrac 1 2 x T Qx c T x d text u d N amp Gx h end aligned nbsp so ist jeder KKT Punkt x m displaystyle x mu nbsp des obigen Problems eine Losung des linearen Gleichungssystems Q G T G 0 x l c h displaystyle begin bmatrix Q amp G T G amp 0 end bmatrix begin bmatrix x lambda end bmatrix begin bmatrix c h end bmatrix nbsp Ist Q displaystyle Q nbsp positiv semidefinit so ist die Losung des Gleichungssystems aufgrund der Konvexitat des Problems eine globale Optimallosung des Optimierungsproblems Lineare Gleichungssysteme der obigen Form werden auch Sattelpunktprobleme genannt da man sie als Bestimmung des Sattelpunktes der Lagrange Funktion auffassen kann Anwendungen BearbeitenTypische Anwendungsfalle sind Methode der kleinsten Quadrate mit oder ohne Nebenbedingungen an die zu bestimmenden Parameter Bestimmen des minimalen Abstandes zweier Mengen die Polyeder sind und damit lineare Ungleichungsrestriktionen erzeugen oder Schnitte von Ellipsoiden sind und damit quadratische Ungleichungsrestriktionen erzeugen Als Teilproblem zur Losung eines grosseren Optimierungsproblems zum Beispiel mittels des SQP Verfahrens Sequential Quadratic Programming Losungsmethoden BearbeitenAls Losungsmethoden werden verwendet Gradientenverfahren Innere Punkte Verfahren Active Set Methoden wie zum Beispiel der Primal Dual Active Set Algorithmus Fuhren die KKT Bedingungen auf ein Lineares Komplementaritatsproblem so stehen spezialisierte Algorithmen wie Lemkes Algorithmus oder Unique Sink Orientations zur Verfugung Literatur BearbeitenC Geiger C Kanzow Theorie und Numerik restringierter Optimierungsaufgaben Springer 2002 ISBN 3 540 42790 2 eingeschrankte Vorschau in der Google Buchsuche Stephen Boyd Lieven Vandenberghe Convex Optimization Cambridge University Press 2004 ISBN 978 0 521 83378 3 online Abgerufen von https de wikipedia org w index php title Quadratische Optimierung amp oldid 208364260