quadratische Programmierung, Theorie der Optimierungsprobleme der Form min f (x) unter den Nebenbedingungen \begin{eqnarray}x\ge 0,A\cdot x\ge b,\end{eqnarray}

wobei \begin{eqnarray}f(x)=\frac{1}{2}\cdot {x}^{T}\cdot D\cdot x+{c}^{T}\cdot x\end{eqnarray}

ein Polynom vom Grad zwei ist, und D ∈ ℝ^n×n symmetrisch, c ∈ ℝⁿ, A ∈ ℝ^m×n und b ∈ ℝ^m sind.

Das wesentliche Unterscheidungsmerkmal für die Behandlung solcher Probleme ist die Frage nach der Definitheit der Matrix D. Die Zielfunktion f ist genau dann konvex, wenn D positiv semidefinit ist. In diesem Fall lassen sich Methoden der linearen Optimierung verallgemeinern bzw. Strategien der konvexen Optimierung anwenden (etwa Innere-Punkte Methoden). Es gilt dann ebenfalls der folgende Dualitätssatz:

Seien (P) das primale Problem\begin{eqnarray}\min \{\frac{1}{2}\cdot {x}^{T}\cdot D\cdot x+{c}^{T}\cdot x,x\ge 0,A\cdot x\ge 0\},\end{eqnarray}

und (D) das duale Problem\begin{eqnarray}\begin{array}{c}\max \{-{y}^{T}\cdot D\cdot y+{b}^{T}\cdot u,u\ge 0\},\\ {A}^{T}\cdot u-2\cdot D\cdot y\le c\}.\end{array}\end{eqnarray}

Ist D symmetrisch und positiv semidefinit, so ist (P) genau dann lösbar, wenn (D) lösbar ist. In diesem Fall sind die Optimalwerte identisch.

Komplexitätstheoretisch sind konvexe quadratische Optimierungsprobleme in polynomialer Zeit lösbar, sofern Eingaben aus ℚ vorliegen und das Turingmodell betrachtet wird. Für allgemeine Matrizen D ist dies vermutlich nicht mehr richtig. Hier gilt vielmehr:

Für allgemeine Eingaben D ∈ ℚ^n×n symmetrisch, A ∈ ℚ^m×n, c ∈ ℚⁿ, b ∈ ℚ^m sind folgende Entscheidungsprobleme im Turingmodell NP-vollständig:

i) Gibt es ein x ∈ ℚⁿ \ {0}, x ≥ 0 mit x^T · D · x< 0?

ii) Gibt es ein x ∈ ℚⁿ mit A · x ≥ b und f (x) ≤ 0 (wobei f wie oben definiert sei)?

Im nichtkonvexen Fall verwendet man dann häufig Methoden der allgemeinen nichtlinearen Optimierung. Die Fragestellungen können verallgemeinert werden, indem man auch quadratische Nebenbedingungen zuläßt.