spezielle Strategie bei der Lösung von Optimierungsaufgaben mit Ungleichungsrestriktionen.

Angenommen, das Minimum einer Funktion f(x), f : ℝⁿ → ℝ unter den linearen Nebenbedingungen \begin{eqnarray}\{x\in {{\mathbb{R}}}^{n}|A\cdot x\le b\}\end{eqnarray}

sei gesucht. Man berechnet nun folgendermaßen iterativ eine Folge von Punkten x_k ∈ ℝⁿ : Ausgehend von einem x_k, betrachtet man die Indexmenge \begin{eqnarray}{N}_{k}:=\{i|{a}_{i}^{T}\cdot {x}_{k}={b}_{i}\}\end{eqnarray}

der in x_k aktiven Nebenbedingungen des Ausgangs-problems. Jetzt löst man zunächst das Ersatzproblem: Minimiere f(x_k + y) unter den Nebenbedingungen \begin{eqnarray}{a}_{i}^{T}\cdot y=0\forall i\in {N}_{k}\end{eqnarray} (d. h. man betrachtet nur noch Gleichungsnebenbedingungen). Ist y_k die Lösung dieses Problems, so minimiert man als nächstes f entlang der Geraden x_k + t · y_k

, wobei der für t zulässige Bereich [0, \begin{eqnarray}\bar{t}\end{eqnarray}] gewissen weiteren Bedingungen unterliegt; letztere werden unter Verwendung spezieller Informationen über die in x_k nicht aktiven Nebenbedingungen gebildet. Der so erhaltene Extremalwert t_k wird verwendet, um die Anpassung von N_k sowie x_k für den nächsten Iterationsschritt durchzuführen.

Man beachte, daß dabei im neuen Punkt x_k+1 vorher aktive Nebenbedingungen nicht-aktiv werden können.