Direkt zum Inhalt

Lexikon der Mathematik: Lagrange-Newton, Verfahren von

behandelt ein Optimierungsproblem unter Nebenbedingungen, indem es dasselbe in ein Nullstellenproblem transformiert.

Gesucht sei beispielsweise min f auf der Menge \begin{eqnarray}M:=\{x\in {{\mathbb{R}}}^{n}|{h}_{i}(x)=0,i\in I\}\end{eqnarray}

mit endlicher Indexmenge I und reellwertigen Funktionen f, hiC1(ℝn). Ferner gelte die lineare Unabhängigkeitsbedingung auf ganz M.

Ist jetzt \(\bar{x}\in M\) ein kritischer Punkt von f|M mit zugehörigen Lagrange-Multiplikatoren \(\bar{\lambda }\), so ist \((\bar{x},\bar{\lambda })\) eine Nullstelle der Abbildung \begin{eqnarray}T(x,\lambda ):=\left(\begin{array}{c}{D}^{T}f(x)-\displaystyle \sum _{i\in I}{\lambda }_{i}\cdot {D}^{T}{h}_{i}(x)\\ -{h}_{i}(x),i\in I\end{array}\right).\end{eqnarray}

Das Verfahren von Lagrange-Newton wird nun angewandt, um solche Nullstellen (und damit mögliche Extremalpunkte des Ausgangsproblems) zu finden.

Dazu werden Iterationsfolgen (xk), (λk) sowie Matrizen (Ak) und (Bk) berechnet, wobei \begin{eqnarray}{A}_{k}:={D}^{2}f({x}_{k})-\displaystyle \sum _{i\in I}{\lambda }_{{i}_{k}}\cdot {D}^{2}{h}_{i}({x}_{k})\end{eqnarray}

und \begin{eqnarray}{B}_{k}:=-({D}^{T}{h}_{i}({x}_{k}),i\in I)\end{eqnarray}

ist. Man löst in jedem Schritt das System \begin{eqnarray}\begin{array}{l}\left(\begin{array}{cc}{A}_{k} & {B}_{k}\\ {B}_{k}^{T} & 0\end{array}\right)\cdot \left(\begin{array}{c}\Delta {x}_{k}\\ \Delta {\lambda }_{k}\end{array}\right)\\ \quad\quad\quad \text{}=\left(\begin{array}{c}-{D}^{T}f({x}_{k})-{B}_{k}\cdot {\lambda }_{k}\\ {h}_{i}({x}_{k}),i\in I\end{array}\right)\end{array}\end{eqnarray}

und ermittelt die neuen Iterierten gemäß \begin{eqnarray}\begin{array}{l}{x}_{k+1} := {x}_{k}+\Delta {x}_{k},\\ {\lambda }_{k+1} := {\lambda }_{k}+\Delta {\lambda }_{k}\end{array}\end{eqnarray}

(Lagrange-Newton Iteration).

Das Vorgehen läßt sich analog auf Probleme mit Ungleichungsnebenbedingungen erweitern.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

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.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.