Optimierung - Optimierung

Optimierung

Ziel dieser Lektion ist es die nichtlineare Optimierung auf Funktionen mit mehreren Variablen zu erweitern. Dazu wird die Theorie der Eigenwerte aus der linearen Algebra benötigt. Neben der theoretischen Abhandlung sollen hier auch algorithmische Ansätze besprochen werden. Ein wesentlicher Punkt ist die Suche nach Extremwerten unter der Einhaltung von gewissen Nebenbedingungen. Als notwendige Kriterien werden die Lagrange–Methode sowie die Karush–Kuhn–Tucker Bedingungen besprochen.

Lokale Extrema von reellen Funktionen

Wir erinnern uns, dass für Funktionen mit einer Veränderlichen eine notwendige Bedingung für lokale Extrema darin besteht, dass die erste Ableitung verschwindet, i.e. durch Lösen der Gleichung ${\textstyle f^{\prime }\left(x\right)=0}$ erhält man mögliche Kandidaten für ein Maximum bzw. ein Minimum einer Funktion.
Beispiel 6: Betrachte das Polynom aus Beispiel 4:
${\textstyle p(x)=-x^{4}+x^{3}+4x^{2}-4x+2}$
Ableitung liefert
${\textstyle p^{\prime }(x)=-4x^{3}+3x^{2}+8x-4}$
Die Suche nach Nullstellen von ${\textstyle p^{\prime }(x)}$ liefert potenzielle Kandidaten für lokale Maxima und Minima. Für ein Polynom dritten Grades gibt es geschlossene Formeln, um die Nullstellen zu bestimmen, man erhält näherungsweise
${\textstyle x_{1}=-1.3263,x_{2}=1.6073,x_{3}=0.4691}$ Der Vergleich mit Abbildung [bild4 ] lässt erkennen, dass an der Stelle ${\textstyle x_{1}}$ das absolute Maximum der Funktion liegt, während es sich bei ${\textstyle x_{2}}$ um ein lokales Minimum und bei ${\textstyle x_{3}}$ um ein lokales Maximum handelt.
Bereits für eine solch einfache Funktion wie ein Polynom dritten Grades ist die Bestimmung der Nullstellen nicht ganz trivial. Für die meisten Funktionen ist eine explizite Lösung überhaupt nicht möglich, und man ist auf numerische Methoden angewiesen. Die wichtigste wird im folgenden Abschnitt vorgestellt:

Das Newton Verfahren

Wir wollen die Nullstelle einer Funktion ${\textstyle g(x)}$ finden. (In Zusammenhang mit den Optimierungsaufgaben dieses Kapitels ist ${\textstyle g\left(x\right)=f^{\prime }\left(x\right)}$ die Ableitung der Funktion, deren Extremwerte gesucht werden; das Verfahren kann aber selbstverständlich für beliebige einmal differenzierbare Funktionen angewandt werden.) Das Newton-Verfahren ist ein Iterationsverfahren. Wir beginnen mit einer Stelle ${\textstyle x_{1}}$, die hoffentlich bereits in der Nähe der Nullstelle liegt. Grundidee ist nun die Funktion ${\textstyle g(x)}$ durch ihre Tangente an der Stelle ${\textstyle x_{1})}$ zu ersetzen, ${\textstyle t(x)=g(x_{1})+g\prime (x_{1})(x-x_{1})}$ und anschließend die Nullstelle der Tangente zu suchen. Die Lösung liefert den nächsten Punkt der Iteration:

$${\begin{aligned}x_{2}=x_{1}-{\frac {g\left(x_{1}\right)}{g^{\prime }\left(x_{1}\right)}}\end{aligned}}$$

Anschließend wird diese Prozedur so lange wiederholt, bis das Verfahren konvergiert, d.h. (bis auf numerische Genauigkeit) eine Nullstelle gefunden wurde. Es kann gezeigt werden, dass das Newton Verfahren extrem rasch (quadratisch) konvergiert, sobald man sich in der Nähe einer Nullstelle befindet. Die deutsche Wikipedia Seite bietet eine sehr schöne Animation, die verdeutlich wie das Newton Verfahren in der Praxis funktioniert. Um Kandidaten für lokale Extrema von ${\textstyle f(x)}$ zu erhalten sucht man Nullstellen der Ableitung von f, und das Iterationsverfahren hat daher die Gestalt

$${\begin{aligned}x_{k+1}=x_{k}-{\frac {f^{\prime }\left(x_{k}\right)}{f^{\prime \prime }\left(x_{k}\right)}}\end{aligned}}$$

Das bedeutet eine Funktion muss mindestens zweimal differenzierbar sein, damit diese Methode verwendet werden kann. In der Literatur findet man eine Unzahl an weiteren Methoden zur numerischen Bestimmung von Nullstellen.
Aufgabe 5:
Berechne für das Polynom ${\textstyle p^{\prime }(x)}$ aus Beispiel 6 die ersten beiden Newtonschritte mit Startwert ${\textstyle x_{1}=0}$. Schreib ein kleines Programm in der Programmiersprache deiner Wahl. Versuche auch andere Startwerte und beobachte wie sich das Verfahren verhält.

Die Bestimmung von globalen Extrema ist typischerweise wesentlich komplizierter als die Suche nach lokalen Extrema. Auch müssen diese nicht zwangsläufig existieren; die Funktion ${\textstyle f(x)=sin(x)}$ besitzt unendlich lokale Minima und Maxima, die gleichzeitig globale Extremwerte sind, die Funktion ${\textstyle f(x)=xsin(x)}$ besitzt unendlich viele lokale Extremwerte, aber keinen globalen. Plotten Sie die beiden Funktionen, um sich diese Tatsache vor Augen zu führen! Für eine gewisse Klasse von Funktionen kann man jedoch von lokaler Optimalität auf globale Optimalität schließen. Speziell nennt man eine Funktion f konvex (konkav), falls die Funktionswerte zwischen zwei Werten x und y jeweils unterhalb der Verbindungsgeraden der beiden Funktionswerte an x und y – der sogenannten Sekante - liegen. D.h. für jede Zahl t zwischen 0 und 1 gilt

$${\begin{aligned}&f(tx+(1-t)y)\leq tf(x)+(1-t)f(y){\text{ (konvex) }}\\&f(tx+(1-t)y)\geq tf(x)+(1-t)f(y)({\text{ konkav) }}\end{aligned}}$$

Datei:Fig/bild8.jpg

Konvexe Funktion

Abbildung 1.1 zeigt eine konvexe Funktion und deren Sekante für zwei ausgewählte Werte ${\textstyle x_{1}}$ und ${\textstyle x_{2}}$. Die Sekante liegt oberhalb des Graphen der Funktion. Falls die zweite Ableitung existiert so gilt für eine konvexe Funktion

$${\begin{aligned}f^{\prime \prime }\left(x\right)\geq 0\end{aligned}}$$

und für eine konkave Funktion

$${\begin{aligned}f^{\prime \prime }\left(x\right)\leq 0\end{aligned}}$$

Für eine konvexe (konkave) Funktion gibt es höchstens ein lokales Extremum, und dies ist dann das globale Minimum (Maximum).

Funktionen mehrerer Veränderlicher

Um Extremwerte von Funktionen in mehreren freien Variablen zu finden ist es erforderlich, die Kriterien für Extremwerten für höherdimensionale Definitionsbereiche zu verallgemeinern. Hier werden Gradient und Hessematrix die gleichen Rollen spielen wie 1. und 2. Ableitung im Eindimensionalen. Während die Bedingung an den Gradienten – er muss gleich dem Nullvektor sein, d.h., die Richtungsableitung muss in jeder Richtung verschwinden, sich ganz unmittelbar übertragen lässt, brauchen wir für die 2. Ableitungen etwas lineare Algebra – schließlich wollen wir der Matrix ansehen, ob die 2. Richtungsableitungen in jeder Richtung positiv oder negativ sind, oder ob das Krümmungsverhalten in den verschiedenen Richtungen unterschiedlich ist.

Determinante einer Matrix

Eine nxn-Matrix A entspricht einer linearen Abbildung:

$${\begin{aligned}{\begin{matrix}f:&\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}\\\ &{\vec {x}}\mapsto A{\vec {x}}\\\end{matrix}}\ \end{aligned}}$$

D.h., jeder Vektor aus dem ${\textstyle \mathbb {R} ^{n}}$ wird durch die Abbildung gedreht und/oder gestreckt oder gestaucht, so dass sein Bild wieder ein Vektor aus dem ${\textstyle \mathbb {R} ^{n}}$ ist. Nun sprengt eine ausführliche Abhandlung der linearen Funktionen den Rahmen dieses Kurses; eine Größe, die wir aber im Weiteren brauchen werden, ist die Determinante der Matrix. Sie errechnet sich für eine 2x2 Matrix

$${\begin{aligned}\ A=\left({\begin{matrix}a&b\\c&d\\\end{matrix}}\right)\end{aligned}}$$

nach der Formel

$${\begin{aligned}\det {\left(A\right)}=ad-bc,\end{aligned}}$$

für eine 3x3 Matrix

$${\begin{aligned}A=\left({\begin{matrix}a&b&c\\d&e&f\\g&h&i\\\end{matrix}}\right)\end{aligned}}$$

nach der Formel

$${\begin{aligned}\det {\left(A\right)}=aei+bfg+cdh-afh-bdi-ceg\end{aligned}}$$

(Regel von Sarrus), für höherdimensionale Matrizen mithilfe des Entwicklungssatzes und in der Praxis mit einem Algebra-Programm; Spezialfälle von Matrizen mit leicht ermittelbaren Determinanten sind Matrizen, die nur in der Diagonale Einträge ungleich 0 haben, sowie Matrizen, die entweder oberhalb oder unterhalb der Diagonale nur Nullen stehen haben; in beiden Fällen ist die Determinante das Produkt der Diagonal-Elemente. Ist die Determinante einer Matrix 0, so heißt das, dass zumindest eine Gerade von der Matrix auf den Nullvektor abgebildet wird; d.h., die Ebene wird auf eine Gerade abgebildet, der dreidimensionale Raum auf eine Ebene (oder eine Gerade) usw. Diese Eigenschaft macht man sich zunutze, um die sogenannten Eigenwerte der Matrix zu finden.

Eigenwerte und Eigenvektoren einer Matrix

Für eine ${\textstyle n\times n}$ Matrix A nennt man einen Vektor ${\textstyle {\vec {x}}\in \mathbb {R} ^{n}}$ einen Eigenvektor zum Eigenwert ${\textstyle \lambda }$, falls die sogenannte Eigenwertgleichung

$${\begin{aligned}A{\vec {x}}=\lambda {\vec {x}}\end{aligned}}$$

erfüllt ist. Dies bedeutet, dass der Eigenvektor x durch Multiplikation mit A einfach um den Faktor ${\textstyle \lambda }$ gestreckt (oder gestaucht) wird, ohne dabei gedreht zu werden; ist ${\textstyle \lambda }$ negativ, so wird der Vektor zusätzlich noch am Koordinaten-Ursprung gespiegelt – d.h., er zeigt nun in die entgegengesetzte Richtung.
Beispiel 7:
Gegeben sei die Matrix

$${\begin{aligned}A=\left({\begin{matrix}3&2\\-3&-4\\\end{matrix}}\right)\end{aligned}}$$

Es gilt

$${\begin{aligned}\left({\begin{matrix}3&2\\-3&-4\\\end{matrix}}\right)\left({\begin{matrix}1\\-3\\\end{matrix}}\right)=\left({\begin{matrix}-3\\\mathrm {\ \ } 9\\\end{matrix}}\right)\end{aligned}}$$

und

$${\begin{aligned}\left({\begin{matrix}3&2\\-3&-4\\\end{matrix}}\right)\left({\begin{matrix}2\\-1\\\end{matrix}}\right)=\left({\begin{matrix}4\\-2\\\end{matrix}}\right)\end{aligned}}$$

Somit ist

$${\begin{aligned}\left({\begin{matrix}1\\-3\\\end{matrix}}\right)\end{aligned}}$$

ein Eigenvektor zum Eigenwert -3,

$${\begin{aligned}\left({\begin{matrix}\mathrm {\ \ } 2\\-1\\\end{matrix}}\right)\end{aligned}}$$

Eigenvektor zum Eigenwert 2.

Wie kann man Eigenwerte und Eigenvektoren berechnen? Die Eigenwertgleichung bei bekanntem ${\textstyle \lambda }$ ist ein lineares Gleichungssystem mit ${\textstyle n}$ Gleichungen in ${\textstyle n}$ Variablen. Allerdings sind auch die Eigenwerte ${\textstyle \lambda _{i}}$ zunächst unbekannt, und müssen erst bestimmt werden: wenn ein Vektor ${\textstyle {\vec {x}}}$ Lösung Lösung der Eigenwertgleichung ${\textstyle \ A{\vec {x}}=\lambda {\vec {x}}}$ ist, so können wir diese Gleichung umformen zu ${\textstyle \left(A-\lambda I\right){\vec {x}}={\vec {o}}}$, (Hier ist I die Einheitsmatrix und ${\textstyle {\vec {o}}}$ der Nullvektor.) Daher ist die Matrix ${\textstyle A-\lambda I}$ singulär und hat die Determinante 0 – schließlich wird ja nicht nur ${\textstyle {\vec {x}}}$ auf den Nullvektor abgebildet, sondern auch jedes Vielfache, also die ganze Gerade, die durch diesen Vektor läuft. Es gilt:

$${\begin{aligned}det(A-\lambda I)=(-\lambda )^{n}+a_{n-1}\lambda ^{n-1}+\cdots +a_{1}\lambda +a_{0}=0\end{aligned}}$$

(Die Koeffizienten ${\textstyle a_{i}}$ ergeben sich dabei aus der Berechnung der Determinante, wie weiter unten ausgeführt.) Man bezeichnet ${\textstyle det\left(A-\lambda I\right)}$ als das charakteristische Polynom von A, die Eigenwerte sind die Nullstellen dieses Polynom. Die Suche nach allen Nullstellen erfolgt für großes n im Normalfall durch die im vorigen Abschnitt besprochenen numerischen Methoden. Für n=2 können Nullstellen sogar als Lösung einer quadratischen Gleichung unmittelbar gefunden werden, für n=3 häufig durch Erraten einer Nullstelle und anschließendes Aufspalten des Polynoms in Linearfaktoren (s. Beispiel 10).

Fortsetzung Beispiel 7:
Die charakteristische Gleichung lautet

$${\begin{aligned}\left|A-\lambda I\right|=\left|{\begin{matrix}3-\lambda &2\\-3&-4-\lambda \\\end{matrix}}\right|=\lambda ^{2}+\lambda -6=0\end{aligned}}$$

Lösen der quadratischen Gleichung

$${\begin{aligned}\lambda =-{\frac {1}{2}}\pm {\sqrt {{\frac {1}{4}}+6}}=-{\frac {1}{2}}\pm {\frac {5}{2}}\end{aligned}}$$

liefert die Nullstellen ${\textstyle \lambda _{1}=-3}$ und ${\textstyle \lambda _{2}=2}$.

Die zugehörigen Eigenvektoren erhält man durch Lösen der jeweiligen Eigenwertgleichungen. Beachte, dass die Eigenvektoren nur bis auf einen multiplikativen Faktor festgelegt sind.
Aufgabe 6:
Berechne alle Eigenwerte und Eigenvektoren für folgende Matrizen:

$${\begin{aligned}A=\left({\begin{matrix}\mathrm {\ 8} &7\\1&2\\\end{matrix}}\right)\\\ B=\left({\begin{matrix}1&-1\\-1&1\\\end{matrix}}\right)\\\ C=\left({\begin{matrix}1&-2&2\\-2&-2&4\\1&4&-6\\\end{matrix}}\right)\end{aligned}}$$

Die Theorie der Eigenwerte und Eigenvektoren spielt in vielen Anwendungsbereichen eine wesentliche Rolle . Ein Polynom n-ten Grades hat genau n Null-stellen, allerdings müssen diese nicht unbedingt verschieden sein – das Polynom ${\textstyle x^{2}-2x+1}$ hat die beiden Nullstellen ${\textstyle x_{1}=x_{2}=1}$ Man sagt: 1 ist eine Nullstelle mit Vielfachheit 2. Nullstellen können auch komplexe Zahlen sein. Für symmetrische Matrizen (d.h. AT = A), kann man zeigen, dass alle Eigenwerte reell sind. Zu den Eigenwerten mit Vielfachheit n gehören dann n linear unabhängige Eigenvektoren. Um uns die Bedeutung dieser Größen im Zusammenhang mit mehrdimensionalen Funktionen vor Augen zu führen, betrachten wir die Abbildung

$${\begin{aligned}f\left(x,y\right)=\left(x+y\right)^{2}+1.5\left(x-y\right)^{2}\end{aligned}}$$

image image image

Die linke Graphik zeigt den (ziemlich faden …) Funktionsgraphen – ein Paraboloid; die mittlere Graphik zeigt das Gradientenfeld – in jedem Punkt zeigt der Vektorpfeil in die Richtung des steilsten Anstiegs; die rechte Graphik zeigt nun die möglichen Wege einer Kugel, die wir am Scheitelpunkt absetzen: genau am Scheitelpunkt ist der Gradient null, d.h., die Richtungsableitung in jeder Richtung ist 0 und die Kugel bleibt einfach liegen. Geben wir ihr aber einen winzig kleinen Schubs, so ist der Gradient ungleich 0 und sie rollt sie nun in jedem Punkt dem Gradienten entgegen – schließlich will sie so schnell wie möglich nach unten und der Gradient zeigt den schnellsten Weg nach oben; die meisten möglichen Bahnen sind daher gekrümmt, d.h., der Gradient ändert ständig seine Richtung; es gibt allerdings zwei Richtungen, in denen die Bahnen Geraden sind – und das sind nun genau die Richtungen der Eigenvektoren der Hessematrix: in jedem Punkt auf dieser Geraden ändert sich der Gradient genau in der Richtung der Verbindung des Punktes mit dem Koordinaten-Ursprung; in unserem Fall zeigen die Pfeile auf diesen Trajektorien-Geraden jeweils vom Ursprung weg – damit ist klar: der Punkt ist ein Maximum – d.h., die Kugel wird in jeder Richtung vom Scheitel wegrollen. Das wiederum bedeutet für die Funktion, die die Höhe des Paraboloids für jeden Punkt der ${\textstyle x,y}$ – Ebene angibt, dass ihre 2. Richtungsableitung im Scheitelpunkt in jeder Richtung negativ sein muss.
Daraus ergibt sich folgendes Kriterium für Extremalstellen: der Gradient muss dort verschwinden; sind alle Eigenwerte der Hessematrix negativ, so ist der Punkt ein Maximum, sind sie positiv, ein Minimum, gibt es sowohl positive als auch negative, so haben wir einen Sattelpunkt. Die Vorzeichen der Eigenwerte bestimmt man mit den Definitheitskriterien:
Definitheit
Wir werden in diesem Abschnitt immer davon ausgehen, dass A eine symmetrische Matrix ist. Für die Anwendung, die wir letztendlich betrachten wollen, nämlich für die Hessematrix, ist dies natürlich der Fall, da ja gilt:

$${\begin{aligned}{\frac {\partial ^{2}f}{\partial x_{i}\partial x_{j}}}={\frac {\partial ^{2}f}{\partial x_{j}\partial x_{i}}}.\end{aligned}}$$

Im Zusammenhang mit symmetrischen Matrizen sind quadratische Formen von besonderem Interesse, dabei handelt es sich um die zur Matrix A gehörende Funktion

$${\begin{aligned}{\begin{matrix}q:&\mathbb {R} ^{n}\rightarrow \mathbb {R} \\\ &{\vec {x}}\mapsto {\vec {x}}^{T}A{\vec {x}}\\\end{matrix}}\end{aligned}}$$

Beispiel 8:
Gegeben sei die symmetrische Matrix

$${\begin{aligned}A=\left({\begin{matrix}1&2\\2&-4\\\end{matrix}}\right)\end{aligned}}$$

Die zu A gehörende quadratische Form ${\textstyle q}$ ordnet jedem zweidimensionalen Vektor den Wert zu.

$${\begin{array}{r}{\vec {x}}=\left({\begin{array}{l}x_{1}\\x_{2}\end{array}}\right)\\{\vec {x}}^{T}A{\vec {x}}=x_{1}^{2}+4x_{1}x_{2}-4x_{2}^{2}\end{array}}$$

Eine quadratische Form heißt
positiv definit, falls ${\textstyle {\vec {x}}^{T}A{\vec {x}}>{\vec {0}}}$ für alle x 0
 positiv semidefinit, falls ${\textstyle {\vec {x}}^{T}A{\vec {x}}\geq {\vec {0}}}$ für alle x 0
 negativ definit, falls ${\textstyle {\vec {x}}^{T}A{\vec {x}}<{\vec {0}}}$ für alle x 0
 negativ semidefinit, falls ${\textstyle {\vec {x}}^{T}A{\vec {x}}\leq {\vec {0}}}$ für alle x 0
 indefinit, falls ${\textstyle {\vec {x}}^{T}A{\vec {x}}>0}$ für einige x und ${\textstyle {\vec {y}}^{T}A{\vec {y}}<0}$ für einige y.

Diese Definitheitseigenschaften stehen in unmittelbarem Zusammenhang mit den Eigenwerten der Matrix A. Man kann zeigen, eine quadratische Form ${\textstyle {\vec {x}}^{T}A{\vec {x}}}$ ist
 positiv definit, falls alle Eigenwerte > 0
 positiv semidefinit, falls alle Eigenwerte ${\textstyle \geq }$ 0
 negativ definit, falls alle Eigenwerte < 0
 negativ semidefinit, falls alle Eigenwerte ${\textstyle \leq }$ 0
 indefinit, falls einige Eigenwerte ${\textstyle >}$ 0 und einige Eigenwerte ${\textstyle <}$ 0 sind.
 

Die dazugehörigen Matrizen werden dann ebenfalls als positiv (semi-) definit usw. bezeichnet. In der Praxis kann die Definitheit von Matrizen oft mit dem Hauptminorenkriterium bestimmt werden. Als i-ten führenden Hauptminor einer Matrix bezeichnet man die Determinante der Matrix, die man gewinnt, wenn man nur die ersten i Zeilen und Spalten betrachtet; für eine Matrix

$${\begin{aligned}A=\left({\begin{matrix}a_{1,1}&\cdots &a_{1,n}\\\vdots &\ddots &\vdots \\a_{n,1}&\cdots &a_{n,n}\\\end{matrix}}\right)\end{aligned}}$$

lauten sie also (die senkrechten Striche sind eine alternative Schreibweise für die Berechnung der Determinante der Matrix zwischen den Strichen):

$${\tilde {\Delta }}_{1}(A)=a_{1,1},\quad {\tilde {\Delta }}_{2}(A)=\left({\begin{array}{cc}a_{1,1}&a_{1,2}\\a_{2,1}a_{2,2}\end{array}}\right),\ldots ,{\tilde {\Delta }}_{n}=\operatorname {det} A$$

Es gilt nun: sind alle führenden Hauptminoren positiv, so ist die Matrix positiv definit; sind die Vorzeichen der führenden Hauptminoren abwechselnd positiv und negativ – beginnend mit negativ – so ist die Matrix negativ definit. Weiters ist die Determinante der Matrix das Produkt der Eigenwerte - ist also die Determinante 0, so ist die Matrix indefinit, ist sie ungleich 0, sind alle Eigenwerte ungleich 0. Viele Fälle können mit diesen Kriterien durch Ausschluss bestimmt werden; nur wenn einer oder mehrere führende Hauptminoren 0 sind, ist keine eindeutige Aussage möglich. Wir können nun allgemeine Kriterien dafür aufstellen, wann eine zweimal differenzierbare mehrdimensionale nichtlineare Funktion ein lokales Extremum aufweist. Eine notwendige Bedingung ist wie bereits erwähnt ${\textstyle \mathrm {\nabla f} =0}$.Für Funktionen in einer Variablen bedeutet das: die Ableitung verschwindet. Ist die zweite Ableitung positiv, so findet sich dort ein Minimum. Diese Bedingung für Minima lässt sich auf Funktionen in mehreren Variablen erweitern: Wenn der Gradient in einem Punkt verschwindet und die zweite Ableitung in jeder Richtung negativ ist, so handelt es sich um ein lokales Minimum. Dafür genügt es, dass die zweite Ableitung in Richtung der Eigenvektoren der Hessematrix negativ ist, d.h., dass alle Eigenwerte der Hessematrix negativ sind und diese daher negativ definit ist; analoges gilt für die Maxima.

Achtung! Ein naheliegender Irrtum: man könnte glauben, dass es reicht, wenn wir uns das Krümmungsverhalten in x und y Richtung anschaun – also die zweiten partiellen Ableitungen; das ist aber nicht der Fall: die Abbildung zeigt eine Funktion, die entlang x und der y-Achse konkav ist; trotzdem ist der Nullpunkt – in dem der Gradient verschwindet – ein Sattelpunkt – es gibt nämlich auch Richtungen, in denen die Funktion konvex ist - die Diagonalen.

Datei:Fig/bild10.jpg

Beispiel für einen Sattelpunkt

Basierend auf den Definitheitseigenschaften der Hessematrix Hf gelten folgende hinreichenden Bedingungen für Extremwerte: Sei

$${\begin{aligned}\mathrm {\nabla f} \left({\vec {x}}_{0}\right)=0.\end{aligned}}$$

 Falls Hf an der Stelle ${\textstyle {\vec {x}}_{0}}$ positiv definit, so hat f dort ein lokales Minimum.
 Falls Hf an der Stelle ${\textstyle {\vec {x}}_{0}}$ negativ definit, so hat f dort ein lokales Maximum.
 Falls Hf an der Stelle ${\textstyle {\vec {x}}_{0}}$ indefinit, so handelt es sich an der Stelle weder um ein lokales Maximum noch um ein Minimum, sondern um einen sogenannten Sattelpunkt.
 Im Falle von ${\textstyle H_{f}}$ positiv semidefinit oder negativ semidefinit kann keine Aussage getroffen werden (vgl. die Situation im eindimensionalen, wenn die zweite Ableitung verschwindet).
 

Die folgende Eierkarton-Funktion ${\textstyle \sin {x\cos {y\ }}}$ hat Bereiche, in denen sie in jeder Richtung kokav ist – dort finden sich die Maxima, also die Gipfel - andere, in denen sie in jeder Richtung konvex ist – dort sind die Minima, also die Gruben, und weitere Beriche, in denen sie in einer Richtung konvex ist, in einer anderen konkav – dort finden sich die Sattelpunkte. Stellen sie sich einen Bewohner einer dieser Gruben vor, der eine Freundin in der benachbarten Grube besuchen möchte; dabei muss er über einen Pass wandern – und dieser Pass ist dann der Sattelpunkt.

Datei:Fig/bild11.jpg

Eierkarton-Funktion

Beispiel 9:
Der linke Graph in Abbildung 1.3 zeigt einen Oberflächenplot der Funktion ${\textstyle x^{2}-y^{2}}$:
 

$${\begin{aligned}{\begin{matrix}f:&\mathbb {R} ^{2}\rightarrow \mathbb {R} \\\ &\left(x,y\right)\mapsto x^{2}-y^{2}\\\end{matrix}}.\end{aligned}}$$

Es gilt

$${\begin{aligned}\mathrm {\nabla f} \left(x,y\right)=\left({\begin{matrix}\mathrm {\ \ } 2x\\-2y\\\end{matrix}}\right)\end{aligned}}$$

und daher ist der Ursprung x=0, y=0 Kandidat für eine Extremstelle. Allerdings gilt

$${\begin{aligned}H_{f}\left(x,y\right)=\left({\begin{matrix}2&0\\0&-2\\\end{matrix}}\right)\end{aligned}}$$

mit den offensichtlichen Eigenwerten -2 und 2. Die Hessematrix ist indefinit, und der Ursprung ist keine Extremstelle, sondern ein Sattelpunkt. Abbildung 1.2 veranschaulicht, woher dieser Name kommt: die zweite Ableitung der Funktion in Richtung der x-Achse ist überall positiv, daher insbesondere im Punkt (0,0); ebenso ist die zweite Ableitung in Richtung der y – Achse überall negativ, d.h. der Punkt (0,0) ist ein lokales Minimum, wenn wir ihn in Richtung der x-Achse queren und ein lokales Maximum, wenn wir ihn in Richtung y – Achse überqueren. Ein lokales Minimum müsste aber in jeder Richtung Minimum sein, daher kann (0,0) keines sein, und aus dem analogen Grund ebenso wenig ein Maximum.

Aufgabe 7:
Untersuche die folgenden beiden Funktionen auf lokale Extrema: \begin{array}{r} f_1(x, y, z)=4 x-2 x^2+6 y-y^2-z^2+3 \\ f_2(x, y, z)=3 x^2-4 x y+3 y^2+10 z-z^2 \end{array} </math>

Algorithmen zur Optimierung

Bisher haben wir nur notwendige und hinreichende Bedingungen für lokale Extremstellen kennen gelernt. Bereits im Eindimensionalen war die aktuelle Berechnung der Stelle nicht immer einfach. Für die in der Praxis so wichtigen Funktionen mehrerer Veränderlicher ist dieses Problem häufig um ein Vielfaches komplizierter – schließlich muss in der Iteration in jedem Schritt die Richtung, in der weitergesucht wird, neu bestimmt werden. Man ist oft auf numerische Lösungsmethoden angewiesen. Dieses Gebiet ist ein aktiver Forschungszweig, und nach wie vor sind bei weitem nicht alle Fragestellungen gelöst. Wir wollen an dieser Stelle nur zwei grundlegende Verfahren besprechen. Eine Umsetzung dieser Verfahren mithilfe von R finden Sie in den Videos auf der Homepage erläutert.

Das Newton Verfahren in mehreren Dimensionen

Das in Abschnitt davor bereits erwähnte Newton-Verfahren kann recht einfach auf mehrere Dimensionen verallgemeinert werden. Die Grundidee bleibt dabei gleich, man sucht nach Nullstellen von ${\textstyle \mathrm {\nabla f} \left({\vec {x}}\right)}$ und ersetzt mit Hilfe dieses Gradienten die Funktion durch eine lineare Approximation. Man erhält das Iterationsverfahren

$${\begin{aligned}{\vec {x}}_{k+1}={\vec {x}}_{k}-\left[H_{f}\left({\vec {x}}_{k}\right)\right]^{-1}\mathrm {\nabla f} \left({\vec {x}}_{k}\right)\end{aligned}}$$

Verfolgen wir die Analogie zum bekannten eindimensionalen Fall: sucht man dort einen Extremwert, so kann mithilfe des eindimensionalen Newton-Verfahrens die Nullstellen der Ableitung bestimmen; dazu wird der Wert der ersten Ableitung an der Stelle ${\textstyle x_{i}}$ durch die zweite Ableitung dividiert, dieser Quotient gibt dann an, wie weit auf der x-Achse weitergegangen werden muss. Ist die Funktion, deren Extremwert gesucht wird, eine quadratische Funktion, dann ist das Verfahren nach einem Schritt am Ziel – dann ist nämlich die Ableitung eine lineare Funktion, deren Nullstelle in einem Schritt gefunden wird; für jede andere Funktion entspricht das Newton-Verfahren dann der Approximation durch quadratische Funktionen. Formal sieht die Iterationsvorschrift im Mehrdimensionalen genauso aus wie im eindimensionalen. Allerdings approximieren wir jetzt den Gradienten durch eine lineare Funktion, und die Division durch die zweite Ableitung im eindimensionalen entspricht der Multiplikation mit der Inversen der Hessematrix. Wenn die zu optimierende Funktion eine quadratische Funktion ist, so führt das Verfahren bereits in einem Schritt zum Ziel – wie im eindimensionalen. Die Hesse-Matrix muss im Allgemeinen nach jedem Iterationsschritt für jedes ${\textstyle {\vec {x}}_{k}}$ neu berechnet und invertiert werden, was bei großer Dimension n recht zeitaufwendig ist. In der Praxis wird dieses Update der Hesse-Matrix daher nicht in jedem Schritt durchgeführt, dies führt zu sogenannten Quasi-Newton Verfahren . Das Newtonverfahren konvergiert äußerst rasch, sobald man sich in der Nähe eines lokalen Minimums befindet. Allerdings ist es noch schwieriger als in einer Dimension, überhaupt in die Nähe eines Minimums zu kommen. Oft werden dazu Verfahren wie das folgende verwendet, die zwar nicht so rasch konvergieren, sich dafür aber mit Sicherheit in Richtung Minimum bewegen.

Das Gradientenverfahren

Die Idee hier ist, dass zunächst eine Suchrichtung festgelegt wird, und dann in diese Richtung ein eindimensionales Optimierungsverfahren angewendet wird. Bei der Suche nach einem Minimum ist es natürlich, dass man eine Richtung sucht, in der die Werte der Funktion ${\textstyle f}$ kleiner werden, eine sogenannte Abstiegsrichtung. Mathematisch gesprochen verringern sich die Werte der Funktion ${\textstyle f\left({\vec {x}}\right)}$ in Richtung des Vektors ${\textstyle {\vec {d}}}$, falls

$${\begin{aligned}f\left({\vec {x}}+c{\vec {d}}\right)<f\left({\vec {x}}\right)\end{aligned}}$$

für kleine Werte von c > 0. Dies hat zur Folge, dass

$${\begin{aligned}\left[\mathrm {\nabla f} \left({\vec {x}}\right)\right]^{T}{\vec {d}}<0\end{aligned}}$$

Das heißt wenn das innere Produkt des Gradienten mit einem Richtungsvektor ${\textstyle {\vec {d}}}$ negativ ist, so handelt es sich um eine Abstiegsrichtung. Wie man leicht zeigen kann erfolgt der steilste Abstieg gerade in die entgegengesetzte Richtung des Gradientenvektors, d.h.

$${\begin{aligned}{\vec {d}}=-{\frac {{\nabla f}({\vec {x}})}{||{{\nabla f}({\vec {x}})}||}}\end{aligned}}$$

ist der normierte Vektor, der die Richtung des optimalen Abstiegs angibt. Die Idee des Gradientenverfahrens besteht nun darin, dass man wieder mit einem beliebigen Startvektor ${\textstyle {\vec {x}}_{1}}$ beginnt und die Suchtrichtung

$${\begin{aligned}{\vec {d_{1}}}=-{\frac {{\nabla f}({\vec {x_{1}}})}{||{{\nabla f}({\vec {x_{1}}})}||}}\end{aligned}}$$

festlegt. (Für die Rechnung einfacher und im Ergebnis äquivalent ist es, wenn der Vektor nicht normiert wird; es ist zwar dann kein Richtungsvektor mehr – aber der nächste Iterationspunkt ist genau derselbe.) Definiere die eindimensionale Funktion

$${\begin{aligned}g\left(y\right)=f\left({\vec {x}}_{1}+y{\vec {d}}_{1}\right)\end{aligned}}$$

deren Minimum ${\textstyle y_{1}}$ nun zum Beispiel mit dem eindimensionalen Newtonverfahren bestimmt werden kann. Dieses liefert den nächsten Iterationspunkt

$${\begin{aligned}{\vec {x}}_{2}={\vec {x}}_{1}+y_{1}{\vec {d}}_{1}\end{aligned}}$$

Bestimme an ${\textstyle {\vec {x}}_{2}}$ eine neue Suchrichtung, und wiederhole das Verfahren so lange, bis ein lokales Minimum gefunden wurde. Dies ist dann der Fall, wenn der Gradient von ${\textstyle {\vec {x}}_{k}}$ sich kaum mehr vom Nullvektor unterscheidet. Das Gradientenverfahren konvergiert zwangsläufig gegen einen kritischen Punkt, d.h. gegen einen Punkt mit ${\textstyle \mathrm {\nabla f} \left({\vec {x}}\right)=0}$. Allerdings kann es in der Nähe eines Minimums zum sogenannten Zickzackphänomen kommen. Dabei ändert sich die Suchrichtung in jedem Iterationsschritt in drastischer Weise, während kaum mehr eine Verminderung des Wertes der Zielfunktion zu beobachten ist. Es empfiehlt sich häufig in der Nähe des Minimums zu anderen Verfahren überzugehen, etwa zu einem Quasi-Newton Verfahren. Für weitere Details sei hier wiederum auf die Literatur verwiesen (Bomze, Grossmann 1993, Nocedal, Wright 1999, etc.)

Optimierung unter Nebenbedingungen

Häufig treten in ökonomischen Anwendungen Optimierungsprobleme auf, bei denen gewisse Nebenbedingungen erfüllt werden müssen. Das bedeutet, das nicht mehr der ganze Definitionsbereich einer Funktion betrachtet wird, sondern nur eine Teilmenge; deren genaue Gestalt hängt von den Nebenbedingungen ab; maximieren wir etwa eine Funktion ${\textstyle f\left(x,y\right)}$ unter der Nebenbedingung: ${\textstyle g\left(x,y\right)=x^{2}+y^{2}=4}$, so wird das Maximum auf dem Kreis mit Radius 2 gesucht. Dieser ist die Höhenschichtline der Funktion ${\textstyle g\left(x,y\right)}$ zum Niveau 4. Wenn wir statt der Gleichung die Ungleichung ${\textstyle g\left(x,y\right)=x^{2}+y^{2}\leq 1}$ als Nebenbedingung vorgeben, so wird das Maximum auf der ganzen Kreisscheibe gesucht (also auch im Inneren des Kreises). Für den Spezialfall der Optimierung von linearen Funktionen unter linearen Nebenbedingungen gibt es das sogenannte Simplex-Verfahren, das hier nicht behandelt wird; es gibt dafür inzwischen leicht auffindbare Internetresourcen (z.B. www.phpsimplex.com oder LINDO); wir behandeln die weitaus schwierigere Fragestellung der nichtlinearen Optimierung unter Nebenbedingungen, die selbst linear oder nichtlinear sein können. Die wichtigste Methode zur Behandlung von Optimierungsaufgaben unter Nebenbedingungen besteht darin, diese auf Optimierungsprobleme ohne Nebenbedingungen zurückzuführen. Der Einfachheit halber werden wir diese Theorie hier nur für Funktionen in zwei Veränderlichen vorstellen, die Verallgemeinerung auf mehrere Veränderliche erfordert zwar mehr Rechenaufwand, jedoch keine neuen Konzepte. Wir beschreiben nur die Suche nach einem lokalen Minimum, für Maxima läuft alles völlig analog, bzw. kann man das Minimum von ${\textstyle -f\left(x,y\right)}$ suchen um das Maximum von ${\textstyle f\left(x,y\right)}$ zu erhalten.

Lagrange – Multiplikatoren – Gleichungen als Nebenbedingung

Wir wollen folgende Aufgabe lösen:Finde

$${\begin{aligned}\mathrm {min\ } f\left(x,y\right)\end{aligned}}$$

unter

$${\begin{aligned}g\left(x,y\right)=c\end{aligned}}$$

d.h., wir suchen das Minimum der Funktion ${\textstyle f\left(x,y\right)}$ über der Höhenschichtline zum Niveau ${\textstyle c}$ der Funktion ${\textstyle g\left(x,y\right)}$, wobei wir voraussetzen, dass sowohl ${\textstyle f}$ als auch ${\textstyle g}$ differenzierbar sind. Im ersten Schritt der Methode wird ein Lagrange-Multiplikator, zumeist mit ${\textstyle \lambda }$ bezeichnet (hat nichts mit den Eigenwerten einer Matrix zu tun!), eingeführt. Man definiert die Lagrange-Funktion ${\textstyle L}$ als

$${\begin{aligned}L\left(x,y,\lambda \right)=f\left(x,y\right)+\lambda \left(g\left(x,y\right)-c\right)\end{aligned}}$$

und sucht jene Paare ${\textstyle \left(x_{0},y_{0}\right)}$, für das es ein Lambda gibt, mit dem die Funktion in ${\textstyle \left(x_{0},y_{0},\lambda (x_{0},y_{0}\right))}$ ein Minimum annimmt. Die Nebenbedingung steckt nun implizit in der Lagrange-Funktion. Falls die Nebenbedingung erfüllt ist so gilt ${\textstyle L\left(x,y,\lambda \right)=f\left(x,y\right)}$. Falls die Nebenbedingung nicht erfüllt ist und zum Beispiel ${\textstyle g\left(x_{0},y_{0}\right)>c}$, so wird die Lagrange-Funktion für diesen Punkt für hinreichen kleines ${\textstyle \lambda }$ beliebig klein, und und die Lagrangefunktion kann in diesem Punkt für kein ${\textstyle \lambda }$ ein Minimum annehmen. Beachten Sie auch: das Kriterium ist etwas anderes als die Suche nach Tripeln ${\textstyle \left(x,y,\ \lambda \right)}$, welche die Lagrangefunktion minimieren – solche wird man im Allgemeinen nicht finden: gilt nämlich ${\textstyle \left(g\left(x,y\right)-c\right)\neq 0}$, dann gibt es aus den genannten Gründen kein optimales ${\textstyle \lambda }$!
Das Lagrange-Theorem besagt nun folgendes: falls ${\textstyle \left(x_{0},y_{0}\right)}$ ein lokales Minimum von ${\textstyle f\left(x,y\right)}$ unter der Nebenbedingung ${\textstyle g\left(x,y\right)=c}$ ist, und falls ${\textstyle \mathrm {\nabla g} (x_{0},y_{0})\neq (0,0)^{T}}$so gibt es eine eindeutige Zahl ${\textstyle \lambda }$, für welche die Lagrange-Funktion einen stationären Punkt in ${\textstyle \left(x_{0},y_{0}\right)}$ hat, d.h. ${\textstyle \mathrm {\nabla L} (x_{0},y_{0})=(0,0)^{T}}$ unter Beibehaltung der Nebenbedingung ${\textstyle g\left(x,y\right)=c}$. Um Kandidaten zur Lösung der ursprünglichen Aufgabe zu erhalten, muss also das folgende System von Gleichungen gelöst werden:

$${\begin{aligned}&{\frac {\partial }{\partial x}}L(x,y,\lambda )={\frac {\partial }{\partial x}}f(x,y)+\lambda {\frac {\partial }{\partial x}}g(x,y)=0\\&{\frac {\partial }{\partial y}}L(x,y,\lambda )={\frac {\partial }{\partial y}}f(x,y)+\lambda {\frac {\partial }{\partial y}}g(x,y)=0\\&{\frac {\partial }{\partial \lambda }}L(x,y,\lambda )=g(x,y)-c=0\end{aligned}}$$

d.h., der Gradient der Zielfunktion ist ein lineares Vielfaches des Gradienten der Funktion, die die Nebenbedingung angibt. Nun zeigt uns der Gradient die Richtung des stärksten Anstiegs an und steht normal auf die Höhenschichtlinie. Stellen wir uns den Graphen der Zielfunktion als hügelige Landschaft vor, so wird durch die Nebenbedingung ein Weg durch diese Landschaft gelegt, und gesucht werden die höchsten bzw. tiefsten Punkte auf diesem Weg. An diesen fällt das Gelände senkrecht zum Weg am steilsten ab (s. Abbildung 1.3).
Beispiel 11:
Ein Verbraucher habe die Nutzenfunktion

$${\begin{aligned}f\left(x,y\right)=\mathrm {xy} .\end{aligned}}$$

Maximiere die Nutzenfunktion unter der Budgetbeschränkung

$${\begin{aligned}g\left(x,y\right)=x+2y=\mathrm {10} .\end{aligned}}$$

Die Lagrange Funktion lautet:

$${\begin{aligned}L\left(x,y,\lambda \right)=\mathrm {xy} +\left(x+2y-\mathrm {10} \right)\end{aligned}}$$

Null setzen der partiellen Ableitungen gibt

$${\begin{aligned}{\frac {\partial }{\partial x}}L\left(x,y,\lambda \right)=y+\lambda =0\\\ {\frac {\partial }{\partial y}}L\left(x,y,\lambda \right)=x+2\lambda =0\end{aligned}}$$

Elimination von ${\textstyle \lambda }$ aus diese beiden Gleichungen liefert ${\textstyle x-2y=0}$ Und wir haben die Nebenbedingung

$${\begin{aligned}x+2y=\mathrm {10} \end{aligned}}$$

Dieses lineare Gleichungssystem mit zwei Variablen hat eine eindeutige Lösung:

$${\begin{aligned}x=5,y=2.5\end{aligned}}$$

und schließlich

$${\begin{aligned}\lambda =-y=-2\mathrm {.} 5\end{aligned}}$$

An sich haben wir bisher nur eine notwendige Bedingung für ein lokales Extremum und es sollte noch gezeigt werden, dass es sich tatsächlich um ein Maximum handelt. Ähnlich wie im Falle der Optimierung ohne Nebenbedingung gibt es entsprechende Kriterien an die zweiten Ableitungen von ${\textstyle f}$ und ${\textstyle g}$, anhand derer man entscheiden kann ob es sich um ein Maximum oder ein Minimum handelt. Wir wollen uns zunächst auf eine graphische Darstellung des Sachverhalts beschränken:

Datei:Fig/bild12.jpg

Optimierung unter Nebenbedingungen

Datei:Fig/bild12a.png

Optimierung unter Nebenbedingungen

Abbildung 1.4 zeigt einerseits ausgewählte Niveaulinien der Zielfunktion ${\textstyle f\left(x,y\right)=\mathrm {xy} }$, anderseits die Gerade ${\textstyle y=5-{\frac {x}{2}}}$ welche gerade die Budget-beschränkung beschreibt. Sinnvoller weise sind beide Investitionen x und y positiv. Entsprechende Ungleichungs-Nebenbedingungen werden im nächsten Abschnitt besprochen. Am Punkt ${\textstyle (x_{0}=5,y_{0}=2.5)}$ berührt die Gerade die Niveaulinie zum Wert ${\textstyle xy=12.5}$. Es ist klar ersichtlich, dass an allen anderen Punkten die Gerade jene Niveaulinien schneidet, die einem geringeren Wert der Zielfunktion entsprechen. Daher handelt es sich bei dem Punkt ${\textstyle (x_{0},y_{0})}$ um ein lokales Maximum der Zielfunktion unter der gegebenen Budgetbeschränkung. Dass an dieser Stelle die Nebenbedingungsgerade tangential an die Niveaulinie liegt ist typisch, und der geometrische Grund dafür, dass die Lagrange-Methode funktioniert. Abbildung 1.5 ist eine dreidimensionale Veranschaulichung des Sachverhaltes; die stark ausgezogene Kurve ist der Graph der Funktion unter der Nebenbedingung (der „Weg durch das hügelige Gelände“, um beim Bild zu bleiben). An seinem höchsten Punkt ist er tangential zum Graphen der Höhenschichtlinien, d.h., das Gelände fällt dort senkrecht zum Weg am steilsten ab.
Für eine allgemeine Klassifizierung von Punkten, die mithilfe der Lagrage Funktion gefunden wurden, steht die Methode der berandeten Hessematrizen zur Verfügung; im zweidimensionalen Fall: Sei

$$L(x,y,\lambda )=f(x,y)+\lambda g(x,y-c)$$

die Lagrangefunktion eines Optimierungsproblems; dann bilden wir die Hessematrix nach allen drei Variablen – allerdings beginnend mit ${\textstyle \lambda }$:

$${\bar {H}}=\left({\begin{array}{c}{\frac {\partial ^{2}L}{\partial \lambda ^{2}}}{\frac {\partial ^{2}L}{\partial \lambda \partial x}}{\frac {\partial ^{2}L}{\partial \lambda \partial y}}\\{\frac {\partial ^{2}L}{\partial \lambda \partial x}}{\frac {\partial ^{2}L}{\partial x^{2}}}{\frac {\partial ^{2}L}{\partial x\partial y}}\\{\frac {\partial ^{2}L}{\partial \lambda \partial y}}{\frac {\partial ^{2}L}{\partial x\partial y}}{\frac {\partial ^{2}L}{\partial y^{2}}}\end{array}}\right)$$

(der linke obere Eintrag – die zweite Ableitung nach ${\textstyle \lambda }$ – ist immer 0.)
Ist die Determinante dieser Matrix positiv, so haben wir ein lokales Maximum, ist sie negativ, ein Minimum, ist die Determinante Null, so ist die Frage nicht entscheidbar.
Einen Sonderfall stellen Nebenbedingungen dar, die eine beschränkte Menge beschreiben – z.B. einen geschlossenen Kreis, eine Ellipse oder ein Streckenstück; auf einer solchen Menge können wir einfach alle kritischen Punkte der Reihe nach betrachten – der mit dem größten Funktionswert ist das Maximum, der mit dem kleinsten das Minimum.

Aufgabe 8:
Finde die beiden Extremstellen von

$${\begin{aligned}f\left(x,y\right)=x^{2}+y^{2}\end{aligned}}$$

unter der Nebenbedingung

$${\begin{aligned}g\left(x,y\right)=x^{2}+\mathrm {xy} +2=3\end{aligned}}$$

Die vorgestellte Theorie lässt sich weitgehend unverändert auf Funktionen mit mehr als zwei unabhängigen Variablen erweitern. Häufig gibt es in der Anwendung mehr als eine Nebenbedingung, und die Lagrange-Methode besteht dann darin, dass für jede Nebenbedingung ein eigener Lagrange-Multiplikator hinzugefügt wird. Bei einem Optimierungsproblem in n Variablen mit m Nebenbedingungen erhält man demnach eine Lagrange-Funktion L in n+m Variablen. Kandidaten für lokale Extrema erhält man wiederum indem man nach stationären Punkten von L sucht, wobei es nun gilt n+m Gleichungen in n+m Variablen zu lösen.

Karush Kuhn Tucker Bedingungen

Häufig tauchen Nebenbedingungen nicht in Gleichungsform, sondern in Ungleichungsform auf, z.B., dass eine Variable x nur positive Werte annehmen kann, also die Nebenbedingung ${\textstyle x\geq 0}$ erfüllen muss. Das allgemeine Problem in zwei Variablen mit einer Nebenbedingung hat die Form: Finde

$${\begin{aligned}\mathrm {max\ (} f(x,y))\end{aligned}}$$

unter

$${\begin{aligned}g\left(x,y\right)\leq c\end{aligned}}$$

D.h., wir suchen das Minimum der Funktion ${\textstyle f\left(x,y\right)}$ über einem Bereich, der von der Höhenschichtline zum Niveau c der Funktion ${\textstyle g\left(x,y\right)}$ begrenzt wird, wobei wir wieder voraussetzen, dass sowohl f als auch g differenzierbar sind. Die Menge aller ${\textstyle \left(x,y\right)}$ welche die Nebenbedingung erfüllen, wird als zulässige Menge bezeichnet. Im Prinzip kann dieses Problem mit den bereits gelernten Methoden behandelt werden, indem man einerseits nach lokalen Extremstellen im Inneren des zulässigen Bereichs sucht (Optimierung ohne Nebenbedingung), und andererseits den Rand des zulässigen Bereichs ${\textstyle g\left(x,y\right)=c}$ mit Hilfe der Lagrange-Methode untersucht. Unter gewissen Voraussetzungen an die Randbedingungen (den sogenannten constraint qualifications ) lassen sich allerdings notwendige Bedingungen für lokale Extremwerte im gesamten zulässigen Bereich angeben. Dazu wird wiederum die Lagrange-Funktion

$${\begin{aligned}L\left(x,y,\lambda \right)=f\left(x,y\right)+\lambda \left(g\left(x,y\right)-c\right)\end{aligned}}$$

definiert, allerdings gilt hier für die Lagrange Multiplikatoren ${\textstyle \lambda \leq 0}$. Entscheidend ist nun die sogenannte komplementäre Schlaffheitsbedingung (complementary slackness). Man fordert, dass entweder die Nebenbedingung exakt erfüllt ist (d.h. ${\textstyle g\left(x,y\right)=c}$), oder aber der Lagrange Multiplikator${\textstyle \lambda =0}$. Diese Bedingung ist erfüllt falls

$${\begin{aligned}\lambda \left(g\left(x,y\right)-c\right)=0\end{aligned}}$$

Die complementary slackness Bedingung beinhaltet in sehr eleganter Form dass ein lokaler Extremwert direkt am Rande des zulässigen Bereiches andere Bedingungen erfüllen muss als im Inneren: für ${\textstyle \lambda =0}$ erhält man die lokalen Maxima im Inneren, diese sind die gleichen, die wir auch ohne Nebenbedingung gefunden hätte. Am Rand hingegen müssen die Gradienten von ${\textstyle f\left(x,y\right)}$ und ${\textstyle g\left(x,y\right)}$ (anti-) parallel sein, d.h., wenn wir der Richtung des steilsten Angstiegs der Zielfunktion folgen würden, würden wir den von der Nebenbedingung erlaubten Bereich verlassen. Zusammenfassend liefert dies die sogenannten Karush Kuhn Tucker (KKT) Bedingungen als notwendige Bedingungen für lokale Extrema unter Ungleichheits-Nebenbedingungen:
 

$${\begin{aligned}{\frac {\partial }{\partial x}}L(x,y,\lambda )={\frac {\partial }{\partial x}}f(x,y)+\lambda {\frac {\partial }{\partial x}}g(x,y)&=0\\{\frac {\partial }{\partial y}}L(x,y,\lambda )={\frac {\partial }{\partial y}}f(x,y)+\lambda {\frac {\partial }{\partial y}}g(x,y)&=0\\g(x,y)\leq c\lambda &\leq 0\\\lambda (g(x,y)-c)&=0\end{aligned}}$$

Beispiel 12:
Ein Unternehmen hat die Möglichkeit zwei Güter zu produzieren. Bei beiden Produkten ist der erzielbare Preis jeweils proportional zur Qualität x bzw. y, während der Aufwand zur Qualitätssteigerung quadratisch wächst. D.h.:
 Produkt 1: Für Preis ${\textstyle ax}$ bedarf es ${\textstyle Ax^{2}}$ Arbeitseinheiten
 Produkt 2: Für Preis ${\textstyle by}$ bedarf es ${\textstyle By^{2}}$ Arbeitseinheiten
 wobei alle Konstanten ${\textstyle (a,b,A,B)}$ größer als 0 sein sollen.
 Das Unternehmen hat insgesamt höchstens L Einheiten an Arbeit pro Woche zur Verfügung, die es der Produktion der beiden Güter zuordnen kann. Bestimme welche Qualität ${\textstyle x}$ bzw. ${\textstyle y}$ den Erlös maximiert, wenn der wöchentliche Absatz auf jeden Fall gewährleistet ist. Lösung: Der erzielbare Erlös beträgt

$${\begin{aligned}f\left(x,y\right)=\mathrm {ax} +b\end{aligned}}$$

Die Gesamtarbeitsleitung ist beschränkt:

$${\begin{aligned}g\left(x,y\right)={\mathrm {Ax} }^{2}+{\mathrm {By} }^{2}\leq L\end{aligned}}$$

Die KKT Bedingungen lauten also:

$${\begin{aligned}{\frac {\partial }{\partial x}}L(x,y)&=a+2\lambda \mathrm {Ax} =0\\{\frac {\partial }{\partial y}}L(x,y)=b+2\lambda \mathrm {By} =0&=\\\lambda \left(\mathrm {Ax} ^{2}+\mathrm {By} ^{2}-L\right)&=0\end{aligned}}$$

wobei

$${\begin{aligned}\lambda \leq 0{\mathrm {Ax} }^{2}+{\mathrm {By} }^{2}\leq L\end{aligned}}$$

Falls ${\textstyle \lambda =0}$ folgt aus den ersten beiden Gleichungen unmittelbar ${\textstyle a=b=0}$, im Widerspruch zur Angabe. Für ${\textstyle \lambda <0}$ folgt ${\textstyle x>0,y>0}$, und daher

$${\begin{aligned}\lambda ={\frac {-a}{2Ax}}={\frac {-b}{2By}}\end{aligned}}$$

Somit gilt auch

$${\begin{aligned}y={\frac {\mathrm {Ab} }{\mathrm {Ba} }}x\end{aligned}}$$

Andererseits muss gelten (complementary slackness)

$${\begin{aligned}\mathrm {Ax} ^{2}+\mathrm {By} ^{2}=L\end{aligned}}$$

und wir folgern, dass insgesamt die optimale Lösung erreicht wird für

$${\begin{aligned}x={\sqrt {\frac {L}{a^{2}B+b^{2}A}}}\cdot {\frac {a{\sqrt {B}}}{\sqrt {A}}}y={\sqrt {\frac {L}{a^{2}B+b^{2}A}}}\cdot {\frac {b{\sqrt {A}}}{\sqrt {B}}}\end{aligned}}$$

Aufgabe 9: Untersuche die Funktion

$${\begin{aligned}f\left(x,y\right)=x^{2}+y+1\end{aligned}}$$

auf Extremwerte unter der Nebenbedingung

$${\begin{aligned}g\left(x,y\right)=x+y\leq 4\end{aligned}}$$

Zusammenfassung
 Wir haben einige Aspekte der nichtlinearen Optimierung kennen gelernt. Speziell wurden zur Lösung von mehrdimensionalen Optimierungsaufgaben als hinreichende Bedingungen für lokale Maxima und Minima die Definitheitseigenschaften der Hessematrix angegeben. Für Optimierungsaufgaben mit Nebenbedingungen wurden nur notwendige Bedingungen zum Finden von lokalen Extremstellen besprochen, und zwar die Lagrange-Methode im Falle von Gleichheits-nebenbedingungen, und die Karush-Kuhn-Tucker Bedingungen für Ungleichheits-nebenbedingungen. Als einfache Algorithmen zum Lösen von nichtlinearen Optimierungsaufgaben wurden das Newton-Verfahren und das Gradientenverfahren kurz diskutiert.

Optimierung ist ein weites Feld, und viele interessante Gebiete konnten hier nicht einmal kurz angerissen werden. Eine Liste von gängigen Fragestellungen umfasst Transportprobleme, Zuordnungsprobleme, Netzplantechnik oder das weitläufige Gebiet der ganzzahligen und kombinatorischen Optimierung. Die dort benötigten Techniken unterscheiden sich oft wesentlich von denen die in diesem Kapitel erwähnt wurden, und oftmals finden Konzepte der Graphentheorie Verwendung. Für eine elementare deutschsprachige Einführung sei etwa auf das Buch von Domschke und Drexl (1995) verwiesen.

Wiederholungsaufgaben/Übungen

Aufgabe 1
Untersuche folgende Funktionen auf Extremwerte bzw. Sattelstellen (verwende die Definitheit der Hessematrix, um Entscheidung zu treffen).

$${\begin{aligned}f\left(x,y\right)=x^{2}+y^{2}\end{aligned}}$$

$${\begin{aligned}f(x,y)=(1+x)^{2}-(1-y)^{2}\end{aligned}}$$

$${\begin{aligned}f\left(x,y\right)=\mathrm {xy} \end{aligned}}$$

Aufgabe 2
Führe zu den Funktionen aus Aufgabe 1 jeweils die erste Iteration des Gradientenverfahrens aus, wobei im Punkt (1,1) gestartet wird. Für welche der drei Aufgaben ist die Suche nach einem (lokalen oder globalen) Minimum überhaupt sinnvoll?

Aufgabe 3
Führe für die Funktion

$${\begin{aligned}f\left(x,y\right)=x^{4}+y^{4}\end{aligned}}$$

die ersten beiden Schritte des Newtonverfahrens aus, wenn im Punkt (1,1) gestartet wird.

Aufgabe 4
Finde die Extremwerte der folgenden Funktionen unter den angegebenen Nebenbedingungen:

$${\begin{aligned}f\left(x,y\right)=4x+3y\\\ NB:g\left(x,y\right)=x^{2}+y^{2}=1\end{aligned}}$$

$${\begin{aligned}f\left(x,y\right)=x^{2}+y^{2}\\\ NB:g\left(x,y\right)=2\mathrm {xy} =1\end{aligned}}$$

$${\begin{array}{r}f(x,y)=e^{xy}\\NB:g(x,y)=x+y=1\end{array}}$$

(Gib jeweils Skizzen mit den Niveaulinien an um zu klären, ob es sich um ein Maximum oder ein Minimum handelt).

Aufgabe 5
Ermittle mit Hilfe der KKT-Bedingungen alle Extremstellen der folgenden Funktionen unter den gegebenen Nebenbedingungen

$${\begin{aligned}f(x,y)=(x-1)^{2}+(y-2)^{2}-1\\\ NB:g\left(x,y\right)=x^{2}+y^{2}\leq 1\end{aligned}}$$

$${\begin{aligned}f\left(x,y\right)=x^{2}+3\mathrm {xy} +y^{2}\\\ NB:g\left(x,y\right)=x+y\leq 1\end{aligned}}$$

Stelle die Lösungen wiederum graphisch dar!