Direkt zum Inhalt

Lexikon der Mathematik: aktive-Restriktionen-Strategie

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

Angenommen, das Minimum einer Funktion f(x), f : ℝn → ℝ 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 xk ∈ ℝn : Ausgehend von einem xk, betrachtet man die Indexmenge \begin{eqnarray}{N}_{k}:=\{i|{a}_{i}^{T}\cdot {x}_{k}={b}_{i}\}\end{eqnarray}

der in xk aktiven Nebenbedingungen des Ausgangs-problems. Jetzt löst man zunächst das Ersatzproblem: Minimiere f(xk + 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 yk die Lösung dieses Problems, so minimiert man als nächstes f entlang der Geraden xk + t · yk

, 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 xk nicht aktiven Nebenbedingungen gebildet. Der so erhaltene Extremalwert tk wird verwendet, um die Anpassung von Nk sowie xk für den nächsten Iterationsschritt durchzuführen.

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

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos