Benutzer:Wurzeldrei/QP

Die Quadratische Optimierung oder Quadratische Programmierung ist ein Verfahren zur Minimierung oder Maximierung einer quadratischen Zielfunktion, welche durch ein System von Nebenbedingungen beschränkt ist.

Ein Allgemeines quadratisches Programm (engl. General quadratic program oder QP) ist ein Optimierungsproblem der Form

${\begin{aligned}\min _{x}q(x)&={\frac {1}{2}}x^{T}Gx+x^{T}c\\{\text{s.t. }}A_{E}x&=b_{E}\\B_{I}x&\leq b_{I}\end{aligned}}$

wobei $G$ als symmetrisch vorausgesetzt wird. Dabei werden Gleichungsnebenbedingungen durch $A_{E}x=b_{E}$ festgelegt und Ungleichungsnebenbedingungen durch das komponentenweise zu verstehende $B_{I}x\leq b_{I}$. Aus praktischen Gründen fordert man häufig, dass G mindestens positiv semidefinit ist, da bei Indefinitheit oder negativer Definitheit kein den Nebenbedingungen entsprechendes Minimum existieren muss. Optimierungsprobleme mit strikt positiv definiten Systemmatrizen G sind spezielle konvexe Optimierungsprobleme.

Rein gleichungsbeschränkte QP

Ein Problem der Form

${\begin{aligned}\min _{x}q(x)&={\frac {1}{2}}x^{T}Gx+x^{T}c\\{\text{s.t. }}A_{E}x&=b_{E}\end{aligned}}$

heißt rein gleichungsbeschränktes QP. Lösungen $x^{\ast }$ dieses Problems erfüllen die notwendige Bedingung

$\exists \lambda ^{\ast }:{\begin{bmatrix}G&-A_{E}^{T}\\A_{E}&0\end{bmatrix}}{\begin{bmatrix}x^{\ast }\\\lambda ^{\ast }\end{bmatrix}}={\begin{bmatrix}-c\\b_{E}\end{bmatrix}}$,

die eine direkte Folgerung aus den allgemeinen Bedingungen 1. Art sind.