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}

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}

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.