wesentlich auf der Verwendung von Lagrange-Multiplikatoren basierendes Verfahren zur Lösung von Optimierungsproblemen unter Nebenbedingungen.

Der Einfachheit halber betrachte man ein solches Problem nur mit Gleichungsnebenbedingun- gen, d. h. min f (x) unter den Nebenbedingungen

\begin{eqnarray}x\in M:=\{z\in {{\mathbb{R}}}^{n}|{h}_{i}(x)=0,\quad i\in I\}\end{eqnarray}

für f, h ∈ C² (ℝⁿ, ℝ) und |I| < ∞. Wir setzen h(x) ≔ (h₁(x), … ,h_|I|(x))^T. Ungleichungen können dann zum Beispiel durch Hinzunahme von Schlupfvariablen behandelt werden (Dimensionserhöhung). Um die Anwendbarkeit der Multiplikatormethode zu garantieren, werden folgende Vereinbarungen getroffen. Wir betrachten einen lokalen Minimalpunkt \(\bar{x}\) von f |_M und nehmen an, daß die lineare Unabhängigkeitsbedingung in M erfüllt ist. Der zu \(\bar{x}\) existierende Vektor von Lagrange-Multiplikatoren sei \(\bar{\lambda }\). Schließlich sei die Hessematrix \({D}^{2}L(\bar{x})\) der Lagrangefunktion \(L(x)=f(x)-\bar{\lambda }\) in \(\bar{x}\) positiv definit auf dem Tangentialraum \({T}_{\bar{x}}M\) von M in \(\bar{x}\). Diese Voraussetzungen implizieren, daß \(\bar{x}\) ein strikter lokaler Minimalpunkt von f|_M ist, der zusätzlich nicht-degeneriert ist.

Die erste Idee zur Berechnung von \(\bar{x}\) ist es, ein Optimierungsproblem ohne Nebenbedingungen zu lösen. Hierzu wird L mit einem Strafterm versehen, und die Funktion

\begin{eqnarray}\phi (x,\lambda ,\sigma ):=f(x)-\lambda \cdot h(x)+\frac{1}{2}\cdot \sigma \cdot {h}^{T}(x)\cdot h(x)\end{eqnarray}

betrachtet. Der Strafterm ist so konstruiert, daß \(\bar{x}\) nicht-degenerierter lokaler Minimalpunkt für \(x\to \phi (x,\quad \bar{\lambda },\quad \sigma )\) bleibt, sofern der Parameter σ größer als ein fester Wert \(\bar{\sigma }\gt 0\) ist. Dies liegt daran, daß die Hessematrix des Strafterms in \(\bar{x}\) eine positivsemidefinite Matrix ist, deren positive Eigenwerte Eigenvektoren im Bild von \(Dh(\bar{x})\) entsprechen.

Damit kann \(\bar{x}\) prinzipiell als lokaler Extremalpunkt der Funktion \(x\to \phi (x,\quad \bar{\lambda },\quad \sigma )\) bestimmt werden (\(\sigma \gt \bar{\sigma }\) fest). Problematisch ist die Unkenntnis der Lagrange-Multiplikatoren \(\bar{\lambda }\). Hier setzt das Verfahren an, indem es versucht, diese approximativ zu ermitteln. Dazu faßt man in φ auch λ als Variablen auf. Obige Voraussetzungen und der Satz über implizite Funktionen liefern lokal um \(\bar{\lambda }\) für jedes λ einen Minimalpunkt x(λ) der Funktion x → φ(x, λ, σ). Für die λ-Werte definiert man eine sogenannte marginale Funktion ψ(λ) ≔ φ(x(λ), λ, σ) und stellt fest, daß ψ durch \(\bar{\lambda }\) lokal maximiert wird. Dadurch sind sowohl \(\bar{x}=x(\bar{\lambda })\) als auch \(\bar{\lambda }\) durch unrestringierte Optimierungsprobleme charakterisiert. Dies benutzt man nunmehr zur Berechnung schrittweiser Näherungen. Startend von Punkten (x^o, λ⁰) ermittelt man im k-ten Schritt aus den aktuellen Approximationen (x^k, λ^k) zunächst x^k+1 als näherungsweise Minimalstelle der Abbildung x → φ(x, λ^k, σ). Anschließend wird λ^k+1 als näherungsweise Maximalstelle von λ → φ(x^k+1, λ, σ) ermittelt. Die Optimierungsschritte können wie üblich verschieden realisiert werden, etwa durch ein Newtonverfahren. Eine wichtige Rolle bei der praktischen Umsetzung spielt der Straffaktor σ, der behutsam zu wählen ist, damit die Hessematrix der Funktion → nicht schlecht konditioniert ist. Ebenso zentral ist der Umstand, daß eine Konvergenz der x^k gegen \(\bar{x}\) i.allg. nicht schneller ist als eine Konvergenz der λ^k gegen \(\bar{\lambda }\). Daher ist eine schnelle Konvergenz der Multiplikatoren wesentliche Voraussetzung für effiziente Algorithmen.