Optimierung - Optimierung unter Nebenbedingungen: Unterschied zwischen den Versionen

Aus FernFH MediaWiki
Zur Navigation springen Zur Suche springen
(Die Seite wurde neu angelegt: „== 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 <math display="inline">f\left(x,y\right)</math> unter der Nebenbedingung: <mat…“)
 
(Die Seite wurde geleert.)
Markierung: Geleert
 
Zeile 1: Zeile 1:
== 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 <math display="inline">f\left(x,y\right)</math> unter der Nebenbedingung: <math display="inline">g\left(x,y\right)=x^2+y^2=4</math>, so wird das Maximum auf dem Kreis mit Radius 2 gesucht. Dieser ist die Höhenschichtline der Funktion <math display="inline">g\left(x,y\right)</math> zum Niveau 4. Wenn wir statt der Gleichung die Ungleichung <math display="inline">g\left(x,y\right)=x^2+y^2\le1</math> 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 <math display="inline">-f\left(x,y\right)</math> suchen um das Maximum von <math display="inline">f\left(x,y\right)</math> zu erhalten.
<span id="lagrange-multiplikatoren-gleichungen-als-nebenbedingung"></span>
=== Lagrange – Multiplikatoren – Gleichungen als Nebenbedingung ===
Wir wollen folgende Aufgabe lösen:Finde<math display="block">\begin{aligned}
\mathrm{min\ }f\left(x,y\right)     
\end{aligned}</math>
unter<math display="block">\begin{aligned}
g\left(x,y\right)=c
\end{aligned}</math>
d.h., wir suchen das Minimum der Funktion <math display="inline">f\left(x,y\right)</math> über der Höhenschichtline zum Niveau <math display="inline">c</math> der Funktion <math display="inline">g\left(x,y\right)</math>, wobei wir voraussetzen, dass sowohl <math display="inline">f</math> als auch <math display="inline">g</math> differenzierbar sind. Im ersten Schritt der Methode wird ein '''Lagrange-Multiplikator''', zumeist mit <math display="inline">\lambda</math> bezeichnet (hat nichts mit den Eigenwerten einer Matrix zu tun!), eingeführt. Man definiert die Lagrange-Funktion <math display="inline">L</math> als
<math display="block">\begin{aligned}
L\left(x,y,\lambda\right)=f\left(x,y\right)+\lambda\left(g\left(x,y\right)-c\right)
\end{aligned}</math>
und sucht jene Paare <math display="inline">\left(x_0,y_0\right)</math>, für das es ein Lambda gibt, mit dem die Funktion in <math display="inline">\left(x_0,y_0,\lambda(x_0,y_0\right))</math> ein Minimum annimmt. Die Nebenbedingung steckt nun implizit in der Lagrange-Funktion. Falls die Nebenbedingung erfüllt ist so gilt <math display="inline">L\left(x,y,\lambda\right)=f\left(x,y\right)</math>. Falls die Nebenbedingung nicht erfüllt ist und zum Beispiel <math display="inline">g\left(x_0,y_0\right)>c</math>, so wird die Lagrange-Funktion für diesen Punkt für hinreichen kleines <math display="inline">\lambda</math> beliebig klein, und und die Lagrangefunktion kann in diesem Punkt für kein <math display="inline">\lambda</math> ein Minimum annehmen. Beachten Sie auch: das Kriterium ist etwas anderes als die Suche nach Tripeln <math display="inline">\left(x,y,\ \lambda\right)</math>, welche die Lagrangefunktion minimieren – solche wird man im Allgemeinen nicht finden: gilt nämlich <math display="inline">\left(g\left(x,y\right)-c\right)\neq0</math>, dann gibt es aus den genannten Gründen kein optimales <math display="inline">\lambda</math>!<br>
Das '''Lagrange-Theorem''' besagt nun folgendes: falls <math display="inline">\left(x_0,y_0\right)</math> ein lokales Minimum von <math display="inline">f\left(x,y\right)</math> unter der Nebenbedingung <math display="inline">g\left(x,y\right)=c</math> ist, und falls <math display="inline">\mathrm{\nabla g}(x_0,y_0)\neq(0,0)^T </math>so gibt es eine eindeutige Zahl <math display="inline">\lambda</math>, für welche die Lagrange-Funktion einen stationären Punkt in <math display="inline">\left(x_0,y_0\right)</math> hat, d.h. <math display="inline">\mathrm{\nabla L}(x_0,y_0)=(0,0)^T</math> unter Beibehaltung der Nebenbedingung <math display="inline">g\left(x,y\right)=c</math>. Um Kandidaten zur Lösung der ursprünglichen Aufgabe zu erhalten, muss also das folgende System von Gleichungen gelöst werden:
<math display="block">
\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}
</math>
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.<br>
Beispiel 11:<br>
Ein Verbraucher habe die Nutzenfunktion<math display="block">\begin{aligned}
f\left(x,y\right)=\mathrm{xy}.
\end{aligned}</math>
Maximiere die Nutzenfunktion unter der Budgetbeschränkung<math display="block">\begin{aligned}
g\left(x,y\right)=x+2y=\mathrm{10}.
\end{aligned}</math>
Die Lagrange Funktion lautet:<math display="block">\begin{aligned}
L\left(x,y,\lambda\right)=\mathrm{xy}+\left(x+2y-\mathrm{10}\right)
\end{aligned}</math>
Null setzen der partiellen Ableitungen gibt<math display="block">
\begin{aligned}
\frac{\partial}{\partial x} L(x, y, \lambda) &=y+\lambda=0 \\
\frac{\partial}{\partial y} L(x, y, \lambda)=x+2 \lambda &=0
\end{aligned}
</math>
Elimination von <math display="inline">\lambda</math> aus diese beiden Gleichungen liefert <math display="inline">x-2y=0</math> Und wir haben die Nebenbedingung<math display="block">\begin{aligned}
x+2y=\mathrm{10}
\end{aligned}</math>
Dieses lineare Gleichungssystem mit zwei Variablen hat eine eindeutige Lösung:<math display="block">\begin{aligned}
x = 5, y = 2.5       
\end{aligned}</math>
und schließlich<math display="block">\begin{aligned}
\lambda=-y=-2\mathrm{.}5
\end{aligned}</math>
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 <math display="inline">f</math> und <math display="inline">g</math>, 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:Mt411 bild1 (18).jpg|300px|none|thumb|Optimierung unter Nebenbedingungen]][[Datei:Mt411 bild1 (19).jpg|300px|none|thumb|Optimierung unter Nebenbedingungen]]
Abbildung [[#bild12 |1.4]] zeigt einerseits ausgewählte Niveaulinien der Zielfunktion <math display="inline">f\left(x,y\right)=\mathrm{xy}</math>, anderseits die Gerade <math display="inline">y=5-\frac{x}{2}</math> 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 <math display="inline">(x_0 = 5, y_0 = 2.5)</math> berührt die Gerade die Niveaulinie zum Wert <math display="inline">xy = 12.5</math>. 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 <math display="inline">(x_0, y_0)</math> 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 [[#bild12a |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.<br>
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
<math display="block">
L(x, y, \lambda)=f(x, y)+\lambda g(x, y-c)
</math>
die Lagrangefunktion eines Optimierungsproblems; dann bilden wir die Hessematrix nach allen drei Variablen – allerdings beginnend mit <math display="inline">\lambda</math>:
<math display="block">
\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)
</math>
(der linke obere Eintrag – die zweite Ableitung nach <math display="inline">\lambda</math> – ist immer 0.)<br>
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.<br>
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:<br>
Finde die beiden Extremstellen von<math display="block">\begin{aligned}
f\left(x,y\right)=x^2+y^2
\end{aligned}</math>
unter der Nebenbedingung<math display="block">\begin{aligned}
g\left(x,y\right)=x^2+\mathrm{xy}+2=3
\end{aligned}</math>
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.
<span id="karush-kuhn-tucker-bedingungen"></span>
=== 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 <math display="inline">x\geq0</math> erfüllen muss. Das allgemeine Problem in zwei Variablen mit einer Nebenbedingung hat die Form: Finde<math display="block">\begin{aligned}
\mathrm{max\ (}f(x,y))     
\end{aligned}</math>
unter<math display="block">\begin{aligned}
g\left(x,y\right)\le c
\end{aligned}</math>
D.h., wir suchen das Minimum der Funktion <math display="inline">f\left(x,y\right)</math> über einem Bereich, der von der Höhenschichtline zum Niveau c der Funktion <math display="inline">g\left(x,y\right)</math> begrenzt wird, wobei wir wieder voraussetzen, dass sowohl f als auch g differenzierbar sind. Die Menge aller <math display="inline">\left(x,y\right)</math> 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 <math display="inline">g\left(x,y\right)=c</math> 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<math display="block">\begin{aligned}
L\left(x,y,\lambda\right)=f\left(x,y\right)+\lambda\left(g\left(x,y\right)-c\right)
\end{aligned}</math>
definiert, allerdings gilt hier für die Lagrange Multiplikatoren&nbsp;<math display="inline">\lambda\le0</math>. Entscheidend ist nun die sogenannte komplementäre Schlaffheitsbedingung (complementary slackness). Man fordert, dass entweder die Nebenbedingung exakt erfüllt ist (d.h. <math display="inline">g\left(x,y\right)=c</math>), oder aber der Lagrange Multiplikator<math display="inline">\lambda=0</math>. Diese Bedingung ist erfüllt falls<math display="block">\begin{aligned}
\lambda\left(g\left(x,y\right)-c\right)=0
\end{aligned}</math>
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 <math display="inline">\lambda=0</math> 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 <math display="inline">f\left(x,y\right)</math> und <math display="inline">g\left(x,y\right)</math> (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:<br>
<math display="block">
\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}
</math>
Beispiel 12:<br>
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.:<br>
&nbsp;Produkt 1: Für Preis <math display="inline">ax</math> bedarf es <math display="inline">Ax^2</math> Arbeitseinheiten<br>
&nbsp;Produkt 2: Für Preis <math display="inline">by</math> bedarf es <math display="inline">By^2</math> Arbeitseinheiten<br>
&nbsp;wobei alle Konstanten <math display="inline">(a,b, A,B)</math> größer als 0 sein sollen.<br>
&nbsp;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 <math display="inline">x</math> bzw. <math display="inline">y</math> den Erlös maximiert, wenn der wöchentliche Absatz auf jeden Fall gewährleistet ist. Lösung: Der erzielbare Erlös beträgt<math display="block">\begin{aligned}
f\left(x,y\right)=\mathrm{ax}+b
\end{aligned}</math>
Die Gesamtarbeitsleitung ist beschränkt:<math display="block">\begin{aligned}
g\left(x,y\right)={\mathrm{Ax}}^2+{\mathrm{By}}^2\le L
\end{aligned}</math>
Die KKT Bedingungen lauten also:
<math display="block">
\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}
</math>
wobei<math display="block">\begin{aligned}
\lambda\le0  {\mathrm{Ax}}^2+{\mathrm{By}}^2\le L
\end{aligned}</math>
Falls <math display="inline">\lambda=0</math> folgt aus den ersten beiden Gleichungen unmittelbar <math display="inline">a=b=0</math>, im Widerspruch zur Angabe. Für <math display="inline">\lambda<0</math> folgt <math display="inline">x>0,y>0</math>, und daher<math display="block">\begin{aligned}
\lambda=\frac{-a}{2Ax}=\frac{-b}{2By}
\end{aligned}</math>
Somit gilt auch<math display="block">\begin{aligned}
y=\frac{\mathrm{Ab}}{\mathrm{Ba}}x
\end{aligned}</math>
Andererseits muss gelten (complementary slackness)<math display="block">\begin{aligned}
\mathrm{Ax}^2+\mathrm{By}^2=L
\end{aligned}</math>
und wir folgern, dass insgesamt die optimale Lösung erreicht wird für<math display="block">\begin{aligned}
x=\sqrt{\frac{L}{a^2B+b^2A}}\cdot\frac{a\sqrt{B}}{\sqrt{A}}
y=\sqrt{\frac{L}{a^2B+b^2A}}\cdot\frac{b\sqrt{A}}{\sqrt{B}}
\end{aligned}</math>
Aufgabe 9: Untersuche die Funktion<math display="block">\begin{aligned}
f\left(x,y\right)=x^2+y+1
\end{aligned}</math>
auf Extremwerte unter der Nebenbedingung<math display="block">\begin{aligned}
g\left(x,y\right)=x+y\le4
\end{aligned}</math>
Zusammenfassung<br>
&nbsp;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.

Aktuelle Version vom 26. Mai 2023, 07:13 Uhr

Abgerufen von „https://mediawiki.fernfh.ac.at/mediawiki/index.php?title=Optimierung_-_Optimierung_unter_Nebenbedingungen&oldid=4479“