Content

24. Nichtlineare Optimierung im Rn in:

Michael Merz, Mario V. Wüthrich

Mathematik für Wirtschaftswissenschaftler, page 701 - 752

Die Einführung mit vielen ökonomischen Beispielen

1. Edition 2012, ISBN print: 978-3-8006-4482-7, ISBN online: 978-3-8006-4483-4, https://doi.org/10.15358/9783800644834_701

Bibliographic information
Teil VIII Optimierung im Rn Kapitel24 Nichtlineare Optimierung im Rn Kapitel 24 Nichtlineare Optimierung im Rn 24.1 Grundlagen In Abschnitt 18.1 wurde bereits erläutert, dass viele wirtschaftswissenschaftliche Problemstellungen als Optimierungsprobleme formuliert werden können und die mathematische Umsetzung des ökonomischen Prinzips in der Formulierung eines geeigneten Minimierungs- oder Maximierungsproblems besteht (vgl. auch Abbildung 18.1). Die Lösung von Optimierungsproblemen ist daher in vielen wirtschaftswissenschaftlichen Bereichen von großer praktischer Bedeutung. Die in Kapitel 18 bereitgestellten notwendigen und hinreichenden Bedingungen für lokale und globale Minima und Maxima reeller Funktionen sind jedoch zur Lösung vieler ökonomischer Optimierungsprobleme nicht ausreichend. Die Gründe hierfür sind, dass in den Wirtschaftswissenschaften a) zum einen die zu optimierenden Ziel- oder Nutzenfunktionen oft nicht nur von einer Variablen x, sondern von mehreren unabhängigen Variablen x1, . . . , xn abhängen und b) zum anderen, dass häufig durch die Problemstellung vorgegebene Nebenbedingungen, wie zum Beispiel Budgetbeschränkungen im Falle der Nutzenmaximierung, zu berücksichtigen sind. Aus diesen Gründen wird im Folgenden das Optimierungskalkül für reellwertige Funktionen in einer Variablen mit Hilfe der in Kapitel 22 entwickelten Differentialrechnung auf reellwertige Funktionen f : D ⊆ Rn −→ R in n Variablen verallgemeinert. Hierbei werden zuerst Optimierungsprobleme ohne Nebenbedingungen (siehe Abschnitt 24.2) und anschließend Optimierungsprobleme mit Nebenbedingungen in Form von Gleichungen (siehe Abschnitt 24.3), Ungleichungen (siehe Abschnitt 24.5) oder beidem (vgl. Abschnitt 24.6) betrachtet. Da hierbei sowohl die zu optimierende Zielfunktion als auch die Gleichungen und Ungleichungen, welche die Nebenbedingungen beschreiben, nichtlineare Funktionen der n unabhängigen Variablen x1, . . . , xn sein können, wird dieser Bereich der Optimierungstheorie als nichtlineare Optimierung bezeichnet. Der einfachere, aber deutlich speziellere Bereich der Optimierungstheorie, der sowohl eine lineare Zielfunktion als auch lineare Nebenbedingungen voraussetzt, wird dagegen als lineare Optimierung bezeichnet und ist Gegenstand von Kapitel 25. 24.2 Optimierung ohne Nebenbedingungen Im Folgenden wird sich zeigen, dass das Optimierungskalkül für Optimierungsprobleme ohne Nebenbedingungen weitgehend analog zu dem für reellwertige Funktionen in einer Variablen ist. Notwendige Bedingung für Extrema P. de Fermat auf einer Briefmarke Der nächste Satz liefert eine notwendige Bedingung für ein (lokales oder globales) Minimum und Maximum in einem inneren Punkt x0 ∈ D◦ des Definitionsbereichs D einer partiell differenzierbaren Funktion f : D ⊆ Rn −→ R (für die Definition der Begriffe innerer Punkt und Inneres einer Menge siehe Definition 21.15). Er ist damit das Analogon zu dem nach dem französischen Mathematiker und Juristen Pierre de Fermat (1608–1665) benannten Kriterium von Fermat für reellwertige Funktionen in einer Variablen (vgl. Satz 16.24 in Abschnitt 16.7). Satz 24.1 (Kriterium von Fermat für reellwertige Funktionen in n Variablen) Es sei f : D ⊆ Rn −→ R eine partiell differenzierbare Funktion, welche im inneren Punkt x0 ∈ D◦ ein (lokales oder globales) Minimum oder Maximum besitzt. Dann gilt grad f (x0) = ( ∂f (x0) ∂x1 , . . . , ∂f (x0) ∂xn )T = 0. (24.1) Beweis: Nach Voraussetzung ist die reellwertige Funktion in einer Variablen hi : (−ε, ε) −→ R, t %→ hi(t) := f (x0 + tei ) für i = 1, . . . , n und ein geeignetes ε > 0 differenzierbar und besitzt an der Stelle t = 0 ein (lokales oder globales) Extremum. Mit dem Kriterium von Fermat für reellwertige Funktionen in 708 Kapitel 2424.2 Optimierung ohne Nebenbedingungen einer Variablen (vgl. Satz 16.24) erhält man somit für die partiellen Ableitungen von f an der Stelle x0 ∂f (x0) ∂xi = h′i (0) = 0 für alle i = 1, . . . , n und damit insbesondere die Behauptung (24.1). Ein x0 ∈ D◦ mit der Eigenschaft (24.1) und der zugehörige Punkt (x0, f (x0)) auf dem Graphen von f werden analog zum eindimensionalen Fall wieder als stationäre Stelle bzw. stationärer Punkt von f bezeichnet. Für den Spezialfall n = 1 erhält man aus dem Fermatschen Kriterium die notwendige Bedingung für (lokale oder globale) Extrema einer differenzierbaren Funktion in nur einer Variablen f : (a, b) −→ R. Der Satz 24.1 ist für die Ermittlung von Extrema sehr hilfreich, da das Fermatsche Kriterium bei partiell differenzierbaren Funktionen häufig leicht nachgeprüft werden kann. Es besagt, dass man sich bei der Suche nach den Extremalstellen einer partiell differenzierbaren Funktion f : D ⊆ Rn −→ R im Inneren von D auf die Bestimmung der stationären Stellen von f beschränken kann. Hierzu ist das – in der Regel nichtlineare – Gleichungssystem ∂f (x) ∂x1 = 0 ∂f (x) ∂x2 = 0 ... ∂f (x) ∂xn = 0 (24.2) nach den n Variablen x = (x1, . . . , xn)T aufzulösen. Es ist jedoch zu beachten, dass das Kriterium von Fermat, wie auch im eindimensionalen Fall, nur eine notwendige, aber keine hinreichende Bedingung darstellt. Das heißt, stationäre Punkte sind lediglich Kandidaten für Extrema, die an Stellen im Inneren D◦ des Definitionsbereichs D liegen. Sie müssen nicht notwendigerweise auch tatsächlich Extrema sein (siehe Beispiel 24.2b)). Zur endgültigen Entscheidung, welche stationären Stellen Extremalstellen sind und welche nicht, werden hinreichende Bedingungen benötigt (siehe hierzu den folgenden Satz 24.3). Stationäre Punkte, die keine Extrema sind, werden als Sattel- oder Terrassenpunkte bezeichnet. Weiter ist zu beachten, dass das Kriterium (24.1) keine Aussage über Stellen macht, die auf dem Rand ∂D des Definitionsbereichs D liegen oder an denen die Funktion f nicht partiell differenzierbar ist. Im Falle der Existenz solcher Stellen müssen diese gesondert darauf untersucht werden, ob sie Extremalstellen der Funktion f sind oder nicht (vgl. Beispiel 24.13). Bei der Suche nach den lokalen und globalen Extremalstellen einer reellwertigen Funktion f : D ⊆ Rn −→ R müssen somit die folgenden drei Arten von Stellen x0 ∈ D untersucht werden: 1) Innere Stellen x0 ∈ D◦ mit grad f (x0) = 0, also die stationären Stellen von f 2) Innere Stellen x0 ∈ D◦, an denen f nicht partiell differenzierbar ist 3) Randstellen x0 ∈ ∂D des Definitionsbereichs D Grundsätzlich kommen alle Stellen x0 ∈ D, die zu einer dieser drei Arten gehören, als lokale oder globale Extremalstellen der Funktion f in Frage. Falls jedoch die Funktion f als Definitionsbereich den Rn oder eine offene Menge D ⊆ Rn besitzt, müssen zur Bestimmung der Extremalstellen lediglich die ersten beiden Arten von Stellen untersucht werden. Ist die Funktion f zusätzlich auch noch partiell differenzierbar, dann sind durch die stationären Stellen von f bereits alle Kandidaten für lokale und globale Extremalstellen gegeben. Beispiel 24.2 (Stationäre Stellen) a) Die reellwertige Funktion f : R3 −→ R, (x, y, z) %→f (x, y, z)=(2−x)4+4e2y2 +(z−4)2+3 nimmt für alle (x, y, z) ∈ R3 wegen (2 − x)4 ≥ 0, 4e2y2 ≥ 4 und (z− 4)2 + 3 ≥ 3 positive Werte an, die größer oder gleich 7 sind. Somit weist f an der Stelle (2, 0, 4) eine globale Minimalstelle auf und das globale Minimum von f beträgt f (2, 0, 4) = 7. Die Funktion f ist ferner partiell differenzierbar und besitzt die ersten partiellen Ableitungen ∂f (x, y, z) ∂x = −4(2 − x)3, ∂f (x, y, z) ∂y = 16ye2y2 und ∂f (x, y, z) ∂z = 2(z− 4). Zur Bestimmung der stationären Stellen von f ist somit das (nichtlineare) Gleichungssystem −4(2 − x)3 = 0 16ye2y 2 = 0 2(z− 4) = 0 709 Kapitel 24 Nichtlineare Optimierung im Rn zu lösen. Es ist leicht zu erkennen, dass es die eindeutige Lösung (2, 0, 4) besitzt. Folglich gilt grad f (2, 0, 4) = (0, 0, 0)T und die einzige stationäre Stelle (2, 0, 4) ist die globale Minimalstelle von f . b) Die reellwertige Funktion f : R2 −→ R, (x, y) %→ f (x, y) = 2x4 + y4 − 2x2 − 2y2 ist partiell differenzierbar und besitzt die ersten partiellen Ableitungen ∂f (x, y) ∂x = 8x3 − 4x = 4x(2x2 − 1) und ∂f (x, y) ∂y = 4y3 − 4y = 4y(y2 − 1). (24.3) Durch Lösen des (nichtlinearen) Gleichungssystems 4x(2x2 − 1) = 0 4y(y2 − 1) = 0 erhält man folglich die stationären Stellen von f . Die erste Gleichung besitzt offensichtlich die drei Lösungen 0, √ 2 2 ,− √ 2 2 und die zweite Gleichung die drei x −1.0 −0.5 0.0 0.5 1.0 y −1.0 −0.5 0.0 0.5 1.0 −1.0 −0.5 0.0 0.5 1.0 f (x, y) = 2x4 + y4 − 2x2 − 2y2 x −1.0 −0.5 0.0 0.5 1.0 y −1.0 −0.5 0.0 0.5 1.0 −1.0 −0.5 0.0 0.5 1.0 f (x, y) = 2x4 + y4 − 2x2 − 2y2 l p1 l p2 l p3 l p4 l p5 l p6 lp7 l p8 lp9 Abb. 24.1: Reellwertige Funktion f : R2 −→ R, (x, y) %→ f (x, y) = 2x4 + y4 − 2x2 − 2y2 (links) und die reellwertige Funktion f mit den eingezeichneten stationären Punkten (rechts) Lösungen 0, 1,−1. Die Funktion f besitzt daher insgesamt die folgenden neun stationären Stellen: (x1, y1) (x2, y2) (x3, y3) (x4, y4) (x5, y5) (0, 0) (0, 1) (0,−1) (√ 2 2 , 0 ) (√ 2 2 , 1 ) (x6, y6) (x7, y7) (x8, y8) (x9, y9) (√ 2 2 ,−1 ) ( − √ 2 2 , 0 ) ( − √ 2 2 , 1 ) ( − √ 2 2 ,−1 ) Bezeichnet pi :=(xi, yi, f (xi, yi)) für i=1, 2, . . . , 9 den zur stationären Stelle (xi, yi) gehörenden stationären Punkt auf dem Graphen von f , dann ist aus Abbildung 24.1 ersichtlich, dass f an der Stelle p1 ein lokales Maximum, an den Stellen p5, p6, p8, p9 lokale Minima und an den Stellen p2, p3, p4, p7 Sattelpunkte besitzt. Dies zeigt, dass stationäre Punkte nicht notwendigerweise auch Extrema sein müssen. Hinreichende Bedingungen für Extrema Das Beispiel 24.2b) zeigt, dass grad f (x0) = 0 keine hinreichende Bedingung dafür ist, dass es sich bei x0 um eine Extremalstelle von f handelt. Aus Abschnitt 18.3 ist jedoch bekannt, dass bei reellwertigen Funktionen in einer Variablen 710 Kapitel 2424.2 Optimierung ohne Nebenbedingungen das Vorzeichen der zweiten Ableitung eine hinreichende Bedingung für lokale und globale Extrema liefert. Wie der folgende Satz zeigt, verhält sich dies für reellwertige Funktionen in n Variablen ähnlich. An die Stelle des Vorzeichens der zweiten Ableitung tritt nun jedoch die Definitheitseigenschaft der Hesse-Matrix mit den n2 zweiten partiellen Ableitungen. Satz 24.3 (Hinreichende Bedingung für lokale Extrema) Es sei f : D ⊆ Rn −→ R eine zweimal stetig partiell differenzierbare Funktion auf einer offenen Menge D mit grad f (x0) = 0 und der Hesse-Matrix Hf (x0) für ein x0 ∈ D. Dann gilt: a) Hf (x0) positiv definit (d. h. xT Hf (x0) x > 0 für alle x ∈ Rn \ {0}) ⇒ x0 ist eine lokale Minimalstelle von f b) Hf (x0) negativ definit (d. h. xT Hf (x0) x < 0 für alle x ∈ Rn \ {0}) ⇒ x0 ist eine lokale Maximalstelle von f c) Hf (x0) indefinit (d. h. es existieren x, y ∈ Rn mit xT Hf (x0) x < 0 und yT Hf (x0) y > 0) ⇒ x0 ist keine lokale Extremalstelle, sondern die Stelle eines Sattelpunktes von f d) f besitzt in x0 eine lokale Minimalstelle ⇒ Hf (x0) ist positiv semidefinit (d. h. xT Hf (x0) x ≥ 0 für alle x ∈ Rn) e) f besitzt in x0 eine lokale Maximalstelle ⇒ Hf (x0) ist negativ semidefinit (d. h. xT Hf (x0) x ≤ 0 für alle x ∈ Rn) Beweis: Die Funktion f ist nach Voraussetzung zweimal stetig partiell differenzierbar mit grad f (x0) = 0. Gemäß Satz 22.42 (mit m = 1) gilt daher f (x)=f (x0)+grad f (x0)T (x−x0)+ 1 2 (x−x0)T Hf (ξ) (x−x0) =f (x0)+ 1 2 (x − x0)T Hf (ξ) (x − x0) (24.4) mit ξ = λx0 + (1 − λ)x für ein geeignetes λ ∈ (0, 1). Zu a): Ist Hf (x0) positiv definit, dann gilt (x−x0)T Hf (x0) (x−x0) > 0 für alle x = x0. Da die partiellen Ableitungen ∂2f (x)∂xj ∂xi alle stetig sind, existiert ein r > 0, so dass (x − x0)T Hf (y) (x − x0) > 0 für alle y ∈ K<(x0, r) = {y ∈ Rn : ‖y − x0‖ < r} gilt. Mit (24.4) erhält man folglich f (x)− f (x0) = 1 2 (x − x0)T Hf (ξ) (x − x0) > 0 für alle x ∈ K<(x0, r) mit x = x0. Das heißt, x0 ist eine lokale Minimalstelle von f . Zu b): Ist Hf (x0) negativ definit, dann zeigt man analog zu a), dass es ein r > 0 gibt mit f (x)− f (x0) = 1 2 (x − x0)T Hf (ξ) (x − x0) < 0 für alle x ∈ K<(x0, r) mit x = x0. Das heißt, x0 ist eine lokale Maximalstelle von f . Zu c): Ist Hf (x0) indefinit, dann erhält man weitgehend analog zu a), dass es für alle r > 0 zwei Vektoren x, y ∈ K<(x0, r) mit f (x)− f (x0) < 0 und f (y)− f (x0) > 0 gibt. Das heißt, es gilt f (x) < f (x0) < f (y) und x0 ist damit keine lokale Extremalstelle von f . Zu d): Da die Funktion f an der Stelle x0 eine lokale Minimalstelle besitzt, folgt mit (24.4), dass 0 ≤ f (x0 + εv)− f (x0) = 1 2 εvT Hf (ξ) εv für ein beliebiges v ∈ Rn, ein hinreichend kleines ε > 0 und ξ = x0 +λεv für ein geeignetes λ ∈ (0, 1) gilt. Dies impliziert vT Hf (ξ) v ≥ 0 für alle v ∈ Rn. Aufgrund der Stetigkeit der partiellen Ableitungen ∂ 2f (x) ∂xj ∂xi erhält man daraus durch Grenz- übergang lim ε→0 v T Hf (ξ) v = vT Hf (x0) v ≥ 0. Das heißt, Hf (x0) ist positiv semidefinit. Zu e): Zeigt man analog zu d). Der Satz 24.3 ist das Analogon der Folgerung 18.8 für reellwertige Funktionen in einer Variablen. Er besagt, dass bei einer zweimal stetig partiell differenzierbaren Funktion die Definitheitseigenschaft der Hesse-Matrix Hf (x0) Auskunft darüber gibt, ob es sich bei einer stationären Stelle x0 um eine lokale Minimalstelle, eine lokale Maximalstelle oder um einen Sattelpunkt handelt. Dabei ist zu beachten, dass positive (negative) Semidefinitheit von Hf (x0) keine hinreichende Bedingung dafür ist, dass eine stationäre Stelle x0 eine lokale Minimalstelle (Maximalstelle) ist. Aus positiver (negativer) Semidefinitheit folgt lediglich, dass es sich bei der stationären Stelle x0 um keine lokale Maximalstelle (Minimalstelle) handeln kann, also x0 eine lokale Mimimalstelle (Maximalstelle) oder ein Sattelpunkt ist. Darüber hinaus macht Satz 24.3 keine Aussagen über reellwertige Funktionen, die nicht zweimal stetig partiell differenzierbar sind (vgl. Abbildung 24.2). 711 Kapitel 24 Nichtlineare Optimierung im Rn Minima Maxima Sattelpunkte positiv definit negativ definit positiv semidefinit negativ semidefinit indefinit Abb. 24.2: Zusammenhang zwischen der Definitheitseigenschaft der Hesse-Matrix Hf (x0) (falls sie existiert) und der Extremal- oder Sattelpunkteigenschaft der Stelle x0 bei einer reellwertigen Funktion f : D ⊆ Rn −→ R Aus Satz 24.3d) und e) erhält man zusammen mit Satz 22.45a) und b), dass bei einer zweimal stetig partiell differenzierbaren Funktion f : D ⊆ Rn −→ R Maximalstellen nur in Bereichen auftreten, in denen f konkav ist, und Minimalstellen nur in Bereichen liegen können, in denen f konvex ist. Aus Satz 24.3 erhält man unmittelbar die folgende hinreichende Bedingung für globale Extrema: Folgerung 24.4 (Hinreichende Bedingung für globale Extrema) Es seien f : D ⊆ Rn −→ R eine zweimal stetig partiell differenzierbare Funktion auf einer offenen Menge D und x0 ∈ D mit grad f (x0) = 0. Dann gilt: a) Hf (x) positiv definit für alle x ∈ D ⇒ x0 ist eine globale Minimalstelle von f b) Hf (x) negativ definit für alle x ∈ D ⇒ x0 ist eine globale Maximalstelle von f Beweis: Zu a): Analog zum Beweis von Satz 24.3a) erhält man, dass nun f (x) > f (x0) für alle x ∈ D gilt. Das heißt, x0 ist eine globale Minimalstelle von f . Zu b). Der Beweis verläuft analog zu a). Besonders einfach ist die Ermittlung von globalen Extrema im Falle von konvexen und konkaven Funktionen. In Satz 21.43 wurde bereits gezeigt, dass bei einer konvexen Funktion jedes lokale Minimum auch ein globales Minimum und bei einer konkaven Funktion jedes lokale Maximum auch ein globales Maximum ist. Darüber hinaus gilt der folgende Satz, der besagt, dass es bei einer konvexen (konkaven) Funktion nicht notwendig ist, die durch Folgerung 24.4 gegebene hinreichende Bedingung für ein globales Minimum (Maximum) zu überprüfen. Es reicht stets aus, wenn die oftmals relativ leicht zu überprüfende notwendige Bedingung grad f (x0)=0 erfüllt ist. Satz 24.5 (Globale Extremalstellen bei konvexen und konkaven Funktionen I) Es seien f : D ⊆ Rn −→ R eine partiell differenzierbare Funktion auf einer offenen und konvexen Menge D und x0 ∈ D mit grad f (x0) = 0. Dann gilt: a) f konvex ⇒ x0 ist globale Minimalstelle von f . b) f konkav ⇒ x0 ist globale Maximalstelle von f . Beweis: Zu a): Es sei angenommen, dass x0 keine globale Minimalstelle ist. Dann existiert ein x1 ∈ D mit x1 = x0 und f (x0) > f (x1). Daraus folgt zusammen mit der Konvexität von f f ((1 − λ)x0 + λx1) ≤ (1 − λ)f (x0)+ λf (x1) < (1 − λ)f (x0)+ λf (x0) = f (x0) für λ ∈ (0, 1) beliebig nahe bei 0. Das heißt, dass in jeder Umgebung von x0 Funktionswerte echt kleiner als f (x0) zu finden sind. Dies steht jedoch im Widerspruch zu der Annahme, dass x0 eine stationäre Stelle von f ist. Zu b): Wenn die Funktion f konkav ist, dann ist −f konvex und gemäß Aussage a) ist x0 damit eine globale Minimalstelle von −f . Daraus folgt aber, dass x0 eine globale Maximalstelle von f ist. Im Allgemeinen kann eine reellwertige Funktion f : D ⊆ R n −→ R mehrere globale Minimal- und Maximalstellen besitzen. Eine streng konvexe (konkave) Funktion f kann jedoch höchstens eine globale Minimalstelle (Maximalstelle) aufweisen. Satz 24.6 (Globale Extremalstellen bei konvexen und konkaven Funktionen II) Es sei f : D ⊆ Rn −→ R eine reellwertige Funktion auf einer offenen und konvexen Menge D. Dann gilt: a) f streng konvex ⇒ f besitzt höchstens eine globale Minimalstelle. b) f streng konkav ⇒ f besitzt höchstens eine globale Maximalstelle. 712 Kapitel 2424.2 Optimierung ohne Nebenbedingungen Beweis: Zu a): Es sei angenommen, dass x0 und x1 zwei verschiedene globale Minimalstellen von f sind. Dann gilt f (x0) ≤ f (x1) und f (x1) ≤ f (x0), also f (x0) = f (x1). Zusammen mit der strengen Konvexität von f impliziert dies f ( 1 2 x0 + 1 2 x1 ) < 1 2 f (x0)+ 1 2 f (x1) = 1 2 f (x0)+ 1 2 f (x0) = f (x0) . Dies ist jedoch ein Widerspruch dazu, dass x0 eine globale Minimalstelle von f ist. Zu b): Zeigt man völlig analog zu a). Die obigen notwendigen und hinreichenden Bedingungen legen das folgende zweistufige Verfahren zur Bestimmung von Extremalstellen einer zweimal stetig partiell differenzierbaren Funktion f : D ⊆ Rn −→ R auf einer offenen Menge D nahe: 1) Berechne den Gradienten grad f (x) der Funktion f und ermittle anschließend die stationären Stellen x0 von f als Lösungen des Gleichungssystems (24.2). 2) Bestimme für die ermittelten stationären Stellen x0 jeweils die Hesse-Matrix Hf (x0) und untersuche ihre Definitheitseigenschaft. Zur Untersuchung der Definitheitseigenschaft der Hesse-Matrix Hf (x0) können neben der jeweiligen Definition (in Satz 24.3 jeweils in Klammern angegeben) auch die in Abschnitt 10.7 vorgestellten Zusammenhänge zwischen den Definitheitseigenschaften einer symmetrischen Matrix und ihren Hauptdiagonaleinträgen (vgl. Beispiel 24.7), Eigenwerten sowie Hauptminoren (vgl. Beispiele 24.9, 24.11 und 24.12) herangezogen werden. Das folgende Beispiel demonstriert, wie mit Hilfe von Satz 24.3 und Folgerung 24.4 die Extrema einer zweimal stetig partiell differenzierbaren Funktion ermittelt werden können. Beispiel 24.7 (Hinreichende Bedingung für Extrema) a) Die reellwertige Funktion f : R2 −→ R, (x, y) %→ f (x, y) = x2 + y2 ist zweimal stetig partiell differenzierbar und für ihren Gradienten gilt grad f (x, y) = (2x, 2y)T . Die stationären Stellen von f erhält man als Lösungen des Gleichungssystems 2x = 0 2y = 0, welches offensichtlich nur die eine Lösung x0 := (0, 0)T besitzt. Die Hesse-Matrix von f an einer beliebigen Stelle (x, y) ∈ R2 lautet Hf (x, y) = ( 2 0 0 2 ) . Da Hf (x, y) eine Diagonalmatrix mit ausschließlich positiven Hauptdiagonaleinträgen ist, folgt mit Satz 10.32, dass die Hesse-Matrix Hf (x, y) für alle (x, y) ∈ R2 positiv definit ist. Mit Folgerung 24.4a) erhält man somit, dass f bei der stationären Stelle x0 ein globales Minimum besitzt (vgl. Abbildung 24.3, links). b) Die reellwertige Funktion f : R2 −→ R, (x, y) %→ f (x, y) = x2 − y2 ist zweimal stetig partiell differenzierbar. Für ihren Gradienten gilt grad f (x, y) = (2x,−2y)T und die stationären Stellen von f erhält man als Lösungen des Gleichungssystems 2x = 0 −2y = 0, welches ebenfalls nur die eine Lösung x0 := (0, 0)T besitzt. Für die Hesse-Matrix an einer beliebigen Stelle (x, y) ∈ R2 gilt Hf (x, y) = ( 2 0 0 −2 ) . Da die Hesse-Matrix Hf (x, y) einen positiven und einen negativen Hauptdiagonaleintrag besitzt, ist sie gemäß Satz 10.32e) indefinit. Mit Satz 24.3c) erhält man daher, dass bei der stationären Stelle x0 kein Extremum, sondern ein Sattelpunkt liegt (vgl. Abbildung 24.3, rechts). c) Die reellwertige Funktion f : R3 −→ R, (x, y, z) %→ f (x, y, z) = 2 3 x3 − 3 2 y2 − 2z2 + yz − 8x + y + 7z− 3 713 Kapitel 24 Nichtlineare Optimierung im Rn ist zweimal stetig partiell differenzierbar und für ihren Gradienten erhält man grad f (x,y,z)=(2x2−8,−3y+z+1,−4z+y+7)T . Dies führt zum Gleichungssystem 2x2 − 8 = 0 −3y + z+ 1 = 0 −4z+ y + 7 = 0, welches die beiden Lösungen x0 := (2, 1, 2)T und x1 := (−2, 1, 2)T besitzt. Das heißt, es gilt grad f (2, 1, 2) = 0 und grad f (−2, 1, 2) = 0. Die Hesse-Matrix von f an einer beliebigen Stelle (x, y, z) ∈ R3 ist gegeben durch Hf (x, y, z) = ⎛ ⎝ 4x 0 0 0 −3 1 0 1 −4 ⎞ ⎠ . Daraus folgt für die Hesse-Matrix an der stationären Stelle x0 Hf (x0) = ⎛ ⎝ 8 0 0 0 −3 1 0 1 −4 ⎞ ⎠ . (24.5) Diese Hesse-Matrix Hf (x, y, z) ist nach Satz 10.32e) indefinit und mit Satz 24.3c) folgt daher, dass die Funktion f bei x0 einen Sattelpunkt besitzt. Für die Hesse-Matrix von f an der stationären Stelle x1 gilt dagegen Hf (x1) = ⎛ ⎝ −8 0 0 0 −3 1 0 1 −4 ⎞ ⎠ . (24.6) Da Satz 10.32 in diesem Fall keine eindeutige Aussage über die Definitheitseigenschaft von Hf (x1) macht, wird für einen beliebigen Vektor (a, b, c) ∈ R 3 \ {0} das Produkt ( a,b,c ) Hf (x1) ⎛ ⎝ a b c ⎞ ⎠=(a, b, c) ⎛ ⎝ −8 0 0 0 −3 1 0 1 −4 ⎞ ⎠ ⎛ ⎝ a b c ⎞ ⎠ =−8a2 − 3b2 − 4c2 + 2bc =−8a2 − 2b2 − 3c2 − (b − c)2 betrachtet. Es ist zu erkennen, dass ( a, b, c ) Hf (x1) ⎛ ⎝ a b c ⎞ ⎠ < 0 für alle (a, b, c) ∈ R3\{0} gilt. Das heißt, die Hesse- Matrix von f ist an der Stelle x1 negativ definit. Mit Satz 24.3b) erhält man folglich, dass die Stelle x1 eine lokale Maximalstelle von f ist. Ferner gilt lim x→∞ f (x, y, z)=∞ und limx→−∞ f (x, y, z)=−∞. Die Funktion f ist somit weder nach oben, noch nach unten beschränkt. Es existiert daher weder ein globales Maximum, noch ein globales Minimum. Das folgende – etwas umfangreichere – Anwendungsbeispiel zeigt, wie im Rahmen einer komparativ-statischen Analyse mit Hilfe der obigen notwendigen und hinreichenden Bedingungen für Extrema das gewinnmaximierende Verhalten eines Unternehmens analysiert werden kann. Beispiel 24.8 (Gewinnmaximierendes Verhalten eines Unternehmens) Betrachtet wird ein Unternehmen, das ein Produkt A mit Hilfe von n verschiedenen Produktionsfaktoren herstellt. Die Produktionsmenge y von Produkt A in Abhängigkeit von den Faktormengen x = (x1, . . . , xn)T wird dabei durch eine zweimal stetig partiell differenzierbare Produktionsfunktion f : (0,∞)n −→ R, x %→ y = f (x) ausgedrückt. Bezeichnet p den Preis, für den das Produkt A auf dem Markt abgesetzt werden kann und q := (q1, . . . , qn) T den Vektor mit den Beschaffungspreisen für die n benötigten Produktionsfaktoren, dann ist der Gewinn des Unternehmens gegeben durch G(x) := pf (x)− qT x. (24.7) In der ökonomischen Theorie der Unternehmung wird davon ausgegangen, dass Unternehmungen das Gewinn- 714 Kapitel 2424.2 Optimierung ohne Nebenbedingungen x −2 −1 0 1 2 y −2 −1 0 1 22 4 6 8 f (x, y) = x2 + y2 x −2 −1 0 1 2 y −2 −1 0 1 2−2 0 2 f (x, y) = x2 − y2 Abb. 24.3: Graphen der reellwertigen Funktionen f : R2 −→ R, (x, y) %→ x2 + y2 (links) und f : R2 −→ R, (x, y) %→ x2 − y2 (rechts) maximierungsziel verfolgen. Das heißt, sie sind an der Faktormengenkombination x∗ = (x∗1 , . . . , x∗n)T ∈ (0,∞)n interessiert, für die der Gewinn maximiert wird, also G(x∗) = max x∈(0,∞)n G(x) gilt. Für die optimale Faktormengenkombination x∗ erhält man aus (24.7) durch partielles Ableiten nach den einzelnen Faktormengen x1, . . . , xn und anschließendes Nullsetzen die notwendige Bedingung ∂G(x∗) ∂xi = p ∂f (x ∗) ∂xi − qi = 0 (24.8) für alle i = 1, . . . , n bzw. in Vektorschreibweise gradG(x∗) = ( ∂G(x∗) ∂x1 , . . . , ∂G(x∗) ∂xn )T = p grad f (x∗)− q = 0. (24.9) Durch (24.8) wird das bekannte Grenzproduktivitätsprinzip ausgedrückt. Es besagt, dass im Gewinnmaximum G(x∗) der i-te Produktionsfaktor nur in dem Ausmaß x∗i eingesetzt wird, bei dem sein marginaler Umsatz p ∂f (x∗) ∂xi gleich seinem Beschaffungspreis qi ist. Das heißt, im Gewinnmaximum stimmen der marginale Umsatz und der Beschaffungspreis der n Produktionsfaktoren jeweils überein. Insbesondere folgt aus (24.8) ∂f (x∗) ∂xi = qi p . Demnach hängt das Verhalten eines gewinnmaximierenden Unternehmens nur von den Preisverhältnissen qi p und nicht von dem Niveau der Preise ab. Wird nun angenommen, dass die Hesse-Matrix Hf (x∗) negativ definit ist, dann ist dies eine hinreichende Bedingung dafür, dass x∗ eine lokale Maximalstelle der Gewinnfunktion G, also eine (lokal) optimale Faktormengenkombination ist. Mit Hilfe dieser hinreichenden Bedingung können Aussagen der komparativen Statik hergeleitet werden, welche die Reaktion eines Unternehmens auf Preisänderungen beim zu produzierenden Produkt A oder bei den n Produktionsfaktoren voraussagen. Zur Untersuchung des Verhaltens eines gewinnmaximierenden Unternehmens auf Preisänderungen beim zu produzierenden Produkt A wird die optimale Faktormengenkombination x∗ als Funktion des Absatzpreises p aufgefasst, d. h. x∗ = x∗(p), und beide Seiten der Gleichung (24.8) werden mit Hilfe der Produktregel (vgl. Satz 16.6c)) und der verallgemeinerten Kettenregel (vgl. Satz 22.24) nach 715 Kapitel 24 Nichtlineare Optimierung im Rn p abgeleitet. Man erhält dann 1 · ∂f (x ∗) ∂xi + p · d dp ( ∂f (x∗) ∂xi ) = ∂f (x ∗) ∂xi + p n∑ j=1 ( ∂2f (x∗) ∂xj ∂xi ) dx∗j (p) dp = 0 für i = 1, . . . , n bzw. in Vektorschreibweise grad f (x∗)+ p Hf (x∗) dx ∗(p) dp = 0, (24.10) wobei dx∗(p) dp := ( dx∗1 (p) dp , . . . , dx∗n(p) dp )T der Vektor mit den (infinitesimalen) Veränderungen der n Faktormengen bei (infinitesimaler) Änderung des Absatzpreises p ist. Durch Transposition der Gleichung (24.10) und anschließender Multiplikation mit dx ∗(p) dp von rechts resultiert weiter grad f (x∗)T dx∗(p) dp = −p ( dx∗(p) dp )T Hf (x∗) dx∗(p) dp >0. (24.11) Dabei folgt die Ungleichung auf der rechten Seite von (24.11) aus der unterstellten negativen Definitheit der Hesse-Matrix Hf (x∗). Mit (24.11) erhält man für das totale Differential der Produktionsfunktion f an der Maximalstelle x∗ die Darstellung df = n∑ i=1 ∂f (x∗) ∂xi dx∗i (p) = grad f (x∗)T dx∗(p) = −p ( dx∗(p) dp )T Hf (x∗) dx∗(p) dp dp > 0 für beliebiges dp > 0 (vgl. (22.20)). Eine Erhöhung des Absatzpreises p führt folglich zu einer Steigerung der Produktionsmenge y = f (x). Mit anderen Worten: Im Gewinnmaximum G(x∗) ist es ausgeschlossen, dass eine Preiserhöhung dp > 0 für das Produkt A zu einer Verringerung der Produktionsmenge führt. Durch Umformung von (24.10) erhält man für die Veränderung der Faktormengen dx∗(p) dp = − 1 p Hf (x∗)−1 grad f (x∗), wobei die Existenz der Inversen Hf (x∗)−1 aufgrund der unterstellten negativen Definitheit der Hesse-Matrix Hf (x∗) sichergestellt ist (vgl. Folgerung 10.35). Zusammen mit (24.9) folgt daraus weiter dx∗(p) dp = − 1 p2 Hf (x∗)−1 q. Auf ähnliche Weise lässt sich auch das Verhalten des gewinnmaximierenden Unternehmens bei Änderung einer der Beschaffungspreise qi der n Produktionsfaktoren, zum Beispiel q1, untersuchen. Dazu wird die optimale Faktormengenkombination x∗ nun als Funktion des Beschaffungspreises q1 aufgefasst, d. h. x∗ = x∗(q1), und anschließend werden beide Seiten der Gleichung p ∂f (x∗) ∂xi = qi (vgl. (24.8)) mit Hilfe der verallgemeinerten Kettenregel (vgl. Satz 22.24) nach dem Beschaffungspreis q1 abgeleitet. Man erhält dann p n∑ j=1 ( ∂2f (x∗) ∂xj ∂xi ) dx∗j (q1) dq1 = { 1 für i = 1 0 für i = 2, . . . , n bzw. in Matrixschreibweise p Hf (x∗) dx∗(q1) dq1 = e1, (24.12) wobei e1 = (1, 0, . . . , 0)T der erste Einheitsvektor ist. Durch Transposition dieser Gleichung und anschließende Multiplikation von rechts mit dem Vektor der (infinitesimalen) Veränderungen der n Faktormengen bei (infinitesimaler) Änderung des Beschaffungspreises q1, also mit dx∗(q1) dq1 := ( dx∗1 (q1) dq1 , . . . , dx∗n(q1) dq1 )T , erhält man p ( dx∗(q1) dq1 )T Hf (x∗) dx∗(q1) dq1 =eT1 dx∗(q1) dq1 = dx ∗ 1 (q1) dq1 <0. (24.13) Dabei folgt die Ungleichung auf der rechten Seite von (24.13) wieder aus der negativen Definitheit der Hesse- Matrix Hf (x∗). Eine Erhöhung des Beschaffungspreises q1 führt folglich zu einer Verringerung der Faktormenge x∗1 . Man kann jedoch nicht schließen, dass auch die 716 Kapitel 2424.2 Optimierung ohne Nebenbedingungen Produktionsmenge y = f (x) bei einer Erhöhung des Beschaffungspreises q1 fällt. Aus (24.12) folgt nämlich dx∗(q1) dq1 = 1 p Hf (x∗)−1e1 und für das totale Differential von f an der Stelle x∗ erhält man somit den Ausdruck df = n∑ i=1 ∂f (x∗) ∂xi dx∗i (q1) = grad f (x∗)T dx∗(q1) = 1 p grad f (x∗)T Hf (x∗)−1 e1 dq1, dessen Vorzeichen unbestimmt ist. Die Folgerung 22.14 in Abschnitt 22.2 besagt, dass die Hesse- Matrix Hf (x) einer zweimal stetig partiell differenzierbaren Funktion f :D⊆Rn −→R symmetrisch ist für alle x ∈D. Bei einer zweimal stetig partiell differenzierbaren Funktion f kann somit die für die Anwendung des Satzes 24.3a) und b) sowie der Folgerung 24.4 benötigte Definitheitseigenschaft der Hesse-Matrix Hf (x)mit Hilfe ihrer Hauptminoren (Hauptunterdeterminanten) untersucht werden (zum Begriff des Hauptminors siehe Definition 10.37). Bezeichnen nämlich det(H1), . . . , det(Hn) die n Hauptminoren von Hf (x), dann besagt das Sylvesterbzw. Hurwitz-Kriterium (vgl. Satz 10.38 in Abschnitt 10.7), dass die beiden Äquivalenzen a) Hf (x) positiv definit ⇐⇒ det(Hk) > 0 für alle k = 1, . . . , n und b) Hf (x) negativ definit ⇐⇒ (−1)k det(Hk) > 0 für alle k = 1, . . . , n sowie die Implikation c) weder det(Hk) ≥ 0, noch (−1)k det(Hk) ≥ 0 für alle k = 1, . . . , n ⇒ Hf (x) indefinit gelten. Die Anwendung des Sylvester-Kriteriums zur Untersuchung der Hesse-Matrix Hf (x) auf positive und negative Definitheit ist jedoch für große n oftmals nicht sehr praktikabel. Für kleine n, wie n = 2, 3, 4, ist das Sylvester-Kriterium aber oftmals gut handhabbar. Im folgenden Beispiel wird noch einmal die reellwertige Funktion aus Beispiel 24.7c) betrachtet. Zur Untersuchung der Definitheitseigenschaften der Hesse-Matrizen wird nun jedoch das Sylvester-Kriterium herangezogen. Beispiel 24.9 (Hinreichende Bedingung für Extrema) Betrachtet wird wieder die zweimal stetig partiell differenzierbare Funktion f : R3 −→ R, (x, y, z) %→ f (x, y, z) = 2 3 x3 − 3 2 y2 − 2z2 + yz − 8x + y + 7z− 3 aus Beispiel 24.7c). Dort wurde gezeigt, dass f die stationären Stellen x0 = (2, 1, 2)T und x1 = (−2, 1, 2)T besitzt und die Hesse-Matrizen an diesen beiden Stellen durch Hf (x0) = ⎛ ⎝ 8 0 0 0 −3 1 0 1 −4 ⎞ ⎠ und Hf (x1) = ⎛ ⎝ −8 0 0 0 −3 1 0 1 −4 ⎞ ⎠ gegeben sind. Für die Hauptminoren der ersten Hesse- Matrix Hf (x0) gilt: det(H1) = 8 det(H2) = 8 · (−3)− 0 · 0 = −24 det(H3) = 8 · (−3) · (−4)− 1 · 1 · 8 = 88 Die Hesse-Matrix Hf (x0) ist also indefinit und an der stationären Stelle x0 liegt ein Sattelpunkt. Für die Hauptminoren der zweiten Hesse-Matrix Hf (x1) gilt dagegen: det(H1) = −8 det(H2) = −8 · (−3)− 0 · 0 = 24 det(H3) = −8 · (−3) · (−4)− 1 · 1 · (−8) = −88 Das heißt, die Hesse-Matrix Hf (x1) ist negativ definit und bei der stationären Stelle x1 handelt es sich um eine lokale Maximalstelle. 717 Kapitel 24 Nichtlineare Optimierung im Rn Hinreichende Bedingung für den Spezialfall n = 2 Speziell für den wichtigen Fall einer zweimal stetig partiell differenzierbaren Funktion in nur zwei Variablen (d. h. n = 2) liefert das Sylvester-Kriterium einfach zu überprüfende hinreichende Bedingungen für lokale und globale Extrema, da in diesem Fall lediglich die beiden Hauptminoren det (H1) = ∂ 2f (x, y) ∂x2 und det (H2) = det ( Hf (x, y) ) untersucht werden müssen. Das heißt, es müssen lediglich die Vorzeichen der partiellen Ableitung ∂ 2f (x,y) ∂x2 und der Determinante det ( Hf (x, y) ) = ∂ 2f (x, y) ∂x2 · ∂ 2f (x, y) ∂y2 − ( ∂2f (x, y) ∂y∂x )2 bestimmt werden und es kann das folgende einfache Resultat angewendet werden. Folgerung 24.10 (Hinreichende Bedingung für Extrema im Fall n = 2) Es sei f : D ⊆ R2 −→ R eine zweimal stetig partiell differenzierbare Funktion auf einer offenen Menge D mit grad f (x0, y0) = (0, 0)T und der Hesse-Matrix Hf (x0, y0) = ⎛ ⎝ ∂2f (x0,y0) ∂x2 ∂2f (x0,y0) ∂y∂x ∂2f (x0,y0) ∂x∂y ∂2f (x0,y0) ∂y2 ⎞ ⎠ für ein (x0, y0) ∈ D. Dann gilt: a) ∂ 2f (x0,y0) ∂x2 > 0 und det ( Hf (x0, y0) ) > 0 ⇒ (x0, y0) ist eine lokale Minimalstelle von f b) ∂ 2f (x0,y0) ∂x2 < 0 und det ( Hf (x0, y0) ) > 0 ⇒ (x0, y0) ist eine lokale Maximalstelle von f c) ∂ 2f (x,y) ∂x2 > 0 und det ( Hf (x, y) ) > 0 für alle (x, y) ∈ D ⇒ (x0, y0) ist eine globale Minimalstelle von f d) ∂ 2f (x,y) ∂x2 < 0 und det ( Hf (x, y) ) > 0 für alle (x, y) ∈ D ⇒ (x0, y0) ist eine globale Maximalstelle von f e) det ( Hf (x0, y0) ) < 0 ⇒ (x0, y0) ist die Stelle eines Sattelpunkts von f Beweis: Zu a): Gemäß Satz 10.38a) ist Hf (x0, y0) positiv definit. Mit Satz 24.3a) folgt daher, dass (x0, y0) eine lokale Minimalstelle von f ist. Zu b): Folgt analog zur Aussage a) aus Satz 10.38b) und Satz 24.3b). Zu c): Folgt analog zur Aussage a) aus Satz 10.38a) und Folgerung 24.4a). Zu d): Folgt analog zur Aussage a) aus Satz 10.38b) und Folgerung 24.4b). Zu e): Folgt analog zur Aussage a) aus Satz 10.38e) und Satz 24.3c). Die Folgerung 24.10 stellt für eine zweimal stetig partiell differenzierbare Funktion f in zwei Variablen leicht zu überprüfende hinreichende Bedingungen für lokale und globale Extrema an einer stationären Stelle x0 bereit. Für lokale Extrema und Sattelpunkte sind diese Aussagen mit Hilfe eines Baumdiagramms in Abbildung 24.4 übersichtlich dargestellt. Gilt jedoch det ( Hf (x0, y0) ) = 0 oder ∂ 2f (x0, y0) ∂x2 = 0, dann liefert Folgerung 24.10 keine eindeutige Aussage. In einem solchen Fall müssen weitere Betrachtungen durchgeführt werden, wie z. B. die Untersuchung der Vorzeichen der Differenz f (x, y)−f (x0, y0) in einer Umgebung der stationären Stelle (x0, y0) (vgl. hierzu Beispiel 24.11b)). Beispiel 24.11 (Hinreichende Bedingung für Extrema) a) Betrachtet wird wieder die zweimal stetig partiell differenzierbare Funktion f : R2 −→ R, (x, y) %→ f (x, y) = 2x4 + y4 − 2x2 − 2y2 aus Beispiel 24.2b). Dort wurde gezeigt, dass f die folgenden neun stationären Stellen besitzt: (x1, y1) (x2, y2) (x3, y3) (x4, y4) (x5, y5) (0, 0) (0, 1) (0,−1) (√ 2 2 , 0 ) (√ 2 2 , 1 ) (x6, y6) (x7, y7) (x8, y8) (x9, y9) (√ 2 2 ,−1 ) ( − √ 2 2 , 0 ) ( − √ 2 2 , 1 ) ( − √ 2 2 ,−1 ) Aus den beiden ersten partiellen Ableitungen (24.3) erhält man die vier partiellen Ableitungen zweiter 718 Kapitel 2424.2 Optimierung ohne Nebenbedingungen det H f (x0, y0) = ∂ 2 f (x0,y0) ∂ x2 · ∂ 2 f (x0,y0) ∂ y2 − ∂ 2 f (x0,y0) ∂ x∂ y 2 det H f (x0, y0) > 0 det H f (x0, y0) < 0 det H f (x0, y0) = 0 lokales Minimum ∂ 2 f (x0 ,y0) ∂ x2 > 0 lokales Maximum ∂ 2 f (x0 ,y0) ∂ x2 < 0 Sattelpunkt Sattelpunkt oder lokales Extremum Abb. 24.4: Hinreichende Bedingung für die Extrema einer zweimal stetig partiell differenzierbaren Funktion f : D ⊆ R2 −→ R in zwei Variablen auf einer offenen Menge D an einer stationären Stelle x0 ∈ D Ordnung: ∂2f (x, y) ∂x2 =24x2 − 4, ∂ 2f (x, y) ∂y2 =12y2 − 4 und ∂2f (x, y) ∂x∂y = ∂ 2f (x, y) ∂y∂x = 0. Für die Hesse-Matrix von f an einer beliebigen Stelle (x, y) ∈ R2 gilt somit Hf (x, y) = ( 24x2 − 4 0 0 12y2 − 4 ) . Die Berechnung der Determinante der Hesse-Matrix Hf (x, y) und der zweiten partiellen Ableitung ∂2f (x,y) ∂x2 für die neun stationären Stellen führt zu der folgenden Tabelle: (x1,y1) (x2,y2) (x3,y3) (x4,y4) (x5,y5) det(Hf (xi,yi)) 16 −32 −32 −32 64 ∂2f (x,y) ∂x2 −4 −4 −4 8 8 (x6,y6) (x7,y7) (x8,y8) (x9,y9) det(Hf (xi,yi)) 64 −32 64 64 ∂2f (x,y) ∂x2 8 8 8 8 Bezeichnet pi := (xi,yi,f (xi,yi)) für i=1, 2, . . . , 9 wieder den zur stationären Stelle (xi, yi) gehörenden stationären Punkt auf dem Graphen von f , dann erhält man mit Folgerung 24.10, dass f an der Stelle p1 ein lokales Maximum, an den Stellen p5, p6, p8, p9 lokale Minima und an den Stellen p2, p3, p4, p7 Sattelpunkte besitzt. Das heißt, die in Beispiel 24.2b) mit Hilfe der Abbildung 24.1 gemachte Beobachtung bestätigt sich. b) Die reellwertige Funktion f : R2 −→R, (x, y) %→f (x, y) = 2x4 − 3x2y + y2 ist zweimal stetig partiell differenzierbar und besitzt den Gradienten grad (x, y) = (8x3 − 6xy,−3x2 + 2y)T . Es gilt somit grad (0, 0) = (0, 0)T und der Ursprung (0, 0) ist eine stationäre Stelle. Für die vier partiellen Ableitungen zweiter Ordnung von f gilt ∂2f (x, y) ∂x2 = 24x2 − 6y, ∂ 2f (x, y) ∂y2 = 2 und ∂2f (x, y) ∂x∂y = ∂ 2f (x, y) ∂y∂x = −6x. Die Hesse-Matrix an der stationären Stelle (0, 0) ist damit gegeben durch Hf (0, 0) = ( 0 0 0 2 ) . Das heißt, es gilt det ( Hf (0, 0) ) = 0 und Folgerung 24.10 ermöglicht keine Aussage bezüglich eines 719 Kapitel 24 Nichtlineare Optimierung im Rn Extremums an der stationären Stelle (0, 0). Aus f (0, y) = y2 und f (x, 0) = 2x4 ist ersichtlich, dass die beiden Schnittkurven, welche durch den Graphen von f und einer zur y-z-Ebene bzw. zur x-z-Ebene parallelen Ebene gebildet werden, im Ursprung (0, 0) jeweils ein lokales Minimum besitzen. Dennoch besitzt f in (0, 0) kein lokales Minimum, sondern einen Sattelpunkt. Aus der alternativen Darstellung f (x, y) = (y − 2x2)(y − x2) für die Funktionsvorschrift von f ist nämlich zu erkennen, dass f (x, y) { < 0 für (x, y) mit x2 < y < 2x2 > 0 für (x, y) mit y > 2x2 oder y < x2 gilt. Das heißt, in jeder Umgebung der stationären Stelle (0, 0) existieren Stellen (x, y) mit einem kleineren und Stellen (x, y) mit einem größeren Funktionswert als f (0, 0) = 0. Folglich besitzt f in (0, 0) kein lokales Minimum oder Maximum, sondern einen Sattelpunkt (vgl. Abbildung 24.5, links). c) Es werden zwei komplementäre, d. h. sich in ihrem Nutzen gegenseitig ergänzende, Güter G1 und G2 (z. B. Drucker und Druckerpatrone) mit den Preisen p1 und p2 betrachtet. Die Preisabsatzfunktionen N1 : (0, 10) −→ R und N2 : (0, 10) −→ R dieser beiden Güter seien gegeben durch N1(p1, p2) := 60 − 3p1 − 3 2 p2 und N2(p1, p2) := 40 − 3 2 p1 − 2p2. Der Umsatz mit diesen beiden Gütern beträgt somit U(p1, p2) = p1N1(p1, p2)+ p2N2(p1, p2) = −3p21 − 2p22 − 3p1p2 + 60p1 + 40p2 und für den Gradienten der Umsatzfunktion U erhält man gradU(p1, p2) = (−6p1 − 3p2 + 60,−4p2 − 3p1 + 40)T . Das heißt, (p1, p2) ∈ (0, 10)2 ist genau dann eine stationäre Stelle der Umsatzfunktion U , wenn sie eine Lösung des linearen Gleichungssystems −6p1 − 3p2 + 60 = 0 −3p1 − 4p2 + 40 = 0 ist. Durch einfache Umformungen erhält man, dass durch (8, 4) die einzige stationäre Stelle von U gegeben ist. Für die vier partiellen Ableitungen zweiter Ordnung von U erhält man ∂2U(p1, p2) ∂p21 = −6, ∂ 2U(p1, p2) ∂p22 = −4 und ∂2U(p1, p2) ∂p1∂p2 = ∂ 2U(p1, p2) ∂p2∂p1 = −3. Folglich lautet die Hesse-Matrix von U HU (p1, p2) = (−6 −3 −3 −4 ) für alle (p1, p2) ∈ (0, 10)2. Das heißt, für die beiden Hauptminoren der Hesse-Matrix HU (p1, p2) gilt det (HU (p1, p2)) = 15 > 0 und ∂2U(p1, p2) ∂p21 = −6 < 0 für alle (p1,p2)∈(0,10)2. Gemäß Folgerung 24.10d) ist damit die Stelle (8, 4) eine globale Maximalstelle von U , und der maximale Umsatz U(8, 4)=320 resultiert bei den Absatzmengen N1(8, 4)= 30 und N2(8, 4)=20 (vgl. Abbildung 24.5, rechts). Das folgende Beispiel zeigt eine Anwendung der nichtlinearen Optimierung ohne Nebenbedingungen in der Statistik. Beispiel 24.12 (Maximum-Likelihood-Methode) Die nach dem deutschen Mathematiker Carl Friedrich Gauß (1777–1855) benannte Gauß- Verteilung mit der Dichtefunktion f : R −→ R, x %→ f (x) = 1 σ √ 2π e − (x−μ)2 2σ2 wurde bereits in Beispiel 18.19 betrachtet. 720 Kapitel 2424.2 Optimierung ohne Nebenbedingungen x −1.0 −0.5 0.0 0.5 1.0 y −1.0 −0.5 0.0 0.5 1.0 0 1 2 3 4 5 6 f (x, y) = 2x4 − 3x2y + y2 l f (0, 0) x 0 2 4 6 8 10 y 0 2 4 6 8 10 0 100 200 300 U(p1, p2) = − 3p12 − 2p22 − 3p1p2 + 60p1 + 40p2 lU(8, 4) Abb. 24.5: Reellwertige Funktion f : R2 −→ R, (x, y) %→ f (x, y) = 2x4 − 3x2y + y2 (links) und die Umsatzfunktion U : (0, 10)2 −→ R, (p1, p2) %→ U(p1, p2) = −3p21 − 2p22 − 3p1p2 + 60p1 + 40p2 (rechts) Die Gauß-Verteilung wird in vielen Bereichen, wie zum Beispiel im quantitativen Risikomanagement sowie in der Finanz- und Versicherungswirtschaft zur Modellierung von Zufallsereignissen eingesetzt, da die Eintrittswahrscheinlichkeiten vieler als zufällig anzusehender Ereignisse oftmals in guter Näherung mit Hilfe der Gauß- Verteilung beschrieben werden können. Hierzu ist es in der Regel erforderlich, die beiden Parameter der Gauß- Verteilung, d. h. den Erwartungswert μ ∈ R und die Standardabweichung σ ∈ (0,∞), aus einer gegebenen Stichprobe (Daten) x1, . . . , xn zu schätzen. Die Standardabweichung σ ist dabei ein Maß für die Streuung der Beobachtungen um μ (vgl. Abbildung 24.6). R. A. Fisher Eines der populärsten Verfahren zur Schätzung der Parameter einer Wahrscheinlichkeitsverteilung ist die Maximum-Likelihood-Methode. Sie geht auf den bedeutenden britischen Statistiker und Evolutionstheoretiker Ronald Aylmer Fisher (1890–1962) zurück. Bei der Schätzung der beiden Parameter μ und σ mittels Maximum-Likelihood- Methode wird die sogenannte Likelihood-Funktion der Stichprobe x1, . . . , xn bezüglich den beiden zu schätzenden Parameternμ und σ maximiert. Unter Likelihood- Funktion der Gauß-Verteilung versteht man dabei die reellwertige Funktion l : R× (0,∞) −→ R mit l(μ,σ ) := n∏ i=1 f (xi) (24.14) = ( 1 σ √ 2π )n exp [ − n∑ i=1 (xi−μ)2 2σ 2 ] =(2πσ 2)− n2 exp [ − 1 2σ 2 n∑ i=1 (xi−μ)2 ] . Das heißt, bei der Maximierung von (24.14) werden die beiden Parameter μ und σ als Variablen und die Beobachtungen x1, . . . , xn als Konstanten, d. h. als gegeben, betrachtet. Da es jedoch häufig rechentechnisch praktikabler ist, wird anstelle von l(μ, σ ) der natürliche Logarithmus von l(μ, σ ), d. h. die sogenannte Log-Likelihood- Funktion ln (l(μ, σ ))=−n 2 ln(2π)−n ln(σ )− 1 2σ 2 n∑ i=1 (xi−μ)2, (24.15) bezüglichμ und σ maximiert. Aufgrund der strengen Monotonie der natürlichen Logarithmusfunktion ist sichergestellt, dass (24.14) und (24.15) dieselben Maximalstellen besitzen. Ferner gilt, dass (μ̂ML, σ̂ML) genau dann eine 721 Kapitel 24 Nichtlineare Optimierung im Rn Maximalstelle von (24.15) ist, wenn (μ̂ML, σ̂ML) eine Minimalstelle der zweimal stetig partiell differenzierbaren Funktion h : R× (0,∞) −→ R mit h(μ, σ ) := − ln (l(μ, σ )) = n 2 ln(2π)+ n ln(σ )+ 1 2σ 2 n∑ i=1 (xi − μ)2 ist. Für den Gradienten von h erhält man gradh(μ, σ ) = ( − 1 σ 2 n∑ i=1 (xi − μ), n σ − 1 σ 3 n∑ i=1 (xi − μ)2 )T , und die stationären Stellen von h – und damit insbesondere auch von der Likelihood-Funktion l – sind als Lösungen des Gleichungssystems − 1 σ 2 n∑ i=1 (xi − μ) = 0 n σ − 1 σ 3 n∑ i=1 (xi−μ)2 = 0 gegeben. Daraus erhält man durch elementare Umformungen, dass (μ̂ML, σ̂ML) mit μ̂ML := 1 n n∑ i=1 xi und σ̂ML := √√ √√ 1 n n∑ i=1 (xi − μ̂ML)2 die einzige stationäre Stelle von h und l ist. Die vier partiellen Ableitungen zweiter Ordnung der Funktion h an einer beliebigen Stelle (μ, σ ) ∈ R×(0,∞) sind gegeben durch: ∂2h(μ, σ ) ∂μ2 = n σ 2 ∂2h(μ, σ ) ∂μ∂σ = ∂ 2h(μ, σ ) ∂σ∂μ = 2 σ 3 n∑ i=1 (xi − μ) ∂2h(μ, σ ) ∂σ 2 = − n σ 2 + 3 σ 4 n∑ i=1 (xi − μ)2 Folglich gilt: ∂2h(μ̂ML, σ̂ML) ∂μ2 = n σ̂ 2ML ∂2h(μ̂ML, σ̂ML) ∂μ∂σ = ∂ 2h(μ̂ML, σ̂ML) ∂σ∂μ = 0 ∂2h(μ̂ML, σ̂ML) ∂σ 2 = 2n σ̂ 2ML Für die Hesse-Matrix von h an der stationären Stelle (μ̂ML, σ̂ML) impliziert dies Hh(μ̂ML, σ̂ML) = ⎛ ⎝ n σ̂ 2 ML 0 0 2n σ̂ 2 ML ⎞ ⎠ und für ihre beiden Hauptminoren gilt det (Hh(μ̂ML, σ̂ML)) > 0 und ∂2h(μ̂ML, σ̂ML) ∂μ2 > 0. Damit ist (μ̂ML, σ̂ML) gemäß Folgerung 24.10a) eine lokale Minimalstelle von h. Da es sich bei (μ̂ML, σ̂ML) um die einzige stationäre Stelle von h handelt und der Definitionsbereich von h eine offene Menge ist, erhält man, dass (μ̂ML, σ̂ML) sogar eine globale Minimalstelle von h ist. Folglich ist (μ̂ML, σ̂ML) eine globale Maximalstelle der Likelihood-Funktion (24.14), und die gesuchte Maximum-Likelihood-Schätzung für die beiden Parameter μ und σ der Gauß-Verteilung ist gegeben durch μ̂ML = 1 n n∑ i=1 xi und σ̂ML = √√√√ 1 n n∑ i=1 (xi − μ̂ML)2. Die in den Beispielen 24.7, 24.8, 24.11 und 24.12 betrachteten zweimal stetig partiell differenzierbaren Funktionen haben gemeinsam, dass sie jeweils auf einer offenen Menge definiert sind. Aus diesem Grund sind in diesen Beispielen durch die stationären Stellen auch bereits alle Kandidaten für lokale und globale Extremalstellen gegeben, was die Ermittlung aller Extrema beträchtlich erleichtert. Wenn jedoch der Definitionsbereich D der zu optimierenden Funktion f : D ⊆ Rn −→ R abgeschlossen ist, müssen die Randpunkte des Definitionsbereichs gesondert darauf untersucht werden, ob sie Extremalstellen der Funktion f sind oder nicht. Ist der Definitionsbereich D zusätzlich beschränkt, also insgesamt kompakt, dann besagt der Satz vom Minimum und Maximum (vgl. Satz 21.53) zwar, dass f eine globale Minimal- und Maximalstelle besitzt, er macht jedoch keine Aussage darüber, wo diese Stellen liegen. Das folgende Beispiel demonstriert anhand einer einfachen Funktion in zwei Variablen, wie in einem solchen Fall häufig vorgegangen werden kann. 722 Kapitel 2424.2 Optimierung ohne Nebenbedingungen −6 −5 −4 −3 −2 −1 0 1 2 3 4 5 6 0.2 0.4 0.6 f (x) = 1 σ 2π e −(x−μ)2 2σ2 Abb. 24.6: Dichte f : R −→ R, x %→ f (x) = 1 σ √ 2π e − (x−μ)2 2σ2 einer Gauß-Verteilung mit den Parametern μ = 0 und σ = 1 (schwarz), μ = −1 und σ = √ 2 2 (blau) und μ = 1 und σ = 2 (rot) Beispiel 24.13 (Extrema einer Funktion mit kompaktem Definitionsbereich) Die reellwertige Funktion f : [0, 1]2 −→ R, (x, y) %→ f (x, y) = 2x(1 − x)√ y + 1 mit dem abgeschlossenen und beschränkten (d. h. kompakten) Definitionsbereich D = [0, 1]2 besitzt die ersten partiellen Ableitungen ∂f (x, y) ∂x = 2 − 4x√ y + 1 und ∂f (x, y) ∂y = 2x(1 − x) ( −1 2 ) (y + 1)− 32 = −(x − x2)(y + 1)− 32 . Offensichtlich ist ∂f (x,y) ∂x = 0 genau dann erfüllt, wenn x = 12 gilt. Da jedoch ∂f (x,y)∂y = 0 für alle ( 1 2 , y ) mit y ∈ (0, 1) gilt, besitzt f im Inneren D◦ = (0, 1)2 von D keine stationären Stellen und damit in D◦ auch keine Extremalstellen. Es muss daher nur noch der Rand ∂D = {(x, y) : x ∈ {0, 1} oder y ∈ {0, 1}} des Definitionsbereichs D = [0, 1]2 auf Extremalstellen untersucht werden. Hierzu wird eine der Variablen x und y gleich 0 oder gleich 1 gesetzt. Man erhält dann die folgenden vier reellwertigen Funktionen in einer Variablen: x = 0 : f1(0, y) = 0 für alle y ∈ [0, 1] x = 1 : f2(1, y) = 0 für alle y ∈ [0, 1] y = 0 : f3(x, 0) = 2x(1 − x) für alle x ∈ [0, 1] y = 1 : f4(x, 1) = √ 2x(1 − x) für alle x ∈ [0, 1] Für die beiden Funktionen f3(x, 0) und f4(x, 1) in der Variablen x erhält man die folgenden beiden ersten und zweiten Ableitungen: f ′3(x, 0) = 2 − 4x und f ′′3 (x, 0) = −4 bzw. f ′4(x, 1) = √ 2(1 − 2x) und f ′′4 (x, 1) = − √ 22. Die beiden Funktionen f3(x, 0) und f4(x, 1) besitzen somit jeweils bei x1 = 12 eine stationäre Stelle, die wegen f ′′3 (x, 0) < 0 und f ′′ 4 (x, 1) < 0 auch jeweils eine globale Maximalstelle ist (vgl. Folgerung 18.8). Das zugehörige globale Maximum von f3 und f4 beträgt f ( 1 2 , 0 ) = 12 bzw. f ( 1 2 , 1 ) = 1 2 √ 2 . Da ferner 2x(1 − x)√ y + 1 ≥ 0 für alle (x, y) ∈ [0, 1]2 gilt, erhält man für f insgesamt das folgende Ergebnis: Die Funktion f besitzt globale Minimalstellen mit dem Funktionswert 0 bei (0, y) und (1, y) für alle y ∈ [0, 1] und eine globale Maximalstelle mit dem Funktionswert 12 bei ( 1 2 , 0 ) (vgl. Abbildung 24.7). 723 Kapitel 24 Nichtlineare Optimierung im Rn x 0.0 0.2 0.4 0.6 0.8 1.0 y 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.1 0.2 0.3 0.4 f (x, y) = 2x(1−x) y+1 Abb. 24.7: Reellwertige Funktion f : [0, 1]2 −→ R, (x, y) %→ f (x, y) = 2x(1−x)√ y+1 mit den globalen Minimalstellen (0, y) und (1, y) für y ∈ [0, 1] und der globalen Maximalstelle ( 1 2 , 0 ) 24.3 Optimierung unter Gleichheitsnebenbedingungen Minimum und Maximum unter Gleichheitsnebenbedingungen Im letzten Abschnitt wurde gezeigt, wie mit Hilfe der Differentialrechnung die lokalen und globalen Extremalstellen einer stetig partiell differenzierbaren Funktion f : D ⊆ R n −→ R in n Variablen bestimmt werden können, wenn der Definitionsbereich D nicht durch zusätzliche Bedingungen, welche die Werte der n Variablen x = (x1, . . . , xn)T erfüllen müssen, eingeschränkt ist. Das heißt, bei der Bestimmung der Extremalstellen von f wurden keine sogenannten Nebenbedingungen berücksichtigt und es wurden somit Minimierungs- und Maximierungsprobleme der „einfachen“ Form min x∈D f (x) bzw. max x∈D f (x) betrachtet. Bei zahlreichen wirtschaftswissenschaftlichen Problemstellungen müssen aber bei der Optimierung auch Nebenbedingungen berücksichtigt werden. Zum Beispiel maximiert ein Haushalt seinen Nutzen unter Berücksichtigung seiner Budgetrestriktion, eine Unternehmung minimiert die Produktionskosten unter Vorgabe eines zu erzielenden Outputs und ein Betrieb maximiert seine Produktionsmenge unter Einhaltung einer Reihe von Kapazitätsbeschränkungen. Das heißt, bei vielen ökonomischen Optimierungsproblemen sind eine oder mehrere Nebenbedingungen der Form h(x1, . . . , xn) = c (24.16) mit einer reellwertigen Funktion h : D ⊆ Rn −→ R und einer Konstanten c ∈ R zu berücksichtigen. Da die Nebenbedingung (24.16) jedoch durch Subtraktion der Konstanten c auf beiden Seiten der Gleichung stets auf die Form h(x1, . . . , xn)− c = 0 gebracht werden kann, beschränkt sich die folgende Darstellung ohne Beschränkung der Allgemeinheit auf Gleichheitsnebenbedingungen der speziellen Form g1(x1, . . . , xn) = 0 g2(x1, . . . , xn) = 0 ... gk(x1, . . . , xn) = 0, (24.17) also mit dem Wert Null auf der rechten Seite. Um die Ergebnisse aus der Differentialrechnung für reellwertige Funktionen in n Variablen anwenden zu können, wird angenommen, dass die k Funktionen g1, g2, . . . , gk : D ⊆ Rn −→ R wie auch die zu optimierende Funktion f : D ⊆ Rn −→ R stetig 724 Kapitel 2424.3 Optimierung unter Gleichheitsnebenbedingungen partiell differenzierbar sind. Darüber hinaus wird vorausgesetzt, dass die Anzahl k der Nebenbedingungen (24.17) kleiner als die Anzahl n der Variablen x1, . . . , xn ist, also k < n gilt. Auf diese Weise wird sichergestellt, dass zur Optimierung von f noch Freiheitsgrade, also Variablen die unabhängig voneinander variiert werden können, vorhanden sind. Der allgemeine Fall, bei dem auch Nebenbedingungen in Form von Ungleichungen gi(x1, . . . , xn) ≤ 0 zugelassen sind, ist deutlich komplizierter zu behandeln und Gegenstand von Abschnitt 24.5 und Kapitel 25. In diesem Abschnitt wird somit die Problemstellung untersucht, dass eine stetig partiell differenzierbare Funktion f : D ⊆ Rn −→ R unter Beachtung von k < n Gleichheitsnebenbedingungen (24.17) mit stetig partiell differenzierbaren Funktionen g1, g2, . . . , gk : D ⊆ Rn −→ R zu optimieren ist. Bezeichnet N := {x ∈ D : g1(x) = 0, . . . , gk(x) = 0} ⊆ D (24.18) die Menge aller x ∈ D, welche die k Nebenbedingungen (24.17) erfüllen, dann sagt man, dass x0 ∈N eine lokale Minimal- bzw. Maximalstelle von f unter den Nebenbedingungen (24.17) ist, wenn es eine Umgebung U ⊆ D von x0 gibt, so dass f (x0) ≤ f (x) bzw. f (x0) ≥ f (x) für alle x ∈ U ∩N gilt. Es werden somit Minimierungs- und Maximierungsprobleme der „komplizierteren“ Form min x∈D g1(x)=0,...,gk (x)=0 f (x) = min x∈N f (x) bzw. max x∈D g1(x)=0,...,gk (x)=0 f (x) = max x∈N f (x) betrachtet, und gesucht sind alle lokalen und globalen Extremalstellen und Extremalwerte von f unter den k angegebenen Nebenbedingungen. Dies sind gerade die Extremalstellen und Extremalwerte der Restriktion fN : N −→ R, x %→ fN(x) := f (x) (24.19) der Funktion f auf die Menge (24.18). Im Allgemeinen ist das Minimum (Maximum) von f unter Einbeziehung von Nebenbedingungen nicht kleiner (größer) als dasjenige von f ohne Berücksichtigung von Nebenbedingungen. Es gelten also stets die Beziehungen min x∈D g1(x)=0,...,gk (x)=0 f (x) ≥ min x∈D f (x) und max x∈D g1(x)=0,...,gk (x)=0 f (x) ≤ max x∈D f (x). In Abbildung 24.8 ist der Unterschied bei der Maximierung einer reellwertigen Funktion f : D ⊆ R2 −→ R, (x, y) %→ f (x, y) in zwei Variablen ohne und mit Nebenbedingung g(x, y) = 0 dargestellt. Es ist zu erkennen, dass das Maximum von f ohne Berücksichtigung einer Nebenbedingung im Scheitelpunkt der Kuppel liegt, während das Maximum unter der Nebenbedingung g(x, y) = 0 der Scheitelpunkt der Schnittkurve ist, die durch den Graphen von f und die Nebenbedingung g(x, y) = 0 festgelegt wird. Abb.24.8:UnterschiedbeiderMaximierungeiner reellwertigen Funktion f : D ⊆ R2 −→ R, (x, y) %→ f (x, y) ohne Nebenbedingung und mit Nebenbedingung g(x, y) = 0 Verfahren der Variablensubstitution Die Optimierung einer reellwertigen Funktion f : D ⊆ R n −→ R unter k < n Gleichheitsnebenbedingungen der Form (24.17) ist relativ einfach möglich, wenn die Gleichungen explizit nach k verschiedenen Variablen, etwa nach x1, . . . , xk , aufgelöst werden können. Man erhält dann für die k Variablen eine Darstellung der Form x1 = h1(xk+1, . . . , xn) x2 = h2(xk+1, . . . , xn) ... (24.20) xk = hk(xk+1, . . . , xn) mit bekannten reellwertigen Funktionen h1, h2, . . . , hk . Die auf diese Weise gewonnenen Ausdrücke (24.20) können an- 725 Kapitel 24 Nichtlineare Optimierung im Rn x 0 20 40 60 80 100 y 0 20 40 60 80 100 10000 20000 30000 K(x, y) = 34x 2 + 114 y 2 + 10y + 700 g(x, y) = 0 l (80 , 20 , 6800 ) ϕ(y) = 72y 2 − 140 y + 8200 0 20 40 60 80 100 0 5000 6800 10000 15000 20000 25000 30000 l Abb. 24.9: Gesamtkostenfunktion K : (0,∞)2 −→ R, (x, y) %→ K(x, y) = 34 x2 + 114 y2 + 10y + 700 (links) und Gesamtkostenfunktion ϕ(y) = K(100 − y, y) = 72 y2 − 140y + 8200 nach Variablensubstitution mit globaler Minimalstelle bei y0 = 20 (rechts) schließend für die Variablen x1, . . . , xk in die zu optimierende Funktion f eingesetzt werden und es resultiert dann mit ϕ(xk+1, . . . , xn) :=f (h1(xk+1, . . . , xn), . . . , hk(xk+1, . . . , xn), xk+1, . . . , xn) eine neue reellwertige Funktion in den verbleibenden n− k Variablen xk+1, . . . , xn. Durch die Funktion ϕ werden also die k Nebenbedingungen (24.17) implizit berücksichtigt und es resultiert ein Optimierungsproblem ohne Nebenbedingungen mit einer reduzierten Variablenanzahl. Die Extremalstellen von ϕ können daher mit Hilfe der Differentialrechnung und den Ergebnissen aus Abschnitt 24.2 in herkömmlicher Weise bestimmt werden, wenn die Funktion ϕ die dazu erforderlichen Differenzierbarkeitsbedingungen erfüllt. Dieses Vorgehen heißt Verfahren der Variablensubstitution oder auch Methode der direkten Elimination und wird im nächsten Beispiel demonstriert. Beispiel 24.14 (Verfahren der Variablensubstitution) a) Ein Textilfabrikant bezieht für seine T-Shirt Produktion Baumwolle von zwei verschiedenen Herstellern H1 und H2. Die Bezugskosten für Baumwolle von diesen beiden Herstellern in Abhängigkeit der Bezugsmengen x und y (in Tonnen) sind durch die beiden Kostenfunktionen k1, k2 : (0,∞) −→ R mit k1(x) := 3 4 x2+400 bzw. k2(y) := 11 4 y2+10y+300 gegeben. Der Textilfabrikant verfolgt als Unternehmensziel die kostenminimale Produktion einer gewissen Anzahl von T-Shirts, für die er insgesamt 100 Tonnen Baumwolle benötigt. Das heißt, für die Gesamtbezugsmenge x + y an Baumwolle von den beiden Herstellern muss die Bedingung x+y = 100 erfüllt sein und folglich ist die Gesamtkostenfunktion K : (0,∞)2 −→ R, (x, y) %→ K(x, y) := k1(x)+ k2(y) = 3 4 x2 + 11 4 y2 + 10y + 700 726 Kapitel 2424.3 Optimierung unter Gleichheitsnebenbedingungen unter Berücksichtigung der Nebenbedingung g(x, y) = x + y − 100 = 0 (24.21) zu minimieren. Da es jedoch möglich ist, die Nebenbedingung (24.21) explizit nach einer der beiden Variablen x oder y aufzulösen und anschließend den resultierenden Ausdruck in die zu minimierende Gesamtkostenfunktion K einzusetzen, kann die Problemstellung auf ein äquivalentes Optimierungsproblem in einer Variablen ohne Nebenbedingung zurückgeführt werden. Wird zum Beispiel (24.21) nach der Variablen x aufgelöst, dann resultiert die Gleichung x = 100 − y und nach Einsetzen in K erhält man mit ϕ(y) := K(100 − y, y) = 3 4 (100 − y)2 + 11 4 y2 + 10y + 700 = 7 2 y2 − 140y + 8200 eine reellwertige Funktion in einer Variablen. Für die ersten beiden Ableitungen von ϕ gilt ϕ′(y) = 7y − 140 bzw. ϕ′′(y) = 7 > 0 und es folgt ϕ′(20) = 0 bzw. ϕ′′(20) > 0. Das heißt, gemäß Satz 18.8b) ist der Wert y0 = 20 eine globale Minimalstelle von ϕ, und mit der Nebenbedingung (24.21) erhält man für die andere Variable den Wert x0 = 80. Die kostenminimalen Bezugsmengen sind folglich x0 = 80 und y0 = 20 und führen zu den (minimalen) Gesamtkosten K(80, 20)= 3 4 802 + 11 4 202 + 10 · 20 + 700=6800 (vgl. Abbildung 24.9). b) Betrachtet werden die durch die Gleichung z = x+y festgelegte Ebene E im dreidimensionalen euklidischen RaumR3 und der Punkt p := (0, 0, 10)T ∈ R3. Zu bestimmen sei der Punkt x0 := (x0, y0, z0)T in der Ebene E, der den euklidischen Abstand zum Punkt p, also den Wert ‖x − p‖ = √ x2 + y2 + (z− 10)2, minimiert (zum Begriff des euklidischen Abstands siehe Definition 7.10). Diese Problemstellung ist äquivalent zur Bestimmung der (globalen) Minimalstelle der Funktion f : R3 −→ R, (x, y, z) %→ f (x, y, z) := x2 + y2 + (z− 10)2 unter der Nebenbedingung g(x, y, z) = x + y − z = 0. (24.22) Durch die Nebenbedingung (24.22) wird sichergestellt, dass die resultierende Lösung auch tatsächlich in der Ebene E liegt. Da die Nebenbedingung jedoch wieder explizit nach einer der drei Variablen x, y oder z aufgelöst werden kann, lässt sich die Problemstellung zu einem äquivalenten Optimierungsproblem in zwei Variablen ohne Nebenbedingung vereinfachen. Zum Beispiel erhält man durch Einsetzen des Ausdrucks z = x + y in die zu minimierende Funktion f mit ϕ(x, y) := f (x, y, x + y) = x2 + y2 + (x + y − 10)2 = 2x2 + 2y2 + 2xy − 20x − 20y + 100 eine reellwertige Funktion in zwei Variablen. Diese Funktion kann ohne Berücksichtigung von Nebenbedingungen minimiert werden. Die partiellen Ableitungen ∂ϕ(x, y) ∂x = 4x + 2y − 20 und ∂ϕ(x, y) ∂y = 4y + 2x − 20 führen zum linearen Gleichungssystem 4x + 2y − 20 = 0 4y + 2x − 20 = 0, dessen eindeutige Lösung ( 10 3 , 10 3 ) die einzige stationäre Stelle von ϕ ist. Durch Einsetzen dieser Werte in die Nebenbedingung (24.22) erhält man für die dritte Variable den Wert z = 203 und aus dem Sachzusammenhang oder der Definitheitseigenschaft der Hesse- Matrix Hϕ(x, y) = ( 4 2 2 4 ) 727 Kapitel 24 Nichtlineare Optimierung im Rn x −6 −4 −2 0 2 4 6 y −6 −4 −2 0 2 4 6 −10 −5 0 5 10 z = x + y l l x0 p x −6 −4 −2 0 2 4 6 y −6 −4 −2 0 2 4 6 100 200 300 400 500 ϕ(x, y) = x2 + y2 + (x + y − 10)2 l (10 3, 10 3, 10 3 ) Abb. 24.10: Die durch die Gleichung z = x + y im R3 festgelegte Ebene E mit dem Punkt x0 = ( 10 3 , 10 3 , 20 3 )T ∈ E, der den Abstand zu p = (0, 0, 10)T minimiert (links) und die zu minimierende Funktion ϕ(x, y) = f (x, y, x + y) = x2 + y2 + (x + y − 10)2 mit ihrem globalen Minimum ( 103 , 10 3 , 100 3 ) (rechts) folgt, dass es sich bei der stationären Stelle ( 10 3 , 10 3 ) tatsächlich um eine globale Minimalstelle von ϕ handelt. Zum Beispiel gilt für die beiden Hauptminoren der Hesse-Matrix det (H1) = ∂ 2ϕ(x, y) ∂x2 = 4 > 0 und det (H2) = det ( Hϕ(x, y) ) = 12 > 0. Gemäß Folgerung 24.10c) ist somit ( 10 3 , 10 3 ) die globale Minimalstelle von ϕ und ( 10 3 , 10 3 , 20 3 ) die globale Minimalstelle von f unter der Nebenbedingung (24.22). Das heißt, der Punkt x0 = ( 10 3 , 10 3 , 20 3 )T ist der gesuchte Punkt auf der Ebene E, der den Abstand zum Punkt p minimiert. Der minimale Abstand beträgt √ f (x0) = √ 100 3 = 103 √ 3 (vgl. Abbildung 24.10). Lagrangesche Multiplikatorenregel In vielen Fällen ist es nicht möglich, bei der Optimierung einer reellwertigen Funktion f : D ⊆ Rn −→ R mit k Nebenbedingungen der Form (24.17) alle Nebenbedingungen explizit nach k verschiedenen Variablen aufzulösen. In solchen Fällen kann das Verfahren der Variablensubstitution nicht zur Berechnung der Extremalstellen von f unter den Nebenbedingungen (24.17) herangezogen werden. Das heißt, es wird eine andere Methode benötigt, mit welcher das Problem auf ein Optimierungsproblem ohne Nebenbedingungen zurückgeführt werden kann. J.-L. de Lagrange Eine solche Methode ist die Lagrangesche Multiplikatorenregel, die im Jahre 1797 von dem italienischen Mathematiker und Astronom Joseph-Louis de Lagrange (1736–1813) in seiner wissenschaftlichen Abhandlung „Théorie des fonctions analytiques“ veröffentlicht wurde. Bei diesem Lösungsansatz wird ein gegebenes Optimierungsproblem in n Variablen mit k < n Nebenbedingungen in ein höherdimensionales Optimierungsproblem mit n + k Variablen ohne Nebenbedingungen überführt. Im Folgenden wird die Lagrangesche Multiplikatorenregel anhand des einfachsten Falles, nämlich der Maximierung einer reellwertigen Funktion f : D ⊆ R2 −→ R, (x, y) %→ f (x, y) 728 Kapitel 2424.3 Optimierung unter Gleichheitsnebenbedingungen auf einer offenen Menge D in nur zwei Variablen und lediglich einer Nebenbedingung g(x, y) = 0 (24.23) erläutert. Die hierbei gewonnenen Erkenntnisse sind hilfreich für das Verständnis der Lagrangeschen Multiplikatorenregel für den allgemeinen Fall, also für die Optimierung einer reellwertigen Funktion in n Variablen unter k 0 und det ( HL ( −1, √ 6 2 , 1 2 )) =det ( HL ( −1,− √ 6 2 , 1 2 )) = −12 < 0. Mit Satz 24.18a) und b) folgt somit, dass es sich bei (0, 2) um eine lokale Maximalstelle und bei(√ 6 2 , 1 2 ) sowie ( − √ 6 2 , 1 2 ) um lokale Minimalstellen von f unter der Nebenbedingung (24.39) handelt. Die zugehörigen Optimalwerte sind gegeben durch f (0,2)=7 bzw. f (√ 6 2 , 1 2 ) =f ( − √ 6 2 , 1 2 ) = 194 . Aus L (−1, x, y) = y2 − y + 5 folgt ferner HL(−1, x, y) = ( 0 0 0 2 ) . Das heißt, die Hesse-Matrix von L(−1, x, y) ist für alle (x, y) ∈ R2 eine Diagonalmatrix mit nichtnegativen Hauptdiagonaleinträgen. Sie ist also positiv semidefinit (vgl. Satz 10.32) und mit Satz 22.45a) folgt daher, dass L (−1, x, y) als Funktion von (x, y) konvex ist. Zusammen mit Satz 24.17a) impliziert dies, dass (√ 6 2 , 1 2 ) und ( − √ 6 2 , 1 2 ) sogar globale Minimalstellen von f unter der Nebenbedingung (24.39) sind (vgl. Abbildung 24.13). x −2 −1 0 1 2 y −2 −1 0 1 2 5 10 15 f(x, y) = x2 + y2 + 3 g(x, y) = 0 l l l (x2, y2) (x3, y3) (x1, y1) f(x, y) = x2 + y2 + 3 4 4.75 6 7 8 l (x1, y1) l (x2, y2)l(x3, y3) g(x, y) = 0 Abb. 24.13: Reellwertige Funktion f : R2 −→ R, (x, y) %→ f (x, y) = x2 + y2 + 3 mit Nebenbedingung g(x, y) = x2 + y − 2 = 0 (links) und Isohöhenlinen If (c) der Funktion f zu verschiedenen Niveaus mit Nebenbedingung g(x, y) = 0 (rechts) Gegenstand des folgenden Beispiels ist die Anwendung der Lagrangeschen Multiplikatorenregel bei der Bestimmung eines risikominimalen Portfolios von Wertpapieren. Beispiel 24.20 (Bestimmung des risikominimalen Portfolios) Betrachtet wird ein Anleger, der vor der Frage steht, wie groß er die Anteile x, y und z von drei zur Auswahl stehenden Wertpapieren bei der Bildung seines Portfolios wählen soll, so dass die erwartete Gesamtrendite r beträgt und das mit dem Portfolio verbundene Investitionsrisiko minimiert wird. Dabei sei angenommen, dass die erwarteten Renditen der drei Wertpapiere 15 , 1 10 bzw. 3 10 betragen und das Risiko des Portfolios durch die reellwertige Funktion f : (0,∞)3 −→ R, (x, y, z) %→ f (x, y, z) = 1 20 x2 + 1 20 y2 + 1 20 z2 quantifiziert wird. Der Anleger ist folglich an der globalen Minimalstelle der Funktion f interessiert, wobei er jedoch die beiden Nebenbedingungen g1(x, y, z) = 1 5 x + 1 10 y + 3 10 z− r = 0 und g2(x, y, z) = x + y + z− 1 = 0 (24.40) 737 Kapitel 24 Nichtlineare Optimierung im Rn mit r ∈ (0, 1) zu berücksichtigen hat. Die Lagrange- Funktion lautet somit: L(λ1, λ2, x, y, z) = 1 20 x2 + 1 20 y2 + 1 20 z2 + λ1 ( 1 5 x + 1 10 y + 3 10 z− r ) + λ2(x + y + z− 1). Durch Berechnung und Nullsetzen der ersten partiellen Ableitungen vonL erhält man das folgende Lagrangesche Gleichungssystem: ∂L(λ1, λ2, x, y, z) ∂x = 1 10 x + 1 5 λ1 + λ2 = 0 ∂L(λ1, λ2, x, y, z) ∂y = 1 10 y + 1 10 λ1 + λ2 = 0 ∂L(λ1, λ2, x, y, z) ∂z = 1 10 z+ 3 10 λ1 + λ2 = 0 ∂L(λ1, λ2, x, y, z) ∂λ1 = 1 5 x + 1 10 y + 3 10 z− r = 0 ∂L(λ1, λ2, x, y, z) ∂λ2 = x + y + z− 1 = 0 (24.41) Durch Einsetzen der ersten drei Gleichungen in die vierte und fünfte Gleichung folgt −14λ1 − 60λ2 = 10r und −6λ1 − 30λ2 = 1, woraus nach kurzer Umformung die Werte λ1 = 1 − 5r und λ2 = r − 7 30 resultieren. Einsetzen von λ1 und λ2 in die ersten drei Gleichungen von (24.41) liefert die Anteile x = 1 3 , y = 4 3 − 5r und z = 5r − 2 3 . Für die Jacobi-Matrix gilt Jg(x, y, z) = ( ∂g1(x,y,z) ∂x ∂g1(x,y,z) ∂y ∂g1(x,y,z) ∂z ∂g2(x,y,z) ∂x ∂g2(x,y,z) ∂y ∂g2(x,y,z) ∂z ) = ( 1 5 1 10 3 10 1 1 1 ) . Da die beiden Zeilen von Jg(x, y, z) offensichtlich linear unabhängig sind, besitzt die Jacobi-Matrix Jg(x, y, z) den vollen Rang k = 2. Folglich ist durch ( 1 3 , 4 3 − 5r, 5r − 2 3 ) (24.42) der einzige Kandidat für das gesuchte risikominimale Portfolio unter den beiden Nebenbedingungen (24.40) in Abhängigkeit von der erwarteten Gesamtrendite r gegeben. Wird L∗(x, y, z) := L (1 − 5r, r − 730 , x, y, z ) als Funktion der drei Variablen x, y und z betrachtet, dann gilt für die Hesse-Matrix HL∗(x, y, z) = ⎛ ⎝ 1 10 0 0 0 110 0 0 0 110 ⎞ ⎠ . Als Diagonalmatrix mit ausschließlich positiven Hauptdiagonaleinträgen ist HL∗(x, y, z) für alle (x, y, z) ∈ R3 positiv definit (vgl. Satz 10.32) und damit die Funktion L∗(x, y, z) gemäß Satz 22.45c) für alle (x, y, z) ∈ R3 streng konvex. Aus Satz 24.17 folgt somit, dass es sich bei (24.42) um die eindeutig bestimmte globale Minimalstelle von f unter den beiden Nebenbedingungen (24.40) handelt. Das heißt, (24.42) ist das gesuchte risikominimale Portfolio und der Wert R(r) :=f ( 13 , 43 − 5r, 5r − 23 )= 52 r2 − r + 760 das zugehörige globale Minimum der Risikofunktion f in Abhängigkeit von der erwarteten Gesamtrendite r (vgl. Abbildung 24.14). Die Bestimmung eines risikominimalen Portfolios unter Vorgabe einer zu erreichenden (erwarteten) Gesamtrendite wird in der Portfoliotheorie nach dem US-amerikanischen Ökonomen und Wirtschaftsnobelpreisträger Harry Markowitz (*1927) als Markowitz- Problem bezeichnet. Neben ihrem Nutzen bei der Optimierung einer partiell differenzierbaren Funktion f :D ⊆ Rn −→ R unter k < n Nebenbedingungen gp(x) = 0 für p = 1, . . . , k besitzen die Lagrange-Multiplikatoren λ1, . . . , λk darüber hinaus auch noch eine interessante ökonomische Interpretation. Wie die folgende Ausführung zeigt, können sie als die wertmäßige Reaktion der Funktion f bei einer Änderung der Nebenbedingungen aufgefasst werden. Zur Erläuterung dieser Interpretationsmöglichkeit sei angenommen, dass die k Gleichheitsnebenbedingungen des Optimierungsproblems in der Form g1(x) = h1(x)− c1 = 0 g2(x) = h2(x)− c2 = 0 ... gk(x) = hk(x)− ck = 0 (24.43) 738 Kapitel 2424.3 Optimierung unter Gleichheitsnebenbedingungen 0 0.1 0.2 0.3 0.4 0.5 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 R(r) = 5 2 r2 − r + 7 60 Abb. 24.14: Risiko R(r) = 52 r2 − r + 760 des risikominimalen Portfolios in Abhängigkeit von der erwarteten Gesamtrendite r mit c1, . . . , ck ∈ R und partiell differenzierbaren Funktionen h1, h2, . . . , hk : D ⊆ Rn −→ R geschrieben werden können. Dies ist zum Beispiel der Fall, wenn durch die Nebenbedingungen gp(x) = 0, also durch die Gleichungen hp(x) = cp , Produktionskapazitäten, Budgetrestriktionen oder erwartete Gesamtrenditen zum Ausdruck gebracht werden sollen. Der Parameter cp gibt dann die Höhe der p-ten Produktionskapazität, Budgetrestriktion bzw. erwarteten Gesamtrendite an. Werden nun die Parameter c1, . . . , ck als variabel betrachtet, dann besitzt die Lagrange-Funktion die (erweiterte) Form L(λ1, . . . , λk, x, c1, . . . , ck) = f (x)+ k∑ p=1 λp ( hp(x)− cp ) , (24.44) und partielles Differenzieren von L nach c1, . . . , ck liefert die ersten partiellen Ableitungen L(λ1, . . . , λk, x, c1, . . . , ck) ∂cp = −λp (24.45) für p = 1, . . . , k. Ferner gilt für ein x ∈ D, welches den Nebenbedingungen (24.43) genügt, L(λ1, . . . , λk, x, c1, . . . , ck) = f (x) (24.46) (vgl. (24.44)). Aus (24.45)-(24.46) folgt somit, dass der mit −1 multiplizierte Lagrange-Multiplikator λi die Änderung des Funktionswertes f (x) an der Optimalstelle bei einer Ver- änderung von cp angibt. Der Wert −λp ist folglich ein Maß für die Sensitivität des Funktionswertes f (x) bezüglich einer Veränderung der p-ten Beschränkung cp und wird deshalb auch als Schattenpreis bezeichnet, der einer Einheit der pten Ressource zugeschrieben wird. Beispiel 24.21 (Ökonomische Interpretation von Lagrange-Multiplikatoren) In Beispiel 24.19b) resultierte als (globale) Minimalstelle der Gesamtkostenfunktion eines Textilfabrikanten K(x,y)= 3 4 x2+ 11 4 y2+10y+700 unter der Nebenbedingung g(x, y) = x + y − 100 = 0 bzw. h(x, y) = x + y = 100 die Stelle (80, 20) und für den zugehörigen Lagrange- Multiplikator der Wert λ = −120. Für die erste partielle 739 Kapitel 24 Nichtlineare Optimierung im Rn Ableitung der (erweiterten) Lagrange-Funktion bezüglich c gilt somit L(λ, x, y, c) ∂c = −λ = 120. Dieser Wert ist der Schattenpreis einer Einheit der Ressource „Baumwolle“ und gibt an, wie sich die minimalen Gesamtkosten K(80, 20) = 6800 bei einer Veränderung der Restriktion c = 100 verhalten. Zum Beispiel führt eine Erhöhung von c = 100 um eine Mengeneinheit auf c = 101 dazu, dass die minimalen Gesamtkosten ungefähr um −λ = 120 Geldeinheiten steigen. 24.4 Wertfunktionen und Einhüllendensatz Maximalwert- und Minimalwertfunktion In vielen ökonomischen Optimierungsproblemen ist die Funktion f : D ⊆ Rn −→ R nicht nur von Variablen x1, . . . , xn abhängig, über die es zu minimieren oder zu maximieren gilt, sondern auch von einer oder mehreren exogenen Variablen (Parametern) α1, . . . , αm, wie zum Beispiel Preise, Löhne, Absatzmengen oder Zinssatz. In solchen Situationen stellt sich dann oftmals die Frage, wie sich die Veränderung eines Parameters αi auf den optimalen Wert der Funktion f auswirkt. Wichtige Beispiele für solche Situationen sind die folgenden ökonomischen Fragestellungen: a) Wie ändert sich der maximale Nutzen eines Konsumenten, wenn sich der Preis eines Gutes oder das Einkommen verändert? b) Welchen Einfluss haben Preisänderungen bei Rohstoffen auf die minimalen Produktionskosten eines Herstellers? c) Wie verändert sich der maximale Unternehmensgewinn, wenn sich der Kapitalkostensatz oder der Lohnsatz ver- ändern? Zur Untersuchung solcher Problemstellungen wird im Folgenden mit f : D1 ×D2 ⊆ Rn+m −→ R, (x,α) %→ f (x,α) eine in x zu optimierende Funktion betrachtet, die neben n Variablen x = (x1, . . . , xn)T auch noch von m Parametern α = (α1, . . . , αm)T abhängt. Durch max x∈D1 f (x,α) und min x∈D1 f (x,α) (24.47) ist dann der maximale bzw. der minimale Wert der Funktion f auf der Menge D1 für feste Parameterwerte α = (α1, . . . , αm)T gegeben. Für die Ermittlung, wie sich der optimale Wert von f bei Änderung der Parameter α verhält, werden die Extremalwerte (24.47) als Funktion von α∈D2 aufgefasst. Man erhält dann, je nach Betrachtung eines Maximierungs- oder Minimierungsproblems, die reellwertige Funktion v : D2 ⊆ Rm −→ R, α %→ v(α) := max x∈D1 f (x,α) (24.48) oder v : D2 ⊆ Rm −→ R, α %→ v(α) := min x∈D1 f (x,α), (24.49) die als Maximalwert- bzw. Minimalwertfunktion oder häufig einfach nur als Wertfunktion von f bezeichnet wird. Die Stelle x ∈ D1, welche die Funktion f (x,α) optimiert, hängt von α ∈ D2 ab und wird deshalb mit x∗(α) bezeichnet. Dabei ist es durchaus möglich, dass es für einen gegebenen Parametervektor α mehrere x gibt, die f (x,α) optimieren. In einem solchen Fall bezeichnet x∗(α) eine dieser Möglichkeiten. Es gilt folglich v(α) = f (x∗(α),α) . Bei der Wertfunktion handelt es sich somit um eine reellwertige Funktion, die aus f dadurch entsteht, dass die n Variablen x1, . . . , xn ihre optimalen Werte bereits angenommen haben und der Wert von f nur noch in Abhängigkeit von den m Parametern α1, . . . , αm analysiert wird. Das heißt, die Werte der Maximalwertfunktion v(α) = maxx∈D1 f (x,α) und der Minimalwertfunktion v(α) = minx∈D1 f (x,α) stellen alle möglichen Maximal- bzw. Minimalwerte der Funktion f dar, die sich bei Änderung der m Parameter α1, . . . , αm ergeben können. Man sagt daher, dass die Maximalwert- und Minimalwertfunktion für unterschiedliche Parameterwerte die Menge der maximierten bzw. minimierten Zielfunktionswerte von oben bzw. von unten „einhüllt“, und bezeichnet v(α) als Einhüllende der Kurvenschar {f (x,α) : x ∈ D1}. Die Abbildung 24.15 veranschaulicht diesen Sachverhalt anhand einer Maximalwertfunktion v(α) = maxx∈D1 f (x, α) für den Spezialfall m = 1 (d. h. für nur einen Parameter α). Für jedes x ∈ D1 existiert eine Funktion α %→ f (x, α) und die Abbildung 24.15 zeigt die Graphen von vier solchen Funktionen. Es ist zu erkennen, dass f (x, α) ≤ v(α) für alle α 740 Kapitel 2424.4 Wertfunktionen und Einhüllendensatz f (x1, α) f (x2, α) f (x3, α) f (x4, α) α v α0 Abb. 24.15: Graph der Maximalwertfunktion (Einhüllenden) v(α) = maxx∈D1 f (x, α) und vier Kurven aus der Kurvenschar{f (x, α) : x ∈ D1} und x gilt. Allerdings gibt es jedoch für jedes α0 mindestens ein x∗(α0) mit f (x∗(α0), α0) = v(α0) und die Graphen von f (x∗(α0), α) und v(α) berühren sich an der Stelle α0. Im Folgenden wird der sogenannte Einhüllendensatz – auch Envelope-Theorem genannt – vorgestellt, der in der Ökonomie zahlreiche Anwendungen besitzt. Er gibt an, wie sich der Optimalwert einer reellwertigen Funktion f mit m Parametern bei Veränderung der einzelnen Parameter verhält. Dabei unterscheidet man gewöhnlich zwischen dem Einhüllendensatz für Optimierungsprobleme ohne und dem Einhüllendensatz für Optimierungsprobleme mit Nebenbedingungen. Einhüllendensatz ohne Nebenbedingungen Der Einhüllendensatz für die Optimierung einer reellwertigen Funktion f : D1 ×D2 ⊆ Rn+m −→ R, (x,α) %→ f (x,α) mit n Variablen x = (x1, . . . , xn)T und m Parametern α = (α1, . . . , αm)T macht eine Aussage über die partiellen Ableitungen der Wertfunktion v. Satz 24.22 (Einhüllendensatz) Es sei f : D1 × D2 ⊆ Rn+m −→ R, (x,α) %→ f (x,α) eine stetig partiell differenzierbare Funktion auf einer offenen Menge D1×D2 und zu α0 ∈ D2 gebe es ein ε > 0, so dass x∗(α) für jedes α ∈ K<(α0, ε) eine Maximalstelle (Minimalstelle) von f ist. Ferner sei angenommen, dass die Wertfunktion v stetig partiell differenzierbar ist. Dann gilt ∂v(α0) ∂αi = ∂f (x ∗(α0),α0) ∂αi (24.50) für alle i = 1, . . . , m. Beweis: Es sei α %→ ϕ(α) := f (x∗(α0),α) − v(α) für alle α ∈ K<(α0, ε). Bei x∗(α0) handelt es sich um eine Maximalstelle (Minimalstelle) von f (x,α), wenn α = α0 gilt. Dies impliziert ϕ(α0) = 0. Aus der Definition der Wertfunktion v folgt ferner, dass ϕ(α) ≤ 0 im Falle eines Maximierungsproblems und ϕ(α) ≥ 0 im Falle eines Minimierungsproblems für alle α ∈ K<(α0, ε) gilt (vgl. (24.48)–(24.49)). Folglich besitzt ϕ an der Stelle α0 ein Maximum (Minimum). Mit der notwendigen Bedingung für lokale Extrema (d. h. dem Kriterium von Fermat, vgl. Satz 24.1) folgt somit, dass die m ersten partiellen 741 Kapitel 24 Nichtlineare Optimierung im Rn Ableitungen von ϕ an der Stelle α0 gleich Null sind. Man erhält somit 0 = ∂ϕ(α0) ∂αi = ∂f (x ∗(α0),α0) ∂αi − ∂v(α0) ∂αi für alle i = 1, . . . , m und damit die Behauptung (24.50). Die Aussage (24.50) des Einhüllendensatzes ist durchaus etwas unerwartet, da eine Veränderung eines Parameters αi grundsätzlich zwei verschiedene Auswirkungen auf den optimalen Funktionswert v(α) hat: a) Zum einen bewirkt eine Änderung von αi eine Veränderung des Parametervektors α = (α1, . . . , αm)T und hat somit einen direkten Einfluss auf v(α). b) Zum anderen führt eine Änderung von αi zu einer Veränderung in x∗(α) und übt somit einen indirekten Einfluss auf v(α) aus. Die Aussage (24.50) des Einhüllendensatzes besagt jedoch, dass der Gesamteffekt ∂v(α) ∂αi , den eine marginale Änderung des Parameters αi auf den optimalen Funktionswert v(α) hat, bereits vollständig durch die partielle Ableitung von f bezüglich αi , also den direkten Effekt, gegeben ist. Das heißt, der indirekte Effekt, der durch eine marginale Veränderung von αi über x∗(α) auf v(α) ausgeübt wird, kann komplett ignoriert werden. Die Ursache hierfür ist, dass Änderungen in Optimalstellen x∗, die durch marginale Veränderungen in α herx 0.0 0.5 1.0 1.5 2.0 0.0 0.5 1.0 1.5 2.0 −3 −2 −1 0 1 2 3 f (x, α) = − (x − α)2 + α + 1 v(α) = max x∈(0, 2) f (x, α) α 0 0.5 1 1.5 2 0 0.5 1 1.5 2 2.5 3 f (0, α) f (0.4 , α) f (0.8 , α) f (1.2 , α) f (1.6 , α) f (2, α) v(α) = max x∈(0, 2) f (x, α) Abb. 24.16: Graph der Funktion f : (0, 2)2 −→ R, (x, α) %→ f (x, α) = −(x − α)2 + α + 1 und ihre Maximalwerte v(α) = maxx∈(0,2) f (x, α) (links) und Maximalwertfunktion v(α) = maxx∈(0,2) f (x, α) von f sowie sechs Kurven aus der Kurvenschar {f (x, α) : x ∈ (0, 2)} (rechts) vorgerufen werden, eine vernachlässigbare Auswirkung auf den Wert f (x∗(α),α) haben. Beispiel 24.23 (Einhüllendensatz) Betrachtet wird die stetig partiell differenzierbare Funktion f : (0, 2)2 →R, (x, α) %→f (x, α)=−(x−α)2+α+1. Für einen festen, aber beliebigen Wert des Parameters α ∈ (0, 2) erhält man für die erste und zweite Ableitung von f bezüglich der Variablen x f ′(x, α) = −2(x − α) und f ′′(x, α) = −2. Daraus folgt, dass x = α eine stationäre Stelle von f (x, α) ist, und mit Folgerung 18.8a) erhält man weiter, dass es sich bei x∗(α) = α um die globale Maximalstelle von f in Abhängigkeit vom Parameter α handelt. Für die Maximalwertfunktion gilt somit v(α) = f (x∗(α), α) = α + 1 und für ihre erste Ableitung erhält man v′(α) = ∂f (x ∗(α), α) ∂α = 1 (vgl. Abbildung 24.16). 742 Kapitel 2424.4 Wertfunktionen und Einhüllendensatz Der Einhüllendensatz besitzt viele ökonomische Anwendungen, da er viele Problemstellungen erheblich vereinfacht. Interessiert man sich zum Beispiel für die Veränderung der Herstellungskosten eines Unternehmens aufgrund einer marginalen Änderung eines Rohstoffpreises, dann genügt es, die unmittelbare Auswirkung einer solchen Veränderung zu untersuchen. Es muss nicht berücksichtigt werden, dass diese Änderung auch die Rohstoffnachfrage verändert. Der Einhüllendensatz ermöglicht daher eine Reihe von wichtigen ökonomischen Schlussfolgerungen. Ein Beleg hierfür ist das folgende Beispiel, in dem mit Hotellings Lemma ein bedeutendes Resultat der Mikroökonomie hergeleitet wird. Beispiel 24.24 (Hotellings Lemma) Betrachtet wird ein Unternehmen, das die beiden Inputfaktoren Kapitaleinsatz K und Arbeitseinsatz L zur Produktion von f (K,L) Mengeneinheiten eines Outputgutes einsetzt. Dabei ist f : (0,∞)2 −→ R eine partiell differenzierbare Produktionsfunktion, und das Unternehmen verfolgt das Ziel der Maximierung seiner Gewinnfunktion π(K,L, p, r, w) = pf (K,L)− rK − wL (24.51) mit gegebenem Outputpreis p sowie gegebenen Faktorpreisen r (Kapitalkostensatz) und w (Lohnsatz). Die optimalen Faktoreinsatzmengen K und L sind von den drei exogenen Variablen (Parametern) p, r und w abhängig und werden deshalb im Folgenden als Funktionen K∗ := K∗(p, r, w) und L∗ := L∗(p, r, w) dieser drei Parameter aufgefasst. Einsetzen von K∗ und L∗ in (24.51) liefert dann die Gewinnfunktion π(K∗, L∗, p, r, w) = pf (K∗, L∗)− rK∗ − wL∗, (24.52) die den maximalen Gewinn als Funktion der drei exogenen Variablen p, r und w angibt. Bei π(K∗, L∗, p, r, w) handelt es sich somit um die Maximalwertfunktion v(p, r, w) = max K,L∈(0,∞) π(K,L, p, r, w) von π , mit deren Hilfe die Frage untersucht werden kann, wie sich der maximal erreichbare Gewinn verändert, wenn die Parameter p, r undw variiert werden. Das heißt, man studiert die Sensitivität des Gewinns π bezüglich der Parameter p, r und w. Für die partiellen Ableitungen von v erhält man mit dem Einhüllendensatz (vgl. (24.50)) die folgenden Ausdrücke: ∂v(p, r, w) ∂p = ∂π(K ∗, L∗, p, r, w) ∂p = f (K∗, L∗) ∂v(p, r, w) ∂r = ∂π(K ∗, L∗, p, r, w) ∂r = −K∗(p, r, w) ∂v(p, r, w) ∂w = ∂π(K ∗, L∗, p, r, w) ∂w = −L∗(p, r, w) H. Hotelling Diese drei Gleichungen werden nach dem US-amerikanischen Statistiker und Volkswirt Harold Hotelling (1895– 1973) als Hotellings Lemma bezeichnet. Die erste Gleichung besagt, dass eine Erhöhung des Outputpreises p um eine Einheit den maximalen Gewinn um ungefähr 1 · f (K∗, L∗) Geldeinheiten steigert. Bei einer marginalen Preiserhöhung muss somit nicht berücksichtigt werden, dass die Erhöhung von p auch zu einer Veränderung der Outputmenge f (K∗, L∗) führt. Die zweite Gleichung besagt, dass eine Erhöhung des Kapitalkostensatzes r den maximalen Gewinn um 1 · K∗(p, r, w) Geldeinheiten reduziert. Folglich muss bei einer marginalen Kapitalkostenerhöhung nicht berücksichtigt werden, dass ein Anwachsen von r zu einer Substitution von Kapital durch Arbeit führt. Eine analoge Interpretation gilt für die dritte Gleichung. 743 Kapitel 24 Nichtlineare Optimierung im Rn Einhüllendensatz mit Nebenbedingungen Für die Optimierung einer reellwertigen Funktion f : D1 ×D2 ⊆ Rn+m −→ R, (x,α) %→ f (x,α) mit n Variablen x = (x1, . . . , xn)T und m Parametern α = (α1, . . . , αm) T unter k Nebenbedingungen g1(x,α) = 0 g2(x,α) = 0 ... gk(x,α) = 0 (24.53) lässt sich ebenfalls ein Einhüllendensatz formulieren, der häufig als verallgemeinerter Einhüllendensatz bezeichnet wird. Er gibt an, wie sich der maximale und der minimale Wert der Funktion f unter Berücksichtigung der k Nebenbedingungen (24.53) bei Variation der Parameter α verändern. Das heißt, der verallgemeinerte Einhüllendensatz gibt Auskunft über das Verhalten der Maximalwert- und Minimalwertfunktion v : D2 ⊆ Rm −→ R, α %→ v(α) := max x∈D1 gp(x,α)=0 für p=1,...,k f (x,α) (24.54) bzw. v : D2 ⊆ Rm −→ R, α %→ v(α) := min x∈D1 gp(x,α)=0 für p=1,...,k f (x,α). (24.55) Im Gegensatz zu Optimierungsproblemen ohne Nebenbedingungen handelt es sich somit bei den Funktionswerten der Wertfunktion (24.54) bzw. (24.55) um die Maximal- bzw. Minimalwerte der Funktion f unter den k Gleichheitsnebenbedingungen (24.53). Der verallgemeinerte Einhüllendensatz liefert nun eine zum (gewöhnlichen) Einhüllendensatz analoge Aussage bezüglich der partiellen Ableitungen der Wertfunktion v. An die Stelle der Funktion f tritt nun jedoch die korrespondierende Lagrange-Funktion L(λ1, . . . , λk, x,α) := f (x,α)+ k∑ p=1 λpgp(x,α). Der verallgemeinerte Einhüllendensatz lautet nun wie folgt: Satz 24.25 (Verallgemeinerter Einhüllendensatz) Es seien f, g1, . . . , gk : D1 × D2 ⊆ Rn+m −→ R stetig partiell differenzierbare Funktionen auf einer offenen Menge D1 × D2, k < n und zu α0 ∈ D2 gebe es ein ε > 0, so dass x∗(α) für jedes α ∈ K<(α0, ε) eine Maximalstelle (Minimalstelle) von f unter den k Nebenbedingungen g1(x,α) = 0, . . . , gk(x,α) = 0 ist. Ferner sei angenommen, dass die (k× n)-dimensionale Jacobi- Matrix Jg(x∗(α),α) für alle α ∈ K<(α0, ε) den vollen Rang k besitzt und die Wertfunktion v stetig partiell differenzierbar ist. Dann gilt ∂v(α0) ∂αi = ∂L(λ1, . . . , λk, x ∗(α0),α0) ∂αi (24.56) für alle i = 1, . . . , m. Beweis: Für einen Beweis unter verschiedenen Annahmen siehe z. B. Sydsaeter et al. [66]. Die große Bedeutung des verallgemeinerten Einhüllendensatzes für die Mikroökonomie wird im nächsten Beispiel bei der Herleitung von Shephards Lemma deutlich. Beispiel 24.26 (Shephards Lemma) Ein Unternehmen benötige die beiden Inputfaktoren Kapitaleinsatz K und Arbeitseinsatz L zur Produktion von insgesamt h(K,L) = x Mengeneinheiten eines Outputgutes. Es sei angenommen, dass die Produktionsfunktion h : (0,∞)2 −→ R partiell differenzierbar ist und dass das Unternehmensziel bei gegebenen Faktorpreisen r (Kapitalkostensatz) und w (Lohnsatz) in der Minimierung der Kostenfunktion C(K,L, r, w) = rK + wL (24.57) unter der Nebenbedingung h(K,L)− x = 0 (24.58) besteht. Die optimalen Werte von K und L sind Funktionen der beiden exogenen Variablen r und w. Sie seien im Folgenden mit K∗ := K∗(r, w) und L∗ := L∗(r, w) 744 Kapitel 2424.5 Optimierung unter Ungleichheitsnebenbedingungen bezeichnet. Durch Einsetzen dieser beiden optimalen Werte in (24.57) für K und L resultiert dann C(K∗, L∗, r, w) = rK∗ + wL∗. (24.59) Die Kostenfunktion C(K∗, L∗, r, w) gibt die minimalen Kosten unter Einhaltung der Nebenbedingung (24.58) als Funktion der beiden Parameter r und w an. Bei C(K∗, L∗, r, w) handelt es sich folglich um die Minimalwertfunktion v(r, w) = min K,L∈(0,∞) f (K,L)=x C(K,L, r, w) von C, und für die zugehörige Lagrange-Funktion gilt L(λ,K∗, L∗, r, w) = rK∗ + wL∗ + λ(f (K∗, L∗)− x). Daraus erhält man mit dem verallgemeinerten Einhüllendensatz (vgl. (24.56)) für die ersten partiellen Ableitungen der Minimalwertfunktion v die beiden Ausdrücke ∂v(r, w) ∂r = ∂L(λ,K ∗, L∗, r, w) ∂r = K∗(r, w) und ∂v(r, w) ∂w = ∂L(λ,K ∗, L∗, r, w) ∂w = L∗(r, w). Diese Gleichungen sind nach dem US-amerikanischen Ökonomen und Statistiker Ronald Shephard (1912–1982) als Shephards Lemma benannt. Es besagt, dass die Nachfrage nach einem Produktionsfaktor der ersten partiellen Ableitung der Minimalwertfunktion v bezüglich des Faktorpreises dieses Produktionsgutes entspricht. 24.5 Optimierung unter Ungleichheitsnebenbedingungen Im letzten Abschnitt wurden mit dem Verfahren der Variablensubstitution und der Lagrangeschen Multiplikatorenregel zwei Methoden vorgestellt, mit denen Optimierungsprobleme unter Gleichheitsnebenbedingungen der Form g1(x) = 0, . . . , gk(x) = 0 gelöst werden können. In ökonomischen Problemstellungen treten jedoch häufig auch Ungleichheitsnebenbedingungen der Gestalt g1(x) ≤ 0 g2(x) ≤ 0 ... gk(x) ≤ 0 auf. So wird zum Beispiel oftmals verlangt, dass die Werte von Variablen, welche die Anzahl von Geld- oder Mengeneinheiten angeben, nichtnegativ sind, so dass die Lösung ökonomisch sinnvoll ist. Ferner geben Kapazitäts- oder Budgetrestriktionen gewöhnlich lediglich obere Verfügbarkeitsgrenzen an, die nicht notwendigerweise voll ausgeschöpft werden müssen. Die Berechnung der Optimalstellen einer reellwertigen Funktion in n Variablen unter Ungleichheitsnebenbedingungen ist jedoch im Allgemeinen eine sehr komplexe mathematische Problemstellung. Es existieren daher nur für einige ausgewählte Klassen von Optimierungsproblemen Lösungskonzepte und Algorithmen. Zum Beispiel bilden die sogenannten linearen Optimierungsprobleme, die in Kapitel 25 betrachtet werden, eine solche Klasse. Eine weitere Klasse ist durch die Gruppe der konvexen Optimierungsprobleme gegeben, die eine Verallgemeinerung von linearen Optimierungsproblemen darstellen und Gegenstand dieses Abschnitts sind. Konvexes Optimierungsproblem Von einem konvexen Optimierungsproblem spricht man, wenn eine konvexe Zielfunktion unter Einhaltung einer oder mehrerer konvexer Ungleichheitsnebenbedingungen minimiert werden soll. Definition 24.27 (Konvexes Optimierungsproblem) Ein Optimierungsproblem der Form min f (x) (24.60) unter den k Nebenbedingungen g1(x) ≤ 0 g2(x) ≤ 0 ... gk(x) ≤ 0 (24.61) mit konvexen reellwertigen Funktionen f, g1, . . . , gk in n Variablen wird als konvexes Optimierungsproblem bezeichnet. Erfüllt ein x ∈ Rn alle k Nebenbedingungen (24.61), dann sagt man, dass x zulässig ist, und die Menge Z := {x ∈ Rn : g1(x) ≤ 0, . . . , gk(x) ≤ 0} aller zulässigen Vektoren wird als zulässiger Bereich des konvexen Optimierungsproblems bezeichnet. Die p-te Nebenbe- 745 Kapitel 24 Nichtlineare Optimierung im Rn dingung gp(x) ≤ 0 heißt bindend oder aktiv an der Stelle x ∈ Z , wenn gp(x) = 0 gilt. Ist dagegen gp(x) < 0 erfüllt, dann sagt man, dass die p-te Nebenbedingung nicht bindend oder nicht aktiv ist. Ein konvexes Optimierungsproblem zeichnet sich gegenüber einem allgemeinen Extremwertproblem durch die folgenden beiden Eigenschaften aus: a) Der zulässige Bereich Z ist eine konvexe Menge. Aus der Konvexität der Funktionen g1, g2, . . . , gk folgt, dass für beliebige x1, x2 ∈ Z und α ∈ (0, 1) gp(αx1 + (1 − α)x2) ≤ αgp(x1)+ (1 − α)gp(x2) ≤ 0 für alle p = 1, . . . , k gilt (vgl. Definition 21.38). Das heißt, es gilt αx1+(1−α)x2 ∈ Z für beliebige x1, x2 ∈ Z und α ∈ (0, 1). Somit ist Z eine konvexe Menge (vgl. Definition 7.25). b) Eine lokale Minimalstelle ist stets auch eine globale Minimalstelle (vgl. Satz 21.43). Das heißt, man kann sich auf die Bestimmung lokaler Minimalstellen beschränken. Die Klasse der konvexen Optimierungsprobleme umfasst auch Maximierungsprobleme, da die Minimierung einer Funktion f der Maximierung der Funktion −f entspricht und eine Funktion f genau dann konvex ist, wenn die Funktion −f konkav ist. Dies bedeutet, dass auch ein Extremwertproblem max f (x) unter den Nebenbedingungen g1(x) ≤ 0 g2(x) ≤ 0 ... gk(x) ≤ 0 mit einer konkaven reellwertigen Funktion f und konvexen reellwertigen Funktionen g1, g2, . . . , gk in ein konvexes Optimierungsproblem überführt werden kann. Darüber hinaus können auch Nichtnegativitätsbedingungen der Form xi ≥ 0 für eine oder mehrere Variablen xi durch Nebenbedingungen der Gestalt g(x) = −xi ≤ 0 im Rahmen von konvexen Optimierungsproblemen berücksichtigt werden, da lineare Funktionen sowohl konvex als auch konkav sind. Weiter sei darauf hingewiesen, dass bei Optimierungsproblemen unter k Ungleichheitsnebenbedingungen (24.61) im Gegensatz zu den in Abschnitt 24.3 betrachteten Optimierungsproblemen unter k Gleichheitsnebenbedingungen nicht gefordert werden muss, dass k < n gilt. Das heißt, bei Optimierungsproblemen unter Ungleichheitsnebenbedingungen können auch mehr Nebenbedingungen zugelassen werden als Variablen existieren, über die optimiert wird (vgl. Beispiel 24.32). Dies ist dadurch begründet, dass eine Ungleichung im Gegensatz zu einer Gleichung den Wert einer Variablen nicht festlegt, sondern stets einen ganzen Bereich abdeckt. Das heißt, der zulässige Bereich Z muss für k > n nicht zwansläufig leer sein. Von besonderer Bedeutung sind konvexe Optimierungsprobleme, bei denen sowohl die Zielfunktion f als auch die k Nebenbedingungsfunktionen g1, g2, . . . , gk affin-linear sind. Man spricht dann von linearen Optimierungsproblemen. Im nachfolgenden Kapitel 25 wird sich zeigen, dass mit dem sogenannten Simplex-Algorithmus ein sehr leistungsstarkes Verfahren zur Lösung solcher spezieller Optimierungsprobleme existiert. Karush-Kuhn-Tucker-Bedingungen H. W. Kuhn Für die Lösung allgemeiner konvexer Optimierungsprobleme sind die als Karush-Kuhn- Tucker-Bedingungen bezeichneten Optimalitätsbedingungen von zentraler Bedeutung. Zu Beginn der fünfziger und sechziger Jahre (des letzten Jahrhunderts) waren diese Bedingungen jedoch noch ausschließlich unter den Namen der beiden einflussreichen USamerikanischen Mathematiker Harold William Kuhn (*1925) und Albert William Tucker (1905–1995) als Kuhn-Tucker- Bedingungen bekannt. Sie waren 1950 die ersten, die diese Optimalitätsbedingungen in ihrem wegweisenden Konferenzbeitrag „Nonlinear Programming“ veröffentlicht haben. A. W. Tucker In den siebziger Jahren wurde jedoch entdeckt, dass der US-amerikanische Mathematiker William Karush (1917–1997) diese Bedingungen bereits im Jahre 1939 in seiner Master-Arbeit an der Uni- 746 Kapitel 2424.5 Optimierung unter Ungleichheitsnebenbedingungen versität Chicago formuliert, jedoch nie veröffentlicht hatte. Aus diesem Grund hat sich in der Literatur in den letzten drei Jahrzehnten – auch auf einen Vorschlag von Kuhn und Tucker hin – mehr und mehr die Bezeichnung Karush-Kuhn-Tucker- Bedingungen (kurz KKT-Bedingungen) durchgesetzt. Bei den KKT-Bedingungen handelt es sich um eine Erweiterung der Lagrangeschen Multiplikatorenregel. Sie basieren ebenfalls auf einer Untersuchung der Lagrange-Funktion von f bezüglich der Nebenbedingungsfunktionen g1, g2, . . . , gk , also auf einer Betrachtung der Funktion L(λ1, . . . , λk, x) = f (x)+ k∑ p=1 λpgp(x). (24.62) Wie bereits erwähnt, ist die Lösung von Optimierungsproblemen unter Ungleichheitsnebenbedingungen mathematisch deutlich komplexer als die von Optimierungsproblemen unter ausschließlich Gleichheitsnebenbedingungen. Die Ursache hierfür ist, dass die Lösungen dazu tendieren, auf dem Rand des zulässigen Bereichs Z zu liegen, bei dem ein Teil der Restriktionen als Gleichungen und der andere Teil als echte Ungleichungen erfüllt sind. Dabei ist jedoch nicht von vornherein bekannt, welche der Nebenbedingungen bindend – also als Gleichungen erfüllt – sind und welche nicht. Es stellt sich damit die Frage, für welche Restriktionen man Lagrange- Multiplikatoren benötigt und für welche Nebenbedingungen man sich in der Situation eines unrestringierten Optimierungsproblems befindet. Die folgenden KKT-Bedingungen ermöglichen eine systematische Untersuchung dieser Frage. Definition 24.28 (Karush-Kuhn-Tucker- Bedingungen) Für ein konvexes Optimierungsproblem (24.60)– (24.61) mit stetig partiell differenzierbaren Funktionen f, g1, . . . , gk erfüllt x0 ∈ Rn die KKT-Bedingungen, wenn k Lagrange-Multiplikatoren λ1, . . . , λk ∈ R mit den folgenden Eigenschaften existieren: ∂L(λ1, . . . , λk, x0) ∂xj = ∂f (x0) ∂xj + k∑ p=1 λp ∂gp(x0) ∂xj = 0 für j = 1, . . . , n (24.63) gp(x0) ≤ 0 für p = 1, . . . , k (24.64) λp ≥ 0 für p = 1, . . . , k (24.65) λpgp(x0) = 0 für p = 1, . . . , k (24.66) Bei der KKT-Bedingung (24.63) handelt es sich um die Bedingung, die auch bei der Lagrangeschen Multiplikatorenregel verwendet wird (vgl. Satz 24.15), und durch die KKT-Bedingung (24.64) wird sichergestellt, dass x0 den k Nebenbedingungen genügt. Folglich stellen lediglich die beiden KKT-Bedingungen (24.65)–(24.66) eine Erweiterung dar. Durch (24.65) wird sichergestellt, dass die Lagrange-Funktion (24.62) eine konvexe Funktion in der ndimensionalen Variablen x ist (vgl. Beweis von Satz 24.29), und bei (24.66) handelt es sich um die sogenannte komplementäre Schlupfbedingung (engl. complementary slackness condition). Die Ungleichungen λp ≥ 0 und gp(x0) ≤ 0 sind in dem Sinne komplementär, dass höchstens eine von beiden „echt“ sein darf. Das heißt, im Falle einer nicht bindenden p-ten Nebenbedingung (also gp(x0) < 0) muss λp = 0 gelten, und die p-te Nebenbedingung spielt dann in der Lagrange-Funktion (24.62) keine Rolle. Gilt dagegen λp > 0, dann muss die p-te Nebenbedingung bindend sein (also gp(x0) = 0), und die p-te Nebenbedingung wird demnach in der Lagrange-Funktion (24.62) berücksichtigt. Die Abbildung 24.17 zeigt zwei konvexe Optimierungsprobleme min f (x, y) unter einer Ungleichheitsnebenbedingung g(x, y) ≤ 0 mit stetig partiell differenzierbaren Funktionen f und g. Beim Optimierungsproblem links ist die Nebenbedingung an der Minimalstelle (x0, y0) bindend, d. h. es gilt g(x0, y0) = 0, weshalb (x0, y0) ein Randpunkt des zulässigen Bereichs Z={(x,y)∈R2 : g(x,y)≤0} ist. Die Stelle (x0,y0) löst folglich das Optimierungsproblem min f (x,y) unter der Gleichheitsnebenbedingung g(x, y)=0, und es existiert gemäß Satz 24.15 – unter der Voraussetzung grad g(x0, y0) = (0, 0)T – ein Lagrange-Multiplikator λ, so dass die Lagrange- Funktion L(λ, x, y) = f (x, y)+ λg(x, y) die Bedingung (24.63) erfüllt. Beim Optimierungsproblem rechts ist dagegen die Nebenbedingung an der Minimalstelle (x0, y0) nicht bindend, d. h. es gilt g(x0, y0)<0, und (x0, y0) ist eine stationäre Stelle von f , so dass gemäß Satz 24.1 für die beiden ersten partiellen Ableitungen ∂f (x0,y0) ∂x = ∂f (x0,y0) ∂y = 0 gelten muss. Setzt man nun λ = 0, dann sind die KKT-Bedingungen (24.63)-(24.66) erfüllt. KKT-Bedingungen als hinreichendes und notwendiges Kriterium Der folgende Satz besagt, dass die KKT-Bedingungen bei konvexen Optimierungsproblemen tatsächlich ein hinreichendes Kriterium für die Existenz globaler Minimalstellen darstellen. 747 Kapitel 24 Nichtlineare Optimierung im Rn f (x, y)=(x−5)2+(y−5)2 1 4 16 25 36 36 36 36 l l (x0, y0) Minimum g(x, y) ≤ 0 f (x, y)=(x−1)2+(y−1)2 1 4 9 16 25 36 49 64 l (x0, y0) Minimum g(x, y) ≤ 0 Abb. 24.17: Die Nebenbedingung g(x, y) = x2 + y − 9 ≤ 0 ist für die Minimalstelle (x0, y0) von f (x, y) = (x − 5)2 + (y − 5)2 bindend (links) und für die Minimalstelle (x0, y0) von f (x, y) = (x − 1)2 + (y − 1)2 nicht bindend (rechts) Satz 24.29 (KKT-Bedingungen als hinreichendes Kriterium) Für ein konvexes Optimierungsproblem (24.60)– (24.61) mit stetig partiell differenzierbaren Funktionen f, g1, . . . , gk erfülle x0 ∈ Rn die KKT-Bedingungen. Dann ist x0 eine globale Minimalstelle dieses Optimierungsproblems. Beweis: Es sei angenommen, dass x0 ∈ Rn die KKT- Bedingungen (24.63)–(24.66) erfüllt und x ∈ Rn eine beliebige weitere Stelle ist, die den k Ungleichheitsnebenbedingungen (24.61) genügt. Das heißt, es gilt x0, x ∈ Z und es ist zu zeigen, dass dann f (x0) ≤ f (x) erfüllt ist. Die Bedingung (24.65) impliziert zusammen mit der Konvexität der Funktionen f, g1, . . . , gk , dass es sich bei der Lagrange-Funktion (24.62) um eine Summe konvexer Funktionen handelt und sie damit bezüglich x selbst eine konvexe Funktion auf Z ist (vgl. hierzu Satz 13.17a)). Folglich ist x0 für feste Lagrange- Multiplikatoren λ1, . . . , λk eine globale Minimalstelle der Funktion x %→ L(λ1, . . . , λk, x) (vgl. Satz 24.5a)). Das heißt, es gilt L(λ1, . . . , λk, x0) ≤ L(λ1, . . . , λk, x) und somit auch f (x0) ≤ f (x)+ k∑ p=1 λp ( gp(x)− gp(x0) ) . (24.67) Es genügt daher zu zeigen, dass die Summe∑k p=1 λp ( gp(x)− gp(x0) ) auf der rechten Seite von (24.67) kleiner oder gleich Null ist. Hierzu sind zwei Fälle zu unterscheiden: a) Es sei gp(x0) < 0. Dann folgt mit der komplementären Schlupfbedingung (24.66), dass λp = 0 und damit insbesondere auch λp ( gp(x)− gp(x0) ) = 0 gilt. b) Es sei gp(x0) = 0. Dann folgt mit der Bedingung (24.65), dass λp ( gp(x)− gp(x0) ) = λpgp(x) ≤ 0 gilt. Das heißt, jeder Summand λp ( gp(x)− gp(x0) ) auf der rechten Seite von (24.67) ist kleiner oder gleich Null. Folglich gilt∑k p=1 λp ( gp(x)− gp(x0) ) ≤ 0, was die Behauptung beweist. Die Implikation „x0 ∈ Rn ist eine globale Minimalstelle eines konvexen Optimierungsproblems ⇒ x0 erfüllt die KKT-Bedingungen“ gilt leider nur unter einer zusätzlichen Qualifikationsbedingung an die Nebenbedingungsfunktionen g1, g2, . . . , gk . Die Situation ist damit vergleichbar zur Lagrangeschen Multiplikatorenregel. Diese ist gemäß Satz 24.15 nur dann eine notwendige Bedingung für ein Extremum unter Gleichheitsnebenbedingungen an der Stelle x0, wenn die Gradienten der k Nebenbedingungsfunktionen g1, g2, . . . , gk an der Stelle x0 linear unabhängig sind. Für konvexe Optimierungsprobleme existieren eine Reihe verschiedener Qualifikationsbedingungen, die sicherstellen, 748 Kapitel 2424.5 Optimierung unter Ungleichheitsnebenbedingungen dass die KKT-Bedingungen nicht nur ein hinreichendes, sondern auch ein notwendiges Kriterium für die Existenz einer Minimalstelle sind. Die drei bekanntesten Qualifikationsbedingungen für eine Stelle x0 ∈ Rn lauten wie folgt: Q1) Die Nebenbedingungsfunktionen g1, g2, . . . , gk sind affin-linear. Q2) Es gibt ein x ∈ Rn mit gp(x) < 0 für alle Nebenbedingungsfunktionen gp , die an der Stelle x0 bindend sind (Slater-Bedingung). Q3) Die Gradienten der an der Stelle x0 bindenden Nebenbedingungsfunktionen gp sind an der Stelle x0 linear unabhängig. Unter Annahme der Gültigkeit einer dieser drei Qualifikationsbedingungen lässt sich der folgende Satz nachweisen. Satz 24.30 (KKT-Bedingungen als notwendiges und hinreichendes Kriterium) Für ein konvexes Optimierungsproblem (24.60)– (24.61) mit stetig partiell differenzierbaren Funktionen f, g1, . . . , gk erfülle x0 ∈ Rn eine der Qualifikationsbedingungen Q1), Q2) oder Q3). Dann ist x0 genau dann eine globale Minimalstelle dieses Optimierungsproblems, wenn x0 die KKT-Bedingungen erfüllt. Beweis: Es sei angenommen, dass x0 ∈ Rn die KKT-Bedingungen erfüllt. Dann ist x0 gemäß Satz 24.29 eine globale Minimalstelle. Für den Nachweis, dass unter der Annahme der Gültigkeit einer der drei Qualifikationsbedingungen Q1), Q2) oder Q3) eine globale Minimalstelle x0 ∈ Rn die KKT-Bedingungen erfüllt, siehe z. B. Collatz-Wetterling [11], Abschnitt 8.1. Die beiden Sätze 24.29 und 24.30 legen es nahe, die Minimalstelle eines konvexen Optimierungsproblems durch Lösen der KKT-Bedingungen (24.63)–(24.66) zu bestimmen. Die KKT-Bedingungen führen jedoch auf ein nichtlineares System von Gleichungen und Ungleichungen, das in den meisten Fällen nur schwer lösbar ist. Es bietet sich daher an, die KKT-Bedingungen in mehrere einfachere gleichungsrestringierte Probleme zu zerlegen, die nur aus den nLagrangeschen Gleichungen (24.63) und den k komplementären Schlupfbedingungen (24.66) bestehen. Diese Zerlegung erfolgt mit Hilfe der KKT-Bedingung (24.66) und je nachdem, welche der k Lagrange-Multiplikatoren λ1, . . . , λk gleich und welche grö- ßer als Null vorausgesetzt werden, resultiert ein anderes gleichungsrestringiertes Problem. Auf diese Weise erhält man insgesamt 2k Fälle, die auf die Existenz einer Minimalstelle zu untersuchen sind. Das Lösen von konvexen Optimierungsproblemen mittels KKT-Bedingungen wird deshalb oft auch mit den Worten „teile und herrsche mit Lagrange“ umschrieben. Das genaue Vorgehen wird im folgenden Beispiel demonstriert. Beispiel 24.31 (Anwendung der KKT-Bedingungen) a) Betrachtet wird das Optimierungsproblem min 4e−x−y − x − 3y (24.68) unter den beiden affin-linearen Nebenbedingungen x + 2y − 2 ≤ 0 (24.69) x + y − 1 ≤ 0 (24.70) (vgl. Abbildung 24.18). Die Funktion f (x, y) = 4e−x−y − x − 3y ist die Summe konvexer Funktionen und somit ebenfalls konvex (vgl. Satz 13.17a)). Folglich handelt es sich bei diesem Optimierungsproblem um ein konvexes Optimierungsproblem, und die Lagrange-Funktion ist gegeben durch L(λ1, λ2, x, y) = 4e−x−y − x − 3y + λ1(x+2y−2) + λ2(x + y − 1). Die Berechnung der beiden ersten partiellen Ableitungen von L bezüglich der Variablen x und y und anschließendes Nullsetzen dieser Ableitungen liefern zusammen mit der komplementären Schlupfbedingung (24.66) das Gleichungssystem: ∂L(λ1, λ2, x, y) ∂x = −4e−x−y − 1 + λ1 + λ2 = 0 (24.71) ∂L(λ1, λ2, x, y) ∂y = −4e−x−y − 3 + 2λ1 + λ2 = 0 (24.72) λ1(x + 2y − 2) = 0 (24.73) λ2(x + y − 1) = 0 (24.74) Bei der Lösung dieses Gleichungssystems sind 22 =4 Fälle zu unterscheiden. 749 Kapitel 24 Nichtlineare Optimierung im Rn x −2 −1 0 1 2 y −2 −1 0 1 2 0 50 100 150 200 f (x, y)=4e −x−y−x−3y l (0, 1, 4e −1 − 3) f (x, y)=4e −x−y−x−3y −5 −4 −3 4 * exp(−1) − 3 −1 0 1 3 5 10 20 50 100 l (0, 1) Abb. 24.18: Veranschaulichung der Minimierung der Funktion f (x, y) = 4e−x−y − x − 3y unter den beiden Nebenbedingungen x + 2y − 2 ≤ 0 und x + y − 1 ≤ 0 mit Hilfe des Graphen von f (links) und Niveaulinien von f (rechts) Fall 1: Es gelte λ1 =λ2 =0. Aus (24.71) folgt dann −4e−x−y = 1, was ein Widerspruch zu e−x−y >0 ist. Fall 2: Es gelte λ1 > 0 und λ2 = 0. Mit λ2 = 0 erhält man für (24.71)–(24.72) −4e−x−y − 1 + λ1 = 0 (24.75) −4e−x−y − 3 + 2λ1 = 0, (24.76) und die Subtraktion der ersten Gleichung von der zweiten Gleichung liefert λ1 = 2. Durch Einsetzen dieses Wertes in (24.75) und eine kurze Umformung resultiert −x − y = ln ( 14 ) , also x + y = ln(4) > 1. Dies ist jedoch ein Widerspruch zu (24.70). Fall 3: Es gelte λ1 = 0 und λ2 > 0. Subtraktion der Gleichung (24.71) von der Gleichung (24.72) und anschließendes Einsetzen von λ1 = 0 liefern den Widerspruch −2 = 0. Fall 4: Es gelte λ1, λ2 > 0. Dann erhält man aus (24.73)–(24.74) das lineare Gleichungssystem x + 2y = 2 x + y = 1, welches nach kurzer Rechnung zur Lösung x = 0 und y = 1 führt. Die KKT-Bedingungen liefern somit die globale Minimalstelle (0, 1) und das globale Minimum f (0, 1) = 4e−1 − 3. Wegen λ1 > 0, λ2 > 0 sind an dieser Minimalstelle beide Nebenbedingungen (24.69)–(24.70) bindend, d. h. als Gleichungen erfüllt. Da das konvexe Optimierungsproblem (24.68)–(24.70) offensichtlich die Qualifikationsbedingung Q1) erfüllt, sind die KKT-Bedingungen nicht nur ein hinreichendes Kriterium, sondern auch ein notwendiges Kriterium für die Existenz einer globalen Minimalstelle. Folglich handelt es sich bei (0, 1) um die einzige globale Minimalstelle des Optimierungsproblems (vgl. Abbildung 24.18). b) Betrachtet wird das Optimierungsproblem min x2 + y2 (24.77) unter einer affin-linearen Nebenbedingung und zwei Nichtnegativitätsbedingungen −x − 2y + 2 ≤ 0 und x ≥ 0, y ≥ 0 (24.78) (vgl. Abbildung 24.19). Die Funktion f (x, y) = x2 + y2 ist als Summe streng konvexer Funktionen selbst wieder streng konvex. Bei dem Optimierungsproblem (24.77)–(24.78) handelt es sich also um ein 750 Kapitel 2424.5 Optimierung unter Ungleichheitsnebenbedingungen konvexes Optimierungsproblem unter den drei affinlinearen Nebenbedingungen −x − 2y + 2 ≤ 0 (24.79) −x ≤ 0 (24.80) −y ≤ 0 (24.81) und die zugehörige Lagrange-Funktion lautet L(λ1, λ2, λ3, x, y) = x2 + y2 − λ1(x + 2y − 2) − λ2x − λ3y. Das Berechnen der beiden ersten partiellen Ableitungen von L und anschließendes Nullsetzen dieser Ableitungen führen zusammen mit der komplementären Schlupfbedingung (24.66) zum Gleichungssystem: ∂L(λ1, λ2, λ3, x, y) ∂x =2x − λ1 − λ2 = 0 (24.82) ∂L(λ1, λ2, λ3, x, y) ∂y =2y − 2λ1 − λ3 =0 (24.83) λ1(−x − 2y + 2)=0 (24.84) −λ2x=0 (24.85) −λ3y=0 (24.86) Bei der Lösung dieses Gleichungssystems sind insgesamt 23 = 8 Fälle zu unterscheiden. Fall 1: Es gelte λ1 = λ2 = λ3 = 0. Aus (24.82)– (24.83) folgt dann x = y = 0. Die Lösung (0, 0) verletzt jedoch die Nebenbedingung (24.79) und ist damit keine globale Minimalstelle. Fall 2: Es gelte λ1 > 0 und λ2 = λ3 = 0. Für λ1 > 0 folgt aus (24.84) −x − 2y + 2 = 0 bzw. x + 2y = 2. (24.87) Ferner erhält man mit λ2 = λ3 = 0 und (24.82)– (24.83) das lineare Gleichungssystem 2x − λ1 = 0 2y − 2λ1 = 0. (24.88) Werden diese beiden Gleichungen in (24.87) eingesetzt, resultiert nach kurzer Umformung 12λ1+2λ1 = 2, also λ1 = 45 . Durch Einsetzen dieses Wertes in das lineare Gleichungssystem (24.88) erhält man für die beiden Variablen x und y die Werte x = 25 und y = 45 . Bei ( 2 5 , 4 5 ) handelt es sich somit um eine globale Minimalstelle mit dem Zielfunktionswert f ( 2 5 , 4 5 ) = 4 5 , an der die erste Nebenbedingung (24.79) bindend ist. Fall 3: Es gelte λ2 > 0 und λ1 = λ3 = 0. Aus λ1 = λ3 = 0 und (24.83) folgt y = 0, und λ2 > 0 impliziert zusammen mit (24.85) x = 0. Bei (0, 0) handelt es sich jedoch um keine globale Minimalstelle (vgl. Fall 1). Fall 4: Es gelte λ3 > 0 und λ1 = λ2 = 0. Aus λ1 = λ2 = 0 und (24.82) folgt x = 0, und λ3 > 0 impliziert zusammen mit (24.86) y = 0. Bei (0, 0) handelt es sich jedoch um keine globale Minimalstelle (vgl. Fall 1). Fall 5: Es gelte λ1, λ2 > 0 und λ3 = 0. Aus λ2 > 0 und (24.85) folgt x = 0. Wird x = 0 in (24.82) eingesetzt, erhält man −λ1 = λ2, was im Widerspruch zu λ1, λ2 > 0 steht. Fall 6: Es gelte λ1, λ3 > 0 und λ2 = 0. Aus λ3 > 0 und (24.86) folgt y = 0. Wird y = 0 in (24.83) eingesetzt, erhält man −2λ1 = λ3, was im Widerspruch zu λ1, λ3 > 0 steht. Fall 7 und Fall 8: Es gelte λ2, λ3 > 0 und λ1 = 0 oder λ1, λ2, λ3 > 0. In beiden Fällen folgt aus λ2, λ3 > 0 und (24.85)–(24.86) x = y = 0. Bei (0, 0) handelt es sich jedoch um keine globale Minimalstelle (vgl. Fall 1). Die KKT-Bedingungen liefern folglich die globale Minimalstelle ( 2 5 , 4 5 ) und das globale Minimum beträgt f ( 2 5 , 4 5 ) = 45 . Wegen λ1>0 und λ2 =λ3=0 ist an der Minimalstelle nur die erste Nebenbedingung (24.79) bindend, während die beiden anderen Nebenbedingungen (24.80)–(24.81) nicht bindend, also als echte Ungleichungen erfüllt sind. Da das konvexe Optimierungsproblem (24.77)–(24.78) die Qualifikationsbedingung Q1) erfüllt, ist ( 2 5 , 4 5 ) die einzige globale Minimalstelle des Optimierungsproblems (vgl. Abbildung 24.19). Das folgende Beispiel zeigt, dass im Allgemeinen auf die Qualifikationsbedingungen nicht verzichtet werden kann, wenn sichergestellt sein soll, dass die KKT-Bedingungen ein notwendiges Kriterium für Minimalstellen sind. 751 Kapitel 24 Nichtlineare Optimierung im Rn x 0.0 0.5 1.0 1.5 2.0 2.5 3.0 y 0.0 0.5 1.0 1.5 2.0 2.5 3.0 0 5 10 15 f (x, y)=x2+y2 l (2 5, 4 5, 4 5) f (x, y)=x2+y2 0.2 0.4 0.8 2 3 4 5 6 7 8 9 l (2 5, 4 5) Abb. 24.19: Veranschaulichung der Minimierung der Funktion f (x, y) = x2 +y2 unter der Nebenbedingung −x−2y+2 ≤ 0 und den beiden Nichtnegativitätsbedingungen x ≥ 0 und y ≥ 0 mit Hilfe des Graphen von f (links) und Niveaulinien von f (rechts) Beispiel 24.32 (Qualifikationsbedingungen) Betrachtet wird das sehr einfache Optimierungsproblem min f (x) = x (24.89) unter der Nebenbedingung und der Nichtnegativitätsbedingung (x − 1)2 ≤ 0 bzw. x ≥ 0. (24.90) Bei (24.89)–(24.90) handelt es sich um ein konvexes Optimierungsproblem unter den beiden Nebenbedingungen (x − 1)2 ≤ 0 (24.91) −x ≤ 0. (24.92) Das heißt, es besitzt den zulässigen Bereich Z = {1} und x0 = 1 ist daher die Minimalstelle. Die Lagrange- Funktion lautet L(λ1, λ2, x) = x + λ1(x − 1)2 − λ2x und die KKT-Bedingungen (24.63)–(24.66) sind gegeben durch: 1 + 2λ1(x − 1)− λ2 = 0 (x − 1)2 ≤ 0 −x ≤ 0 λ1, λ2 ≥ 0 λ1(x − 1)2 = 0 −λ2x = 0 (24.93) Die Minimalstelle x0 = 1 erfüllt die KKT-Bedingungen offensichtlich nicht, denn aus der ersten Bedingung in (24.93) folgt λ2 = 1, was gegen die letzte Bedingung in (24.93) verstößt. Dies ist allerdings kein Widerspruch zu Satz 24.30, denn das konvexe Optimierungsproblem (24.89)–(24.90) erfüllt keine der drei Qualifikationsbedingungen Q1), Q2) und Q3): Die erste Nebenbedingung ist nicht affin-linear, die Slater-Bedingung g1(x) = (x − 1)2 < 0 ist für kein x ∈ R erfüllbar und für den Gradienten von g1 an der Stelle x0 gilt grad g1(x0) = g′1(x0) = 0. 752 Kapitel 2424.6 Optimierung unter Gleichheits- und Ungleichheitsnebenbd. 24.6 Optimierung unter Gleichheitsund Ungleichheitsnebenbedingungen Verallgemeinertes konvexes Optimierungsproblem Wirtschaftswissenschaftliche Fragestellungen führen häufig zu Optimierungsproblemen mit sowohl Gleichheits- als auch Ungleichheitsnebenbedingungen. Solche Problemstellungen lassen sich oftmals im Rahmen von verallgemeinerten konvexen Optimierungsproblemen lösen. Definition 24.33 (Verallgemeinertes konvexes Optimierungsproblem) Ein Optimierungsproblem der Form min f (x) (24.94) unter den k + l Nebenbedingungen gp(x) ≤ 0 für p = 1, . . . , k (24.95) hq(x) = 0 für q = 1, . . . , l (24.96) mit l < n und konvexen reellwertigen Funktionen f, g1, . . . , gk sowie affin-linearen reellwertigen Funktionen h1, h2, . . . , hl in n Variablen wird als verallgemeinertes konvexes Optimierungsproblem bezeichnet. Bei einem verallgemeinerten konvexen Optimierungsproblem sind also zusätzlich auch affin-lineare Gleichheitsnebenbedingungen der Form n∑ i=1 aixi − b = 0 mit a1, a2, . . . , an, b ∈ R zugelassen. Die Menge der zulässigen x ∈ Rn, also der zulässige Bereich des Optimierungsproblems, ist gegeben durch Z := {x ∈ Rn : gp(x) ≤ 0 und hq(x) = 0 für p = 1, . . . , k und q = 1, . . . , l}. Die p-te Ungleichheitsnebenbedingung gp(x) ≤ 0 heißt wieder bindend oder aktiv an der Stelle x ∈ Z , wenn gp(x) = 0 gilt, und nicht bindend oder nicht aktiv, falls gp(x) < 0 erfüllt ist. Verallgemeinerte Karush-Kuhn-Tucker- Bedingungen Völlig analog zu (gewöhnlichen) konvexen Optimierungsproblemen lassen sich auch für verallgemeinerte konvexe Optimierungsprobleme KKT-Bedingungen formulieren. Diese basieren nun auf der Untersuchung der Lagrange-Funktion von f bezüglich der k + l Nebenbedingungsfunktionen g1, g2, . . . , gk, h1, h2, . . . , hl , d. h. auf der Betrachtung der Funktion L(λ,μ, x) = f (x)+ k∑ p=1 λpgp(x)+ l∑ q=1 μqhq(x). (24.97) Die verallgemeinerten KKT-Bedingungen sind in der folgenden Definition zusammengefasst: Definition 24.34 (Verallgemeinerte Karush-Kuhn- Tucker-Bedingungen) Für ein verallgemeinertes konvexes Optimierungsproblem (24.94)–(24.96) mit stetig partiell differenzierbaren Funktionen f, g1, . . . , gk, h1, h2, . . . , hl und l < n erfüllt x0 ∈ Rn die verallgemeinerten KKT-Bedingungen, wenn insgesamt k + l Lagrange-Multiplikatoren λ1, . . . , λk, μ1, . . . , μl ∈ R mit den folgenden Eigenschaften existieren: ∂L(λ,μ, x0) ∂xj = ∂f (x0) ∂xj + k∑ p=1 λp ∂gp(x0) ∂xj + l∑ q=1 μq ∂hq(x0) ∂xj = 0 für j = 1, . . . , n (24.98) gp(x0) ≤ 0 für p = 1, . . . , k (24.99) hq(x0) = 0 für q = 1, . . . , l (24.100) λp ≥ 0 für p = 1, . . . , k (24.101) λpgp(x0) = 0 für p = 1, . . . , k (24.102) Die (verallgemeinerten) KKT-Bedingungen sind also wieder gegeben durch die einzuhaltenden Nebenbedingungen (24.95)–(24.96), den gleich Null gesetzten ersten partiellen Ableitungen der Lagrange-Funktion (24.97) nach den n Variablen x1, . . . , xn sowie den Nichtnegativitätsbedingungen und komplementären Schlupfbedingungen für die zu den k Ungleichheitsnebenbedingungen (24.95) 753 Kapitel 24 Nichtlineare Optimierung im Rn gehörenden Lagrange-Multiplikatoren λ1, . . . , λk . Die zu den l Gleichheitsnebenbedingungen (24.96) gehörenden Lagrange-Multiplikatoren μ1, . . . , μl müssen dagegen keinen Nichtnegativitätsbedingungen oder komplementären Schlupfbedingungen genügen. Verallgemeinerte KKT-Bedingungen als hinreichendes und notwendiges Kriterium Völlig analog zu Satz 24.29 lässt sich zeigen, dass die verallgemeinerten KKT-Bedingungen bei verallgemeinerten konvexen Optimierungsproblemen ein hinreichendes Kriterium für die Existenz globaler Minimalstellen darstellen. Darüber hinaus lässt sich nachweisen, dass bei Gültigkeit einer (entsprechend angepassten) Qualifikationsbedingung die verallgemeinerten KKT-Bedingungen auch ein notwendiges Kriterium sind. Diese auf verallgemeinerte konvexe Optimierungsprobleme angepassten Qualifikationsbedingungen für eine Stelle x0 ∈ Rn lauten wie folgt: Q1’) Die Nebenbedingungsfunktionen g1, g2, . . . , gk, h1, h2, . . . , hl sind affin-linear. Q2’) Es gibt ein x ∈ Rn mit hq(x) = 0 für alle q = 1, . . . , l und gp(x) < 0 für alle Nebenbedingungsfunktionen gp , die an der Stelle x0 bindend sind (Slater-Bedingung). Q3’) Die Gradienten der Nebenbedingungsfunktionen h1, h2, . . . , hl und die Gradienten der an der Stelle x0 bindenden Nebenbedingungsfunktionen gp sind an der Stelle x0 linear unabhängig. Unter Annahme der Gültigkeit einer dieser drei Qualifikationsbedingungen lässt sich der folgende Satz nachweisen. Satz 24.35 (Verallg. KKT-Bed. als notwendiges und hinreichendes Kriterium) Für ein verallgemeinertes konvexes Optimierungsproblem (24.94)–(24.96) mit stetig partiell differenzierbaren Funktionen f, g1, . . . , gk, h1, h2, . . . , hl erfülle x0 ∈ Rn eine der Qualifikationsbedingungen Q1’), Q2’) oder Q3’). Dann ist x0 genau dann eine globale Minimalstelle dieses Optimierungsproblems, wenn x0 die verallgemeinerten KKT-Bedingungen erfüllt. Beweis: Siehe die Beweise der beiden Sätze 24.29 und 24.30. Die Anwendung der verallgemeinerten KKT-Bedingungen wird im folgenden Beispiel verdeutlicht. Beispiel 24.36 (Anwendung der verallgemeinerten KKT-Bedingungen) Betrachtet wird das Optimierungsproblem min f (x, y) = (x − 3)2 + (y − 2)2 (24.103) unter den Nebenbedingungen x2 + y2 − 5 ≤ 0 (24.104) −x ≤ 0 (24.105) −y ≤ 0 (24.106) x + 2y − 4 = 0 (24.107) (vgl. Abbildung 24.20). Es handelt sich um ein verallgemeinertes konvexes Optimierungsproblem mit den Nebenbedingungsfunktionen g1(x, y) = x2 + y2 − 5, g2(x, y) = −x, g3(x, y) = −y und h(x, y) = x+2y−4. Die Lagrange-Funktion ist gegeben durch L(λ1, λ2, λ3, μ, x, y) = (x − 3)2 + (y − 2)2 + λ1(x2 + y2 − 5)− λ2x − λ3y + μ(x + 2y − 4). Die Berechnung der beiden ersten partiellen Ableitungen von L bezüglich x und y und anschließendes Nullsetzen dieser Ableitungen liefert zusammen mit der Gleichheitsnebenbedingung und der komplementären Schlupfbedingung (24.102) das Gleichungssystem: ∂L(λ1, λ2, λ3, μ, x, y) ∂x = 2(x − 3)+ 2λ1x − λ2 + μ = 0 (24.108) ∂L(λ1, λ2, λ3, μ, x, y) ∂y = 2(y − 2)+ 2λ1y − λ3 + 2μ = 0 (24.109) x + 2y − 4 = 0 (24.110) λ1(x 2 + y2 − 5) = 0 (24.111) −λ2x = 0 (24.112) −λ3y = 0 (24.113) Für eine zulässige Stelle (x, y) ∈ Z = {(x, y) ∈ R2 : g1(x, y) ≤ 0, g2(x, y) ≤ 0, g3(x, y) ≤ 0, h(x, y) = 0 } 754 Kapitel 2424.6 Optimierung unter Gleichheits- und Ungleichheitsnebenbd. kann immer nur eine der drei Ungleichheitsnebenbedingungen (24.104)–(24.106) bindend sein. Folglich müssen von den insgesamt 23 = 8 Fällen nur drei untersucht werden. Ferner gilt rang ( gradh(x, y)T grad g1(x, y)T ) = rang ( 1 2 2x 2y ) = 2 rang ( gradh(x, y)T grad g2(x, y)T ) = rang ( 1 2 −1 0 ) = 2 rang ( gradh(x, y)T grad g3(x, y)T ) = rang ( 1 2 0 −1 ) = 2 für alle (x, y) ∈ Z . Das heißt, die Qualifikationsbedingung Q3’) ist für alle zulässigen Stellen erfüllt und jede Minimalstelle muss daher die verallgemeinerten KKT- Bedingungen erfüllen. Fall 1: Es sei die Ungleichung (24.104) bindend. Dann sind die beiden anderen Ungleichungen (24.105)– (24.106) nicht bindend, und mit (24.112)–(24.113) folgt λ2 = λ3 = 0. Damit ergibt sich aus (24.108)–(24.111) das folgende Gleichungssystem: 2(x − 3)+ 2λ1x + μ = 0 2(y − 2)+ 2λ1y + 2μ = 0 x + 2y − 4 = 0 x2 + y2 − 5 = 0 Daraus erhält man nach kurzer Umformung die eindeutig bestimmte Lösung x = 2, y = 1, μ = 23 und λ1 = 13 . Fall 2 und 3: Ist entweder die Ungleichung (24.105) oder die Ungleichung (24.106) bindend, dann erhält man jeweils einen Widerspruch zu den verallgemeinerten KKT- Bedingungen. Durch (2, 1) ist folglich die eindeutig bestimmte globale Minimalstelle gegeben und das globale Minimum beträgt f (2, 1) = 2 (vgl. Abbildung 24.20). Zum Abschluss dieses Abschnitts wird ein komplexeres Anwendungsbeispiel aus der (betriebswirtschaftlichen) Produktionstheorie betrachtet. f (x, y)=(x−3)2+(y−2)2 1 2 4 9 16 25 36 l l (x0, y0) Minimum g1(x, y) ≤ 0 h(x, y) = 0 Abb. 24.20: Minimierung der Funktion f (x, y) = (x − 3)2 + (y−2)2 unter den Ungleichheitsnebenbedingungen g1(x, y) = x2+y2−5 ≤ 0, g2(x, y) = −x ≤ 0 und g3(x, y) = −y ≤ 0 sowie der Gleichheitsnebenbedingung h(x, y) = x + 2y − 4 = 0 Beispiel 24.37 (Minimierung der Lager- und Produktionskosten) Betrachtet wird ein Betrieb, der innerhalb von n Zeitperioden ein Produkt A produziert. Von diesem Erzeugnis können bis zu D Mengeneinheiten gelagert werden, und der Bedarf bj an Produkt A in der j -ten Periode (j = 1, . . . , n) ist jeweils bis zum Ende der Periode zu decken. Dazu kann das Produkt aus dem Lager oder aus der laufenden Produktion verwendet werden. Die Lagerkosten von K Geldeinheiten (in €) pro Mengeneinheit richten sich nach dem zu Beginn jeder Periode vorhandenen Lagerbestand. Zu Beginn der ersten Periode seien s0 Mengeneinheiten von Produkt A vorhanden und zum Ende der n-ten Periode sollen noch s1 Mengeneinheiten für Reklamationen oder Nachbestellungen verfügbar sein. Ferner sei vorausgesetzt, dass die Produktionskosten in jeder Periode mindestens proportional mit der produzierten Stückzahl an- 755 Kapitel 24 Nichtlineare Optimierung im Rn wachsen, so dass die Produktionskosten in jeder Periode eine konvexe Funktion der produzierten Menge sind. Als Ziel verfolgt der Betrieb die Minimierung der Summe der Lager- und Produktionskosten für die n Perioden. Im Folgenden sei für j = 1, . . . , n xj die in der j -ten Periode produzierte Menge von Produkt A, bj der in der j -ten Periode zu erfüllende Bedarf an Produkt A, yj der zu Beginn der j -ten Periode vorhandene Lagerbestand und fj (xj ) die Produktionskosten (in €) in der j -ten Periode. Damit erhält man das verallgemeinerte konvexe Optimierungsproblem min n∑ j=1 fj (xj )+K n∑ j=1 yj unter den Nebenbedingungen: yj + xj ≥ bj für j=1, . . . , n yj ≤ D für j=1, . . . , n xj ≥ 0 für j=1, . . . , n yj ≥ 0 für j=1, . . . , n y1= s0 (24.114) yj+1= yj+xj−bj für j=1, . . . , n−1 (24.115) yn+xn−bn= s1 (24.116) Mit Hilfe der Nebenbedingungen (24.114)–(24.116) können die Variablen y1, . . . , yn aus dem Modell eliminiert werden. Es resultiert dann das äquivalente Optimierungsproblem min n∑ j=1 fj (xj )+K ( ns0 + n∑ i=1 (n− i)(xi − bi) ) unter den Nebenbedingungen: s0 + j∑ i=1 (xi − bi) ≤ D für j = 1, . . . , n− 1 s0 + j∑ i=1 (xi − bi) ≥ 0 für j = 1, . . . , n− 1 s0 + n∑ i=1 (xi − bi) = s1 xj ≥ 0 für j = 1, . . . , n Die zugehörige Lagrange-Funktion lautet L(λ,μ, x) = n∑ j=1 fj (xj )+K ( ns0+ n∑ i=1 (n−i)(xi−bi) ) + λ1,1 ( s0 + 1∑ i=1 (xi − bi)−D ) + . . . + λ1,n−1 ( s0 + n−1∑ i=1 (xi − bi)−D ) − λ2,1 ( s0 + 1∑ i=1 (xi − bi) ) − . . . − λ2,n−1 ( s0 + n−1∑ i=1 (xi − bi) ) + μ ( s0 − s1 + n∑ i=1 (xi − bi) ) − λ3,1x1 − . . .− λ3,nxn und die verallgemeinerten KKT-Bedingungen sind gegeben durch: ∂L(λ,μ, x) ∂x1 = ∂f1(x1) ∂x1 + (n− 1)K + n−1∑ i=1 (λ1,i − λ2,i )+ μ− λ3,1= 0 ∂L(λ,μ, x) ∂x2 = ∂f2(x2) ∂x2 + (n− 2)K + n−1∑ i=2 (λ1,i − λ2,i )+ μ− λ3,2= 0 ... ∂L(λ,μ, x) ∂xn−1 = ∂fn−1(xn−1) ∂xn−1 +K + λ1,n−1 − λ2,n−1 + μ− λ3,n−1 = 0 ∂L(λ,μ, x) ∂xn = ∂fn(xn) ∂xn + μ− λ3,n = 0 s0 + 1∑ i=1 (xi − bi)−D ≤ 0 ... 756 Kapitel 2424.6 Optimierung unter Gleichheits- und Ungleichheitsnebenbd. s0 + n−1∑ i=1 (xi − bi)−D ≤ 0 − s0 − 1∑ i=1 (xi − bi) ≤ 0 ... − s0 − n−1∑ i=1 (xi − bi) ≤ 0 − x1,−x2, . . . ,−xn ≤ 0 s0 − s1 + n∑ i=1 (xi − bi) = 0 λ1,1, . . . , λ1,n−1, λ2,1, . . . , λ2,n−1, λ3,1, . . . , λ3,n≥ 0 λ1,1 ( s0 + 1∑ i=1 (xi − bi)−D ) = 0 ... λ1,n−1 ( s0 + n−1∑ i=1 (xi − bi)−D ) = 0 λ2,1 ( s0 + 1∑ i=1 (xi − bi) ) = 0 ... λ2,n−1 ( s0 + n−1∑ i=1 (xi − bi) ) = 0 − λ3,1x1 = 0 ... − λ3,nxn = 0 Da dieses verallgemeinerte konvexe Optimierungsproblem die Qualifikationsbedingung Q1’) erfüllt, sind alle seine globalen Minimalstellen durch die Lösung der verallgemeinerten KKT-Bedingungen gegeben. Gilt zum Beispiel konkret: n = 4, D = 2000, s0 = s1 = K = 500 und f (xj ) = 3000xj + ajx2j für j = 1, 2, 3, 4 sowie j 1 2 3 4 bj 2000 4000 3000 1000 aj 2 1,75 0,75 0 und werden diese Werte in die verallgemeinerten KKT- Bedingungen eingesetzt, dann erhält man nach einigen Rechnungen die Lösung x = ⎛ ⎜⎜ ⎝ 2500 3000 3000 1500 ⎞ ⎟⎟ ⎠ und λ1,1 = λ1,2 = λ1,3 = 0, λ2,1 = 0, λ2,2 = 6500, λ2,3 = 5000, μ = −3000 sowie λ3,1 = λ3,2 = λ3,3 = λ3,4 = 0. 757

Chapter Preview

References

Zusammenfassung

"uneingeschränkt zu empfehlen, [...] insbesondere als Einstiegslektüre im Bachelor-Studium". In: Studium, 2013.

So zentral die Rolle der Mathematik in der Ökonomie ist, so schwer tun sich die Studierenden mit mathematischen Methoden und Konzepten. Umso wichtiger ist es, die Studierenden bei ihrem aktuellen Wissensstand abzuholen und vorsichtig an den Stoff heranzuführen. Diesem Ziel verschreibt sich dieses Lehrbuch. Es führt mit vielen interessanten Beispielen aus der Ökonomie, kurzen Anekdoten und einem modernen mehrfarbigen Design in die zentralen mathematischen Methoden für ein erfolgreiches Wirtschaftsstudium ein, ohne dabei auf mathematische Klarheit sowie die notwendige Formalität und Stringenz zu verzichten. Auch nach dem Studium ist dieses Buch ein wertvoller Begleiter bei der mathematischen Lösung wirtschaftswissenschaftlicher Problemstellungen.

Aus dem Inhalt:

* Mathematische Grundlagen

* Lineare Algebra

* Matrizentheorie

* Folgen und Reihen

* Reellwertige Funktionen in einer und mehreren Variablen

* Differential- und Integralrechnung

* Optimierung mit und ohne Nebenbedingungen

* Numerische Verfahren

Dozenten finden auf der Website zum Buch unter www.vahlen.de zusätzliche Materialien zum Download.

"Indem Sie den Lehrstoff schrittweise aufbereiten und den Leser bei seinem aktuellen Wissenstand abholen, gelingt es ihnen [den Autoren], auch komplexe Zusammenhänge leicht nachvollziehbar zu vermitteln. Geschickt bauen sie immer wieder kurze Anekdoten, historische Ereignisse und überraschende Erkenntnisse in den Text ein". In: Studium, 2013.

Prof. Dr. Michael Merz ist Inhaber des Lehrstuhls für Mathematik und Statistik in den Wirtschaftswissenschaften an der Universität Hamburg. Prof. Dr. Mario V. Wüthrich forscht und lehrt am Department für Mathematik der ETH Zürich.