Optimierung, Lagrange Multiplikator

21.04.2012, 09:48

Verndank

Optimierung, Lagrange Multiplikator

Guten Morgen.

in dem angehängten Bild habe ich eine Aufgabe aus dem Bereich Optimierung gestellt bekommen, die mit Lagrange Multiplier gelöst werden soll.

Ich habe noch mal in meine Unterlagen zu dem Thema geguckt, finde dort aber nur Beispiel oder Erklärungen in denen ausschließlich lambda verwendet wird. Das theta sehe ich zum ersten mal an der Stelle, das irritiert mich.
Kann mir jemand erklären was hier zu machen ist, bzw. welche Funktion das theta einnimmt?

22.04.2012, 00:04

Kasen75

Auf diesen Beitrag antworten »

RE: Optimierung, Lagrange Multiplikator
Gute Nacht,

du hast ja zwei Nebenbedingungen. Also brauchst du auch zwei Lagrange-Multiplikatoren.

Die Lagrange-Funktion sähe dann so aus:

$\begin{eqnarray*} \underset{\text{p}}{max} \ \ L(p, \lambda, \theta)=\sum\limits_{i=1}^n p_i \cdot log \ p_i + \lambda(c - \sum\limits_{i=1}^n p_i \cdot i^2) + \theta(1 - \sum\limits_{i=1}^n p_i) \end{eqnarray*}$

Dann nach $\begin{eqnarray*} p, \ \lambda, \ und \ \theta \end{eqnarray*}$ ableiten.

Prinzipiell könnte man die beiden Lagrange-Multipliktoren $\begin{eqnarray*} \lambda_1 \ und \ \lambda_2 \end{eqnarray*}$ benennen; oder auch irgendwie anders.

Mit freundlichen Grüßen

22.04.2012, 10:46

Verndank

Auf diesen Beitrag antworten »

Ah, ok.

Wie handhabe ich den die Summen beim Ableiten? Kann ich die irgendwie raus substiuieren?

22.04.2012, 14:45

Kasen75

Auf diesen Beitrag antworten »

RE: Optimierung, Lagrange Multiplikator
Hallo,

wäre gut wenn du mal deine Ableitungen posten würdest. Dann kann man sicher schon einiges sehen, wo man etwas vereinfachen kann.

Mit freundlichen Grüßen.

22.04.2012, 18:56

Verndank

Auf diesen Beitrag antworten »

$\begin{eqnarray*} l_p = log(p) - \theta - \lambda*i^2 + 1 \end{eqnarray*}$
$\begin{eqnarray*} l_{\lambda} = c - i^2*p \end{eqnarray*}$
$\begin{eqnarray*} l_{\theta} = 1-p \end{eqnarray*}$

Ich hab versucht das Summenzeichen durch Variable p zu ersetzen, weil alle p_i ja p ergeben, geht das?

22.04.2012, 20:32

Kasen75

Auf diesen Beitrag antworten »

RE: Optimierung, Lagrange Multiplikator

Zitat:

weil alle p_i ja p ergeben, geht das?

Die Summe der $\begin{eqnarray*} p_i \end{eqnarray*}$ ergibt 1. Damit kann man sicher was machen. Aber die Summenzeichen einfach weglassen geht nicht. Da steht bei Dir:

Zitat:

$\begin{eqnarray*} l_{\theta} = 1-p \end{eqnarray*}$

Und da man die Nebenbedingung Null setzt ergibt sich:

$\begin{eqnarray*} l_{\theta} = 1-p =0 \end{eqnarray*}$

Daraus würde sich ergeben, dass p = 1 ist. Das ist insoweit richtig, wenn man annimmt, dass $\begin{eqnarray*} P = \sum\limits_{k=1}^n pi \end{eqnarray*}$ ist. Aber daraus ergibt sich eine weitere Nebenbedingung. Also kein Informationsgewinn.

Was man aber machen kann ist folgendes: Dass man bei n =4 für p_1 = 1 - p_2 - p_3 - p_4 schreiben kann.

Auch wenn man mit dem Summenzeichen die part. Ableitungen aufschreibt gibt es noch Vereinfachungsmöglichkeiten. Deswegen würde ich die Ableitungen mal mit Summenzeichen aufschreiben. Dann kann man weitersehen.

Mit freundlichen

23.04.2012, 08:58

Verndank

Auf diesen Beitrag antworten »

Also ich hab jetzt meine substituierten p-werte durch das summenzeichen ersetzt, aber ich so richtig helfen tut mir das nicht.
$\begin{eqnarray*} l_p = \sum\limits_{i=1}^n p_i \cdot log(p) - \theta - \lambda*i^2 + 1 \end{eqnarray*}$
$\begin{eqnarray*} l_{\lambda} = c - i^2 \cdot \sum\limits_{i=1}^n p_i \end{eqnarray*}$
$\begin{eqnarray*} l_{\theta} = 1-\sum\limits_{i=1}^n p_i \end{eqnarray*}$

23.04.2012, 15:07

Kasen75

Auf diesen Beitrag antworten »

Hallo,

ich bin mit deiner Ableitung nach p nicht einverstanden. So ergibt z.B.

die Ableitung des Ausdrucks $\begin{eqnarray*} \sum\limits_{i=1}^n p_i \cdot log \ p_i: \end{eqnarray*}$

$\begin{eqnarray*} \sum\limits_{i=1}^n p_i \cdot \frac{1}{p_i}+1 \cdot log (p_i) \end{eqnarray*}$

Das kann man noch zusammenfassen.

Und was ergibt den abgeleitet der Ausdruck $\begin{eqnarray*} \sum\limits_{i=1}^n p_i<br /> \end{eqnarray*}$ nach pi?

Zitat:

$\begin{eqnarray*} l_{\lambda} = c - i^2 \cdot \sum\limits_{i=1}^n p_i \end{eqnarray*}$

Bei der Ableitung nach $\begin{eqnarray*} \lambda \end{eqnarray*}$ hast du das $\begin{eqnarray*} i^2 \end{eqnarray*}$ einfach vor die Summe gezogen. Das geht nicht, da $\begin{eqnarray*} i^2 \end{eqnarray*}$ keine Konstante ist.

Des Weiteren, solltest du noch alle Ableitungen gleich 0 setzen.

Mit freundlichen Grüßen.

24.04.2012, 09:02

Verndank

Auf diesen Beitrag antworten »

Zitat:

Original von Kasen75

Und was ergibt den abgeleitet der Ausdruck $\begin{eqnarray*} \sum\limits_{i=1}^n p_i<br /> \end{eqnarray*}$ nach pi?

Wenn ich jedes p der summe einzeln ableite, ist doch jedes p_i = 1, und ich addiere n*1?

26.04.2012, 07:35

Kasen75

Auf diesen Beitrag antworten »

Hallo,

ich schreib jetzt mal die Ableitung auf:

$\begin{eqnarray*} \frac{\partial L}{\partial p_i}=log p_i + 1 - \lambda \cdot i^2 - \theta \end{eqnarray*}$

Die Summenzeichen fallen weg, da nur nach einem bestimmten pi abgeleitet wird.

Bei den Ableitungen nach den Lagrangemultiplikatoren bleiben sie aber erhalten.

$\begin{eqnarray*} \frac{\partial L}{\partial \lambda}= (c - \sum\limits_{i=1}^n p_i \cdot i^2) \end{eqnarray*}$
$\begin{eqnarray*} \frac{\partial L}{\partial \theta}=(1 - \sum\limits_{i=1}^n p_i) \end{eqnarray*}$

Um so eine Funktion mit Nebenbedingungen zu maximieren kann man z.B. die Methode von Karush-Kuhn-Tucker (KKT) verwenden. Nur wenn es dir irgendwie für dein Problem hilft solltest du dich näher mit dem Verfahren beschäftigen, da es ziemlich aufwendig ist. Es ist auch ganz gut auf dieser Seite (Link) beschrieben.

Ich habe mal beispielhaft für i=2 (p1,p2) mal die Bedingugen aufgeschrieben. Weiter unten sind die 4 Fälle aufgeschrieben, die man untersuchen muss. Man untersucht erst den ersten Fall und schaut, ob es einen Widerspruch in den KKT-Bedingungen sich ergeben oder schon gleich eine Lösung. Keine Lösung, dann zum 2. Fall. Um es konkret rechnen zu können braucht man z.B. einen konreten Wert für den Parameter c.

$\begin{eqnarray*} \frac{\partial L}{\partial p_1} \geq 0 \end{eqnarray*}$

$\begin{eqnarray*} \frac{\partial L}{\partial p_2} \geq 0 \end{eqnarray*}$

Weitere Kriterien:

$\begin{eqnarray*} \frac{\partial L}{\partial \theta} \leq 0 \end{eqnarray*}$

$\begin{eqnarray*} \frac{\partial L}{\partial \lambda} \leq 0 \end{eqnarray*}$

$\begin{eqnarray*} p_1\cdot \frac{\partial L}{\partial p_1} = 0 \end{eqnarray*}$

$\begin{eqnarray*} p_2 \cdot \frac{\partial L}{\partial p_2} = 0 \end{eqnarray*}$

$\begin{eqnarray*} \theta \cdot \frac{\partial L}{\partial \theta} = 0 \end{eqnarray*}$

$\begin{eqnarray*} \lambda \cdot \frac{\partial L}{\partial \lambda} = 0 \end{eqnarray*}$

Und es muss gelten: $\begin{eqnarray*} \theta, \lambda, p_1, p_2, \geq 0 \end{eqnarray*}$

Jetzt muss man folgende Fälle untersuchen:

1. Fall: $\begin{eqnarray*} \theta \end{eqnarray*}$ , $\begin{eqnarray*} \lambda \end{eqnarray*}$ $\begin{eqnarray*} \geq \end{eqnarray*}$ 0

2. Fall: $\begin{eqnarray*} \theta \end{eqnarray*}$ , $\begin{eqnarray*} \lambda \end{eqnarray*}$ = 0

3. Fall: $\begin{eqnarray*} \theta \end{eqnarray*}$ =0, $\begin{eqnarray*} \lambda \end{eqnarray*}$ $\begin{eqnarray*} \geq \end{eqnarray*}$ 0

4. Fall: $\begin{eqnarray*} \theta \end{eqnarray*}$ $\begin{eqnarray*} \geq \end{eqnarray*}$ 0, $\begin{eqnarray*} \lambda \end{eqnarray*}$ = 0

Zitat:

Wenn ich jedes p der summe einzeln ableite, ist doch jedes p_i = 1

Das ist richtig.

26.04.2012, 10:36

Mystic

Auf diesen Beitrag antworten »

@Kasen75

Wenn ich mir hier einen schnellen Einwurf erlauben darf: Ja, so würde das der "Profi" machen, aber ich fürchte, wenn der Fragesteller offensichtlich schon bei der Bildung der noch einfachen Ableitungen und der Manipulation der Summen erhebliche Probleme hat, sind ihm die korrekte Anwendung der KKT-Bedingungen "um Welten" zu hoch... geschockt

Neue Frage »

Antworten »

Optimierung, Lagrange Multiplikator

Verwandte Themen