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

Es seien $E;G\in \mathbb {R} ^{m\times n}$ reelle $m\times n$-Matrizen, $Q\in \mathbb {R} ^{n\times n}$ eine symmetrische Matrix, $c;x\in \mathbb {R} ^{n}$ sowie $f;h\in \mathbb {R} ^{m}$ reelle Vektoren und schließlich $d\in \mathbb {R}$ eine reelle Zahl.

Ein Optimierungsproblem der Form

${\begin{aligned}{\text{Minimiere }}&s(x)={\tfrac {1}{2}}x^{T}Qx+c^{T}x+d\\{\text{unter den Nebenbedingungen }}&Ex\leq f\\&Gx=h\end{aligned}}$

heißt ein quadratisches Optimierungsproblem oder ein quadratisches Programm (englisch quadratic program, kurz QP).

Ist das Problem von der Form

${\begin{aligned}{\text{Minimiere }}&s(x)={\tfrac {1}{2}}x^{T}Qx+c^{T}x+d&\\{\text{unter den Nebenbedingungen }}&{\tfrac {1}{2}}x^{T}P_{i}x+r_{i}^{T}x+f_{i}\leq 0&i=1,\dots ,m\\&Gx=h&\end{aligned}}$

für symmetrische Matrizen $(P_{i})_{1\leq i\leq m}$ und Serien von Vektoren $(r_{i})_{i};(f_{i})_{i}$, so heißt es ein quadratisches Programm mit quadratischen Nebenbedingungen (englisch quadratically constrained quadratic program, kurz QCQP).

Anmerkungen

• Die additive Konstante $d$ beeinflusst nicht die Lage der Optimalpunkte und kann deshalb bei der Formulierung des Optimierungsproblems unterschlagen werden.
• Die Symmetrieforderung an die Matrizen $Q$ und $P_{i}$ stellt keine Einschränkung dar, was auf folgendem Trick beruht. Falls die quadratische Matrix $A$ nicht symmetrisch ist, kann der Ausdruck $x^{T}Ax$ durch $x^{T}{\tilde {A}}x$ ersetzen werden, wobei ${\tilde {A}}:={\frac {1}{2}}\left(A+A^{T}\right)$ gilt. Die Matrix ${\tilde {A}}$ ist symmetrisch und es gilt $x^{T}Ax=x^{T}{\tilde {A}}x$ für alle $x$.

Spezialfälle

• Jedes lineare Optimierungsproblem ist ein quadratisches Optimierungsproblem. Setze dazu $Q=0$.
• Jedes quadratische Optimierungsproblem ist ein quadratisches Programm mit quadratischen Nebenbedingungen. Dazu setzt man $P_{i}=0$ und ordnet die Vektoren $r_{i}$ zeilenweise zur Matrix $E$ an.
• Sind alle auftretenden Matrizen $Q,P_{i}$ 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

Betrachte als Beispiel das Problem

${\begin{aligned}\min \ &\left\Vert x-(-1,-1)^{T}\right\Vert _{2}^{2}&\\{\text{u. d. N. }}&{\tfrac {x_{1}^{2}}{4}}+x_{2}^{2}-1\leq 0&\\&x_{1}-x_{2}\geq -1&\end{aligned}}$

Ein Umschreiben der quadratischen Terme liefert die in der Definition gegebene Darstellung mit Matrix-Vektor-Produkten:

${\begin{aligned}\min \ &{\tfrac {1}{2}}x^{T}{\bigl (}{\begin{smallmatrix}2&0\\0&2\end{smallmatrix}}{\bigr )}x+(2,2)x+2&\\{\text{u. d. N. }}&{\tfrac {1}{2}}x^{T}{\bigl (}{\begin{smallmatrix}0{,}5&0\\0&2\end{smallmatrix}}{\bigr )}x-1\leq 0&\\&(-1,1)x-1\leq 0&\end{aligned}}$.

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

Allgemeiner Fall

Für beliebige Eingabeparameter gibt es das notwendige Optimalitätskriterium, dass wenn $x^{*}$ ein lokales Minimum eines QPs oder QCQPs ist, dann existieren $\mu ^{*},\lambda ^{*},z^{*}$, so dass $(z^{*},x^{*},\mu ^{*},\lambda ^{*})$ ein Fritz-John-Punkt ist und $(z^{*},\mu ^{*},\lambda ^{*})$ ungleich dem Nullvektor ist. Sind noch zusätzliche gewisse Regularitätsvoraussetzungen wie zum Beispiel die LICQ, die MFCQ oder die Abadie CQ in $x^{*}$ erfüllt, so gibt es $\mu ^{*},\lambda ^{*}$, so dass $(x^{*},\mu ^{*},\lambda ^{*})$ ein Karush-Kuhn-Tucker-Punkt ist.

Für konvexe Probleme

Sind die Matrizen $Q,P_{i}$ 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

Betrachtet man das Quadratische Programm, das nur Gleichungsrestriktionen enthält

${\begin{aligned}\min \ &\,{\tfrac {1}{2}}x^{T}Qx+c^{T}x+d\\{\text{u.d.N. }}&\,Gx=h,\end{aligned}}$

so ist jeder KKT-Punkt $(x^{*},\mu ^{*})$ des obigen Problems eine Lösung des linearen Gleichungssystems

${\begin{bmatrix}Q&G^{T}\\G&0\end{bmatrix}}{\begin{bmatrix}x\\\lambda \end{bmatrix}}={\begin{bmatrix}-\ c\\h\end{bmatrix}}$.

Ist $Q$ 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

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

Als Lösungsmethoden werden verwendet:

• Gradientenverfahren
• Innere-Punkte-Verfahren
• Active-Set-Methoden wie zum Beispiel der Primal-Dual-Active-Set-Algorithmus.
• Führen die KKT-Bedingungen auf ein Lineares Komplementaritätsproblem, so stehen spezialisierte Algorithmen wie Lemkes Algorithmus oder Unique Sink Orientations zur Verfügung.

Literatur

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