Lagrange-Verfahren
Joseph-Louis Lagrange
Schreibweise:
Fette Symbole bezeichnen Spaltenvektoren. Beispiel:
\[
\vx=(x_1\BIS x_n)\T
\]
Das Symbol $\nabla$ kennzeichnet den Gradienten. Beispiel:
\[
\nabla_{\vx} f(\vx^*) = \left(\abl{f(\vx^*)}{x_1}\BIS\abl{f(\vx^*)}{x_n}\right)\T
\]
Eine Optimallösung $(\vx^*,\vy^*)$ bezeichnet einen
Sattelpunkt der Lagrange-Funktion $\cL$.
Minimierungsproblem: Die Funktionen $f$ und $g_i$ seien
konvex und differenzierbar.
\[
\min_{\vx} f(\vx)\quad\text{u.d.NB.}\quad \vg(\vx)\leq\vO,\quad \vx\geq\vO
\]
Lagrange-Funktion $\cL$ mit den Lagrange-Multiplikatoren $\vy$:
\[
\cL(\vx,\vy) = f(\vx) + \vy\T\vg(\vx)
\]
Kuhn-Tucker-Bedingungen:
\begin{eqnarray*}
\nabla_{\vy} \cL(\vx^*,\vy^*)=\vg(\vx^*) {\leq} \vO &\UND&
\nabla_{\vx} \cL(\vx^*,\vy^*) \geq \vO \\
\vy^{*\textsf{T}} \nabla_{\vy} \cL(\vx^*,\vy^*) = 0 &\UND&
\vx^{*\textsf{T}} \nabla_{\vx} \cL(\vx^*,\vy^*) = 0\\
\vy^* \geq \vO &\UND&
\vx^* \geq \vO
\end{eqnarray*}
Maximierungsproblem: Die Funktionen $f$ und $g_i$ seien
konkav und differenzierbar.
\[
\max_{\vx}f(\vx)\quad\text{u.d.NB.}\quad \vg(\vx)\geq\vO,\quad \vx\geq\vO
\]
Lagrange-Funktion $\cL$ mit den Lagrange-Multiplikatoren $\vy$:
\[
\cL(\vx,\vy) = f(\vx) + \vy\T\vg(\vx)
\]
Kuhn-Tucker-Bedingungen:
\begin{eqnarray*}
\nabla_{\vy} \cL(\vx^*,\vy^*) = \vg(\vx^*) \geq \vO &\UND&
\nabla_{\vx} \cL(\vx^*,\vy^*) \leq \vO\\
\vy^{*\textsf{T}} \nabla_{\vy} \cL(\vx^*,\vy^*) = 0 &\UND&
\vx^{*\textsf{T}} \nabla_{\vx} \cL(\vx^*,\vy^*) = 0\\
\vy^* \geq \vO &\UND&
\vx^* \geq \vO
\end{eqnarray*}
Dieses Vorgehen impliziert die Nichtnegativität der
Lagrange-Multiplikatoren $\vy$!
Beachte: Alle Summanden haben das gleiche Vorzeichen, so dass z.B.
\begin{eqnarray*}
&&\vy^{*\textsf{T}}\nabla_{\vy}L(\vx^*,\vy^*) = \sum_{j=1}^m
y_j^* \abl{L}{y_j}(\vx^*,\vy^*) = 0\\
&\iff& y_j^*\,\abl{L}{y_j}(\vx^*,\vy^*) = 0 \quad (j=1,...,m)
\end{eqnarray*}
Anmerkung:
Leider lassen sich einige degenerierte Probleme nicht ausschließen.
Die Details erfährt man in der einschlägigen Literatur zur nichtlinearen
Programmierung.
