Blog

2 – Grundlagen der Optimierung

In diesem Abschnitt wiederholen wir noch einmal wichtige theoretische Aussagen, vor allem notwendige Bedingungen für Extrema im {\mathbb{R}^n}. In verallgemeinerter Form werden wir auch bei der Optimierung in Funktionenräumen dieselben Techniken verwenden: Nullsetzen von Ableitungen und Behandlung von Nebenbedingungen mithilfe von Lagrange-Multiplikatoren.

2.1 Partielle Differenzierbarkeit und Gradient

Beginnen wir mit der Differentiation von Funktionen in mehreren Veränderlichen.

Sei D \subset {\mathbb{R}^n} offen, f:D \to \mathbb{R}, x \mapsto f\left( x \right) = f\left( {{x_1}, \ldots ,{x_n}} \right) eine multivariante Funktion. Sei nun a = \left( {{a_1}, \ldots ,{a_n}} \right) \in D fest gewählt. Dann ist die univariante Funktion (nur eine Größe variabel) {x_i} \mapsto f\left( {{a_1}, \ldots ,{a_{i-i}},{x_i},{a_{i+1}}, \ldots ,{a_n}} \right) eine partielle Funktion von f\left( x \right).

Ableitung nach {x_i}:

{\left. {\frac{{\partial f}}{{\partial {x_i}}}} \right|_{x = a}} = \mathop {\lim }\limits_{t \to 0} \frac{{f\left( {{a_1}, \ldots ,{a_i}+t, \ldots ,{a_n}} \right)-f\left( a \right)}}{t}

{\left. {\frac{{\partial f}}{{\partial {x_i}}}} \right|_{x = a}} = :\frac{{\partial f}}{{\partial {x_i}}}\left( a \right) = :{f_{x,i}}\left( a \right)

Dies ist die partielle Ableitung von f nach {x_i} an der Stelle a. Andere Schreibweisen, z.B. n = 3 mit f\left( {x,y,z} \right) statt f\left( {{x_1},{x_2},{x_3}} \right):

\frac{{\partial f}}{{\partial x}} = {f_x},\quad \frac{{\partial f}}{{\partial y}} = {f_y},\quad \frac{\partial }{{\partial x}}\left( {\frac{{\partial f}}{{\partial y}}} \right) = {f_{xy}} = {f_{yx}}

f heißt (stetig) partiell differenzierbar, wenn alle partiellen Ableitungen existieren (und stetig sind).

Die partiellen Ableitungen können zusammengefasst und als Vektor geschrieben werden. Diesen nennt man den Gradienten von f und schreibt:

\operatorname{grad} \left( {f\left( x \right)} \right) = \left( {\begin{array}{*{20}{c}}{\frac{{\partial f}}{{\partial {x_1}}}\left( x \right)} \\ \vdots \\ {\frac{{\partial f}}{{\partial {x_n}}}\left( x \right)} \end{array}} \right) = {\left( {\nabla f\left( x \right)} \right)^T}


Beispiel 2.1: Gradient

f\left( {x,y,z} \right) = 3{x^2}+\sin \left( {yz} \right)

\nabla f\left( {x,y,z} \right) = \left( {\begin{array}{*{20}{c}}{6x}&{\cos \left( {yz} \right)z}&{\cos \left( {yz} \right)y} \end{array}} \right)

{C^k}\left( D \right): = \left\{ {f:D \to \mathbb{R};\quad f\:{\text{k-mal stetig partiell differenzierbar}}} \right\}

{C^0}\left( D \right): = \left\{ {f:D \to \mathbb{R};\quad f\:{\text{stetig}}} \right\}

{C^1}\left( D \right): = \left\{ {f:D \to \mathbb{R};\quad f\:{\text{in alle Richtungen partiell stetig differenzierbar}}} \right\}

Beispiel für eine stetige Funktion, dessen Ableitung nicht stetig ist:

f\left( x \right) = \left\{ {\begin{array}{*{20}{c}}{{x^2}\cos \left( {\frac{1}{x}} \right)}&{x \ne 0} \\ 0&{x = 0} \end{array}} \right.

\Rightarrow \quad {f^\prime }\left( x \right) = \left\{ {\begin{array}{*{20}{c}}{2x\cos \left( {\frac{1}{x}} \right)+\sin \left( {\frac{1}{x}} \right)}&{x \ne 0} \\ 0&{x = 0} \end{array}} \right.

2.2 Totale Differenzierbarkeit und Tangentialebene

Hier zunächst eine Definition.

Definition 2.2: Totale Differenzierbarkeit

f:D \to \mathbb{R} heißt (total) differenzierbar in {\vec x_0} \in D \subset {\mathbb{R}^n}, wenn die Funktion in diesem Punkt linear durch eine Tangentialebene approximierbar ist, d.h. wenn es einen Vektor \vec a \in {\mathbb{R}^n} gibt mit

f\left( {\vec x} \right) = \underbrace {f\left( {{{\vec x}_0}} \right)+{{\vec a}^T}\left( {\vec x-{{\vec x}_0}} \right)}_{Ebenengleichung}+o\left( {{{\left\| {\vec x-{{\vec x}_0}} \right\|}_2}} \right)

\Leftrightarrow \quad \mathop {\lim }\limits_{x \to {x_0}} \frac{{{{\left\| {f\left( {\vec x} \right)-f\left( {{{\vec x}_0}} \right)-{{\vec a}^T}\left( {\vec x-{{\vec x}_0}} \right)} \right\|}_2}}}{{{{\left\| {\vec x-{{\vec x}_0}} \right\|}_2}}} = 0

Ist f in jedem Punkt \vec x \in D differenzierbar, dann heißt f differenzierbar auf D.

Dabei steht das Landau-Symbol o\left( {{{\left\| {\vec x-{{\vec x}_0}} \right\|}_2}} \right) für einen Ausdruck A = A\left( {\vec x} \right) mit \frac{{A\left( {\vec x} \right)}}{{{{\left\| {\vec x-{{\vec x}_0}} \right\|}_2}}} \to 0 für \vec x \to {\vec x_0}. Zum Beispiel ist \left\| {\vec x-{{\vec x}_0}} \right\|_2^2 = o\left( {{{\left\| {\vec x-{{\vec x}_0}} \right\|}_2}} \right). Bedeutung: Der quadratische Rest geht schneller gegen 0 als der Abstand. Statt der euklidischen Norm könnte man hier auch jede andere verwenden, denn im {\mathbb{R}^n} ist

{\left\| {{{\vec x}_n}-{{\vec x}_0}} \right\|_2}\xrightarrow{{n \to \infty }}0\quad \Leftrightarrow \quad \left\| {{{\vec x}_n}-{{\vec x}_0}} \right\|\xrightarrow{{n \to \infty }}0

für jede beliebige Norm.

Ist f in {\vec x_0} (total) differenzierbar, schreibt man im Kontext der obigen Definition {f^\prime }\left( {{{\vec x}_0}} \right) statt \vec a. Jede in {\vec x_0} differenzierbare Funktion ist dort auch stetig und partiell differenzierbar. Es ist dann stets

{f^\prime }\left( {{{\vec x}_0}} \right) = \nabla f\left( {{{\vec x}_0}} \right) = \operatorname{grad} f\left( {{{\vec x}_0}} \right)

(Im Folgenden wollen wir \operatorname{grad} f und \nabla f synonym verwenden.) Umgekehrt folgt aus der Existenz der partiellen Ableitungen noch nicht die Differenzierbarkeit von f. Dazu muss man noch zusätzlich Stetigkeit voraussetzen.

Satz 2.3: totale und stetig partielle Differenzierbarkeit

Wenn f:D \to \mathbb{R} auf der offenen Menge D \subset {\mathbb{R}^n} stetig partiell differenzierbar ist, dann ist f auf D total differenzierbar.

Geometrisch bedeutet die totale Differenzierbarkeit, dass der Graph der Funktion f im Punkt \left( {{{\vec x}_0},f\left( {{{\vec x}_0}} \right)} \right) durch die Tangentialebene

z = f\left( {{{\vec x}_0}} \right)+{\vec a^T}\left( {\vec x-{{\vec x}_0}} \right) = f\left( {{{\vec x}_0}} \right)+{\vec a^T}\vec x-{\vec a^T}{\vec x_0}

approximiert werden kann. Der Normalenvektor der Tangentialebene ist durch

\left( {-\nabla f\left( {{{\vec x}_0}} \right),1} \right) \in {\mathbb{R}^{n+1}} gegeben. Die Gleichung der Tangentialebene lässt sich umformen zu

z-{\vec a^T}\vec x = f\left( {{{\vec x}_0}} \right)-{\vec a^T}{\vec x_0} = \operatorname{const}.

Veranschaulichung:
tangentialebene-veranschaulichung-beispiel

Für unsere Zwecke und wegen des letzten Satzes ist der Begriff der stetigen partiellen Differenzierbarkeit eigentlich ausreichend. Wir haben die totale Differenzierbarkeit dennoch aufgeführt wegen ihrer geometrischen Anschaulichkeit und weil sie einen Weg zu einer abstrakten Differentialrechnung auf Banachräumen öffnet. Diese abstrakte Form der Ableitung heißt Fréchet-Ableitung und spielt in der funktionalanalytischen Theorie der Variationsrechnung eine große Rolle.

2.3 Richtungsableitung

Partielle Ableitungen zeigen immer in die Richtung einer der Koordinatenachsen. Wir können aber auch in beliebige Richtungen ableiten:

\vec v \in {\mathbb{R}^n},\quad {\partial _{\vec v}}f\left( {\vec x} \right): = {D_{\vec v}}f\left( {\vec x} \right): = \mathop {\lim }\limits_{t \to 0} \frac{{f\left( {\vec x+t\vec v} \right)-f\left( {\vec x} \right)}}{t}

Wenn \left| {\vec v} \right| = 1 ist, heißt {D_{\vec v}}f\left( {\vec x} \right) die Richtungsableitung von f an der Stelle \vec x in Richtung \vec v.

Tatsächlich genügt im Wesentlichen die Kenntnis der partiellen Ableitungen, um auch alle Richtungsableitungen zu kennen.

Satz 2.4: Richtungsableitungen

Wenn f:D \to \mathbb{R} auf der offenen Menge D \subset {\mathbb{R}^n} total differenzierbar ist (insbesondere, wenn f stetig partiell differenzierbar ist), dann hat man für jeden Vektor \vec v \in {\mathbb{R}^n} mit \vec v \ne \vec 0:

{D_{\vec v}}f\left( {\vec x} \right) = \left\langle {\operatorname{grad} f\left( {\vec x} \right),\vec v} \right\rangle = \sum\limits_{i = 1}^n {{f_{x,i}}\left( {\vec x} \right){v_i}}

Satz für das Skalarprodukt:

{D_{\vec v}}f\left( {\vec x} \right) = \left\langle {\operatorname{grad} f\left( {\vec x} \right),\vec v} \right\rangle = {\left\| {\operatorname{grad} f\left( {\vec x} \right)} \right\|_2}{\left\| {\vec v} \right\|_2}\cos \varphi ,\quad \varphi = \sphericalangle \left( {\operatorname{grad} f\left( {\vec x} \right),\vec v} \right)

{D_{\vec v}}f\left( {\vec x} \right) ist maximal, wenn \vec v = \frac{{\operatorname{grad} f\left( {\vec x} \right)}}{{\left\| {\operatorname{grad} f\left( {\vec x} \right)} \right\|}}.

Man sieht: Der steilste Anstieg der Funktion f geschieht in Richtung des Gradienten. Entsprechend zeigt -\operatorname{grad} f\left( {\vec x} \right) in Richtung des steilsten Abfalls der Funktionswerte. Diese Beobachtung ist Grundlage des bekanntesten Verfahrens der Optimierung im {\mathbb{R}^n}, des Gradientenverfahrens, auch Methode des steilsten Abstiegs genannt. Dieses ist ein iteratives Verfahren, das eine Folge von Punkten {\vec x_0},{\vec x_1}, \ldots \in {\mathbb{R}^n} produziert, von der man hofft, dass sie gegen ein lokales Minimum der Funktion f konvergiert. Die Folge wird definiert über die Beziehung:

{\vec x_{i+1}} = {\vec x_i}-\lambda \operatorname{grad} f\left( {{{\vec x}_i}} \right)

Man geht also von jedem Iterationspunkt aus weiter in Richtung des steilsten Abfalls von Funktionswerten, wobei \lambda eine zu wählende reelle Schrittweite ist.

2.4 Lokale und globale Extrema ohne Nebenbedingung

Definition 2.5: Lokales und globales Minimum und Maximum

Sei \hat \vec x \in D \subset {\mathbb{R}^n}. f \in {C^1}\left( D \right) ist stationär in \hat \vec x genau dann, wenn \operatorname{grad} f\left( {\hat \vec x} \right) = 0.

f hat ein globales Minimum in \hat \vec x, genau dann, wenn f\left( {\hat \vec x} \right) \leq f\left( {\vec x} \right)\quad \forall \vec x \in D.

f hat ein lokales Minimum in \hat \vec x, genau dann, wenn es eine Umgebung {U_r}\left( {\hat \vec x} \right): = \left\{ {\vec x \in {\mathbb{R}^n}:} \right\}{\left\| {\vec x-\hat \vec x} \right\|_2} < r gibt mit f\left( {\hat \vec x} \right) \leq f\left( {\vec x} \right)\quad \forall \vec x \in {U_r} \cap D.

Die Definition für Maxima und Maximalstellen sind analog. Ein Extremum ist ein Minimum oder ein Maximum.

Der folgende Satz gibt eine notwendige Bedingung für eine Extremalstelle.

Satz 2.6: Lokale Extrema ohne Nebenbedingung

Es sei f:{U_r}\left( {\hat \vec x} \right) \to \mathbb{R} eine {C^1}-Funktion. Falls \hat \vec x eine lokale Extremstelle in D ist, dann folgt daraus \operatorname{grad} f\left( {\hat \vec x} \right) = 0. Dies gilt nur, wenn D eine offene Menge ist, da bei einem Minimum auf dem Rand der Gradient nicht 0 sein muss.


Beweis:

Nach der Definition der Richtungsableitung in Satz 2.4 darf es an einer Extremalstelle \hat \vec x keine Auf- oder Abstiegsrichtung geben. Wäre nämlich \operatorname{grad} f\left( {\hat \vec x} \right) = \vec v \ne 0, dann hätte die Funktion t \mapsto f\left( {\hat \vec x+t\vec v} \right) an der Stelle t = 0 die Ableitung {\left. {{D_{\vec v}}f\left( {\vec x} \right)} \right|_{\vec x = \hat \vec x}} = \left\| {\vec v} \right\|_2^2 und könnte dort somit kein Extremum haben.

Der Satz schränkt die Kandidatenmenge für Extremalstellen im Inneren des Definitionsbereichs von f auf die stationären Stellen ein. Löst man das im Allgemeinen nichtlineare Gleichungssystem \operatorname{grad} f\left( {\vec x} \right) = 0, so befinden sich die lokalen (und damit auch insbesondere die globalen) Extrema innerhalb der Lösungsmenge. Umgekehrt ist aber nicht jede stationäre Stelle ein Extremum. Ist sie es nicht, nennt man sie einen Sattelpunkt.

Ob man das Gleichungssystem f\left( {\vec x} \right) = 0 praktisch tatsächlich lösen kann, steht freilich auf einem anderen Blatt. Schafft man es tatsächlich, dann kann man den folgenden Satz heranziehen, um festzustellen, ob ein Kandidat auch tatsächlich ein Extremum ist. Um diesen Satz prägnanter formulieren zu können, führen wir vorher noch die folgende Bezeichnung ein:

Für ein offenes D \subset {\mathbb{R}^n} heißt die für f \in {C^2}\left( D \right) definierte Matrix

{H_f}\left( {\vec x} \right) = \left( {\begin{array}{*{20}{c}}{{f_{{x_1},{x_1}}}\left( {\vec x} \right)}& \ldots &{{f_{{x_1},{x_n}}}\left( {\vec x} \right)} \\ \vdots & \ddots & \vdots \\ {{f_{{x_n},{x_1}}}\left( {\vec x} \right)}& \ldots &{{f_{{x_n},{x_n}}}\left( {\vec x} \right)} \end{array}} \right)

Hesse-Matrix von f in \vec x \in D.

Die Hesse-Matrix ist die Verallgemeinerung der zweiten Ableitung für Funktionen in mehreren Veränderlichen. Bekanntlich hat eine {C^2}-Funktion f:\mathbb{R} \to \mathbb{R} eine Minimalstelle \hat x, wenn

{f^\prime }\left( {\hat x} \right) = 0 und {f^{\prime \prime }}\left( {\hat x} \right) > 0.

Für Funktionen in n Variablen verallgemeinert sich das:

{f^\prime }\left( {\hat x} \right) = 0 entspricht \operatorname{grad} f\left( {\hat \vec x} \right) = 0

und {f^{\prime \prime }}\left( {\hat x} \right) > 0 entspricht {H_f}\left( {\hat \vec x} \right) ist positiv definit.

Eine symmetrische Matrix A \in {\mathbb{R}^{n \times n}} ist positiv definit genau dann wenn {\vec x^T}A\vec x \geq 0\quad \forall \vec x \in {\mathbb{R}^n}. Dabei darf = 0 nur gelten, wenn \vec x = 0 ist.

Wenn stattdessen {\vec x^T}A\vec x < 0\:\:\forall \vec x \ne 0 gilt, heißt A negativ definit. Gibt es sowohl einen Vektor \vec x mit {\vec x^T}A\vec x > 0 als auch einen Vektor \vec y mit {\vec y^T}A\vec y < 0, dann heißt die symmetrische Matrix A indefinit.

Satz 2.7: Hinreichende Bedingung für lokale Extrema ohne Nebenbedingung

Es sei f:{U_r}\left( {\hat \vec x} \right) \to \mathbb{R} eine {C^2}-Funktion und \hat \vec x ein stationärer Punkt von f. Dann folgt:

{H_f}\left( {\hat \vec x} \right) positiv definit: lokales Minimum

{H_f}\left( {\hat \vec x} \right) negativ definit: lokales Maximum

{H_f}\left( {\hat \vec x} \right) indefinit: Sattelpunkt


Beweis:

Der Sachverhalt wird einsichtig, wenn man nach der mehrdimensionalen Taylorformel f in \hat \vec x durch eine Schmiegequadrik approximiert: Zu jedem \vec x \in {U_r}\left( {\hat \vec x} \right) gibt es ein {\vec \xi _x} auf der Strecke von \vec x nach \hat \vec x, so dass

f\left( {\vec x} \right) = f\left( {\hat \vec x} \right)+\left\langle {\operatorname{grad} f\left( {\hat \vec x} \right),\left( {\vec x-\hat \vec x} \right)} \right\rangle +{\left( {\vec x-\hat \vec x} \right)^T}{H_f}\left( {{{\vec \xi }_x}} \right)\left( {\vec x-\hat \vec x} \right)

Da \hat \vec x ein stationärer Punkt ist, gilt \operatorname{grad} f\left( {\hat \vec x} \right) = 0 und damit auch \left\langle {\operatorname{grad} f\left( {\hat \vec x} \right),\left( {\vec x-\hat \vec x} \right)} \right\rangle = 0. Wir erhalten also:

f\left( {\vec x} \right) = f\left( {\hat \vec x} \right)+{\left( {\vec x-\hat \vec x} \right)^T}{H_f}\left( {{{\vec \xi }_x}} \right)\left( {\vec x-\hat \vec x} \right)

Wenn \hat \vec x ein lokales Minimum ist, muss also gelten: {\left( {\vec x-\hat \vec x} \right)^T}{H_f}\left( {{{\vec \xi }_x}} \right)\left( {\vec x-\hat \vec x} \right) > 0. Dies ist genau dann erfüllt, wenn {H_f}\left( {\hat \vec x} \right) negativ definit ist, da dann aufgrund der Stetigkeit der zweiten Ableitung auch {H_f}\left( {{{\vec \xi }_x}} \right) negativ definit ist. Analoges gilt für Maximum und Sattelpunkt.

2.5 Extremum mit Gleichungs-Nebenbedingung

Selten wird in der Praxis nach einem Extremum gefragt, ohne dass weitere einschränkende Nebenbedingungen gestellt werden. Wir betrachten zuerst Nebenbedingungen in Gleichungsform:

Sei U \subset {\mathbb{R}^n} offen, f \in {C^1}\left( U \right), {g_1}, \ldots ,{g_k} \in {C^1}\left( {{\mathbb{R}^n}} \right). Wir suchen das Minimum von f\left( {\vec x} \right) unter der Nebenbedingung {g_1}\left( {\vec x} \right) = \ldots = {g_k}\left( {\vec x} \right) = 0, also:

f\left( {\vec x} \right)\mathop = \limits^! \operatorname{Extr} .\quad udNB\quad {g_1}\left( {\vec x} \right) = \ldots = {g_k}\left( {\vec x} \right) = 0\quad \quad \quad \quad \left( 1 \right)

Die Nebenbedingungen definieren eine Teilmenge von U:

N: = \left\{ {\vec x \in U:{g_1}\left( {\vec x} \right) = \ldots = {g_k}\left( {\vec x} \right) = 0} \right\}

\hat \vec x löst das Minimierungsproblem mit Nebenbedingung genau dann, wenn es eine Umgebung {U_r}\left( {\hat \vec x} \right) gibt mit f\left( {\hat \vec x} \right) \leq f\left( {\vec x} \right)\:\:\:\forall \vec x \in {U_r}\left( {\hat \vec x} \right) \cap N.

Sehen wir uns dazu erst einmal eine einzige Nebenbedingung an. Wie wir wissen, zeigt der (negative) Gradient einer Funktion in die Richtung des steilsten Anstiegs (Abstiegs) von Funktionswerten. Im folgenden Bild hat \operatorname{grad} f\left( {\vec b} \right) einen Anteil orthogonal zu \operatorname{grad} g\left( {\vec b} \right) und damit tangential zur Höhenlinie (Niveaulinie, contour line) g = 0:

restringierte-optimierung-nebenbedingung-gleichung

Das bedeutet, dass man längs der Höhenlinie g = 0 noch zu Werten f\left( {\vec x} \right) < f\left( {\vec b} \right) und f\left( {\vec x} \right) > f\left( {\vec b} \right) kommt. Also kann \vec b kein lokales Extremum sein. Anders im Punkt \vec a: Dort sind die Gradienten \operatorname{grad} f\left( {\vec a} \right) und \operatorname{grad} g\left( {\vec a} \right) kollinear. Die Höhenlinien von g und f berühren sich tangential. Von diesem Punkt aus gelangt man zu größeren oder kleineren Funktionswerten von f nur dann, wenn man die Nebenbedingung g = 0 verlässt. \vec a ist somit ein lokales Extremum.

Der eben entwickelten Anschauung nach erwartet man eine Aussage der Form (noch ganz ohne Voraussetzungen formuliert): “Ist \hat \vec x ein lokales Extremum von f unter der Nebenbedingung g\left( {\vec x} \right) = 0, dann gibt es ein \lambda \in \mathbb{R} so, dass \nabla f\left( {\hat \vec x} \right) = \lambda \nabla g\left( {\hat \vec x} \right).”

Im folgenden Satz wird diese Aussage präzise formuliert, und zwar gleich für den Fall mehrerer Nebenbedingungen.

Satz 2.8: Lagrange-Multiplikatoren

Sei U \subset {\mathbb{R}^n} offen und f:U \to \mathbb{R} sowie g = \left( {{g_1}, \ldots ,{g_k}} \right):{\mathbb{R}^n} \to {\mathbb{R}^k} seien {C^1}-Funktionen. Ist \hat \vec x ein lokales Extremum von f unter der Nebenbedingung {g_1}\left( {\vec x} \right) = \ldots = {g_k}\left( {\vec x} \right) = 0 und sind weiterhin die Gradienten \nabla {g_1}\left( {\hat \vec x} \right), \ldots ,\nabla {g_k}\left( {\hat \vec x} \right) linear unabhängig, dann gibt es einen Vektor \left( {{\lambda _1}, \ldots ,{\lambda _k}} \right) \in {\mathbb{R}^k}, die sogenannten Lagrange-Multiplikatoren, so dass

\nabla f\left( {\hat \vec x} \right) = \sum\limits_{i = 1}^k {{\lambda _i}\nabla {g_i}\left( {\hat \vec x} \right)} .\quad \quad \quad \quad \left( 2 \right)

Mit der Lagrange-Funktion

L\left( {\vec x,\vec \lambda } \right): = f\left( {\vec x} \right)+{\vec \lambda ^T}g\left( {\vec x} \right)

lässt sich dies schreiben als {\nabla _{\vec x}}L\left( {\vec x,\vec \lambda } \right) = 0, wobei {\nabla _{\vec x}} bedeutet, dass der Gradient nur bezüglich \vec x genommen wird.

Die Bedingung \nabla f\left( {\hat \vec x} \right) = \sum\limits_{i = 1}^k {{\lambda _i}\nabla {g_i}\left( {\hat \vec x} \right)} besagt, dass man zur Vergrößerung oder Verkleinerung von Funktionswerten f von \hat \vec x aus in eine Richtung gehen müsste, die notwendig mindestens eine Nebenbedingung verletzen würde.

Vorausgesetzt wird die lineare Unabhängigkeit der Gradienten im lokalen Extremum. Dies nennt man Regularitätsbedingung. Die Regularitätsbedingung wird beim Beweis des Satzes benötigt, um zu zeigen, dass man im Extremum \hat \vec x “die Nebenbedingungen linearisieren” (durch den Tangentialraum ersetzen) kann.

Der Satz gibt eine notwendige Bedingung für lokale Extrema \hat \vec x, die der Regularitätsbedingung genügen. Ex könnte jedoch durchaus lokale Extrema geben, die der Regularitätsbedingung nicht genügen. Für solche Extrema lässt sich im Allgemeinen die Existenz von Lagrange-Multiplikatoren nicht beweisen.

Aus n Unbekannten {x_i},\:i = 1, \ldots ,n und k Nebenbedingungen {g_1} = \ldots = {g_k} = 0 erhalten wir so n Gleichungen \nabla f = \sum\limits_{i = 1}^k {{\lambda _i}\nabla {g_i}} und k Gleichungen für die Nebenbedingungen. Insgesamt haben wir also n+k Gleichungen und n+k Unbekannte. Das resultierende nichtlineare Gleichungssystem kann z.B. mit Newton numerisch gelöst werden. Nicht reguläre Stellen müssen daneben noch gesondert untersucht werden.

Beispiel 2.9: Lagrange-Multiplikatoren

Der Quader \left( {-x,x} \right) \times \left( {-y,y} \right) \times \left( {-z,z} \right) hat das Volumen f\left( {x,y,z} \right) = 2x \cdot 2y \cdot 2z = 8xyz. Gesucht wird das Maximum von f\left( {x,y,z} \right) udNB \frac{{{x^2}}}{{{a^2}}}+\frac{{{y^2}}}{{{b^2}}}+\frac{{{z^2}}}{{{c^2}}}-1 = g\left( x \right) = 0. Der Quader soll also innerhalb des durch a, b und c festgelegten Ellipsoids liegen.

Es muss das folgende Gleichungssystem ausgewertet werden:

\nabla f+\lambda \nabla g = 0

g\left( x \right) = 0

Wir erhalten daraus die Gleichungen:

{f_x}+\lambda {g_x} = 8yz+\lambda \frac{{2x}}{{{a^2}}} = 0

{f_y}+\lambda {g_y} = 8xz+\lambda \frac{{2y}}{{{b^2}}} = 0

{f_z}+\lambda {g_z} = 8xy+\lambda \frac{{2z}}{{{c^2}}} = 0

g = \frac{{{x^2}}}{{{a^2}}}+\frac{{{y^2}}}{{{b^2}}}+\frac{{{z^2}}}{{{c^2}}}-1 = 0

Dies sind 4 Gleichungen für 4 Unbekannte, nämlich x, y, z und \lambda. Wir können auflösen:

\lambda \frac{{{x^2}}}{{{a^2}}} = \lambda \frac{{{y^2}}}{{{b^2}}} = \lambda \frac{{{z^2}}}{{{c^2}}} = -4xyz

Es gilt \lambda \ne 0, da sonst das Volumen 0 wäre. Wir kürzen:

\frac{{{x^2}}}{{{a^2}}} = \frac{{{y^2}}}{{{b^2}}} = \frac{{{z^2}}}{{{c^2}}}

3\frac{{{x^2}}}{{{a^2}}} = 1\quad \Rightarrow \quad x = \frac{a}{{\sqrt 3 }}

\frac{{{y^2}}}{{{b^2}}} = \frac{{{x^2}}}{{{a^2}}} = \frac{{\frac{{{a^2}}}{3}}}{{{a^2}}} = \frac{1}{3}\quad \Rightarrow \quad y = \frac{b}{{\sqrt 3 }}\quad \Rightarrow \quad z = \frac{c}{{\sqrt 3 }}

2.6 Extremum mit Ungleichungs-Nebenbedingung

Nebenbedingungen kommen nicht nur in Gleichungsform vor, sondern auch als Ungleichungen. Wir haben dann ein Problem der Form:

Sei U \subset {\mathbb{R}^n} offen und f:U \to \mathbb{R}, g = \left( {{g_1}, \ldots ,{g_k}} \right):{\mathbb{R}^n} \to {\mathbb{R}^k} und h = \left( {{h_1}, \ldots ,{h_p}} \right):{\mathbb{R}^n} \to {\mathbb{R}^p} seien {C^1}-Funktionen.

Minimierungsaufgabe:

\mathop {\min }\limits_{\vec x \in U} f\left( {\vec x} \right)\quad udNB\quad g\left( {\vec x} \right) = 0,\quad h\left( {\vec x} \right) \leq 0\quad \quad \quad \quad \left( 3 \right)

Nebenbedingung:

{g_1}\left( {\vec x} \right) = \ldots = {g_k}\left( {\vec x} \right) = 0\quad \Rightarrow \quad g = \left( {\begin{array}{*{20}{c}}{{g_1}\left( {\vec x} \right)} \\ \vdots \\ {{g_k}\left( {\vec x} \right)} \end{array}} \right) = 0

{h_1}\left( {\vec x} \right) = \ldots = {h_p}\left( {\vec x} \right) \leq 0\quad \Rightarrow \quad h = \left( {\begin{array}{*{20}{c}}{{h_1}\left( {\vec x} \right)} \\ \vdots \\ {{h_p}\left( {\vec x} \right)} \end{array}} \right) \leq 0

Hier ist h\left( {\vec x} \right) \leq 0 komponentenweise zu lesen (Vektoren können nicht geordnet werden).

Menge der Punkte, die alle Nebenbedingungen erfüllen:

S: = \left\{ {\vec x \in U;\quad g\left( {\vec x} \right) = 0;\quad h\left( {\vec x} \right) \leq 0} \right\}

Zur Veranschaulichung betrachten wir zunächst eine einzige Nebenbedingung in Ungleichungsform und sehen uns dazu die folgende Skizze an:

restringierte-optimierung-nebenbedingung-ungleichung

Offenbar kommt es hier darauf an, welche Art von Extremum wir suchen. Wenn f minimiert werden soll, so haben wir in \vec a ein lokales Minimum gefunden: Zur Verkleinerung von Funktionswerten über f\left( {\vec a} \right) hinaus müsste man von \vec a in Richtung des negativen Gradienten -\operatorname{grad} f\left( {\vec a} \right) gehen. Dann würde man aber den zulässigen Bereich verlassen.

In Punkt \vec b hingegen hat -\operatorname{grad} f\left( {\vec b} \right) einen zu \operatorname{grad} g\left( {\vec b} \right) orthogonalen Anteil. Man kann also den Funktionswert von f\left( {\vec b} \right) durch einen Schritt in einer Richtung verringern, der die Nebenbedingung nicht verletzt.

Der Beweis des folgenden Satzes beruht wiederum auf einer Linearisierung von Nebenbedingungen, allerdings nur jener, die im Optimum zum Tragen kommen. Dazu definieren wir wie folgt.

Definition 2.10: Regularität von Nebenbedingungen

Es seien U \subset {\mathbb{R}^n} offen und f:U \to \mathbb{R}, g = \left( {{g_1}, \ldots ,{g_k}} \right):{\mathbb{R}^n} \to {\mathbb{R}^k} und h = \left( {{h_1}, \ldots ,{h_p}} \right):{\mathbb{R}^n} \to {\mathbb{R}^p} seien {C^1}-Funktionen. Es sei weiterhin

S: = \left\{ {\vec x \in U;\quad g\left( {\vec x} \right) = 0;\quad h\left( {\vec x} \right) \leq 0} \right\}.

Für jedes \vec x \in S sei

J\left( {\vec x} \right): = \left\{ {j \in \left\{ {1, \ldots ,p} \right\};\quad {h_j}\left( {\vec x} \right) = 0} \right\}

die Indexmenge aktiver Ungleichungsnebenbedingungen.

Ein \vec x \in S heißt regulär, wenn die Gradienten \nabla {g_i}\left( {\vec x} \right) und \nabla {h_j}\left( {\vec x} \right) linear unabhängig sind für i = 1, \ldots ,k,\:\:j \in J\left( {\vec x} \right).

In der Menge J\left( {\vec x} \right) werden die Indizes aller in \vec x aktiven Nebenbedingungen versammelt. Wenn j \notin J\left( {\vec x} \right) ist, bedeutet dies {h_j}\left( {\vec x} \right) < 0. Wegen der Stetigkeit von {h_j} bleibt diese Nebenbedingung dann auch noch in einer Umgebung von \vec x erfüllt.

Satz 2.11: Satz von Kuhn-Tucker

Es seien U \subset {\mathbb{R}^n} offen und f:U \to \mathbb{R}, g = \left( {{g_1}, \ldots ,{g_k}} \right):{\mathbb{R}^n} \to {\mathbb{R}^k} und h = \left( {{h_1}, \ldots ,{h_p}} \right):{\mathbb{R}^n} \to {\mathbb{R}^p} seien {C^1}-Funktionen. Es sei weiterhin

S: = \left\{ {\vec x \in U;\quad g\left( {\vec x} \right) = 0;\quad h\left( {\vec x} \right) \leq 0} \right\}.

\hat \vec x sei Lösung der Minimierungsaufgabe. Dann existieren {\lambda _1}, \ldots ,{\lambda _k},{\mu _1}, \ldots ,{\mu _p} so, dass

\nabla f\left( {\hat \vec x} \right)+\sum\limits_{i = 1}^k {{\lambda _i}\nabla {g_i}\left( {\hat \vec x} \right)} +\sum\limits_{j = 1}^p {{\mu _j}\nabla {h_j}\left( {\hat \vec x} \right)} = 0,\quad {\mu _j} \geq 0,\quad {\mu _j}{h_j}\left( {\hat \vec x} \right) = 0,\quad j = 1, \ldots ,p

Die Bedingung {\mu _j}{h_j}\left( {\hat x} \right) = 0 bedeutet, dass der Multiplikator {\mu _j}, der zu einer inaktiven Nebenbedingung {h_j}\left( {\hat x} \right) gehört, verschwindet.

Der Satz von Kuhn-Tucker ist offensichtlich eine Verallgemeinerung des Satzes 2.8 über die Lagrange-Multiplikatoren und beinhaltet diesen als Spezialfall.

Die Frage nach hinreichenden Bedingungen für Extrema unter Nebenbedingungen lassen wir an dieser Stelle offen. Sie wird in allgemeinerem Rahmen bei der Optimierung in Funktionenräumen wieder aufgegriffen.

Leave a Reply

Close Menu