| |
| Autor |
 Lagrangian dual berechnen |
|
SophiaB
Junior 
Dabei seit: 13.02.2022
Mitteilungen: 7
 |  Themenstart: 2022-02-13
|
Guten Morgen,
ich beschäftige mich gerade etwas mit der Optimierungstheorie, speziell dem Lagrangian-Verfahren. Nun hänge ich aber an einer Übungsaufgabe fest und hoffe ihr könnt mir dort etwas helfen.
Gegeben ist das folgende LP mit $x,y,z \in \mathbb{R}$:
$\begin{equation*}
\begin{array}{ll@{}ll}
{\underset{x,y,z}{minimize}} & x+y-z &\\
\text{subject to}& x-y-3z=1 \\
& x,y,z \geq 0
\end{array}
\end{equation*}$
und ich soll davon die Lagrangian Dual Funktion aufstellen/berechnen.
Die Lagrangian Funktion selbst lautet:
$\begin{equation*}
L(x,y,z,\lambda_1,\lambda_2, \lambda_3, \kappa) = (x+y-z) - \lambda_1x -\lambda_2y - \lambda_3z + \kappa(x-y-3z-1)
\end{equation*}$
Die einzelnen Ableitungen für die KKT Bedingungen lauten:
$\begin{equation*}
\begin{array}{ll@{}ll}
&\nabla_x L(x,y,z,\lambda_1,\lambda_2, \lambda_3, \kappa) = 1 - \lambda_1 + \kappa = 0\\
&\nabla_y L(x,y,z,\lambda_1,\lambda_2, \lambda_3, \kappa) = 1 - \lambda_2 - \kappa = 0\\
&\nabla_z L(x,y,z,\lambda_1,\lambda_2, \lambda_3, \kappa) = -1 - \lambda_3 - 3 \kappa = 0\\
&\\
&\nabla_{\lambda_1} L(x,y,z,\lambda_1,\lambda_2, \lambda_3, \kappa) = -x \leq 0\\
&\nabla_{\lambda_2} L(x,y,z,\lambda_1,\lambda_2, \lambda_3, \kappa) = -y \leq 0\\
&\nabla_{\lambda_3} L(x,y,z,\lambda_1,\lambda_2, \lambda_3, \kappa) = -z \leq 0\\
\end{array}
\end{equation*}$
Aber nun kommt das Problem. Normalerweise würde ich irgendwas in Abhängigkeit von $x,y,z$ aus der erst KKT Bedingung (ersten 3 Ableitung(siehe oben)) herausbekommen und dies in die Lagrangian Funktion einsetzen, aber hier geht es nicht. Wie komme ich hier weiter, oder habe ich mich bis jetzt vlt schon vermacht?
Bedanke mich im Voraus für die Hilfe.
Viele Grüße
Sophia
|
 Profil
|
Bozzo
Senior 
Dabei seit: 11.04.2011
Mitteilungen: 2289
Wohnort: Franken
 | Beitrag No.1, eingetragen 2022-02-15
|
Fuer die Ableitungen nach den Lambdas gilt nur "<= 0" und nicht "== 0". Ausserdem fehlen dir noch die Komplementaritaetsbedingungen "λ1 x == 0" usw. und der Vollstandigkeithalber auch noch "λi >= 0".
Du kannst z. B. deine ersten drei Gleichungen nach den λi aufloesen und diese in die Komplementaritaetsbedingungen einsetzen. Am Ende kommt nur ein Loesungskandidat (KKT-Punkt) heraus, der auch die Nebenbedingungen erfuellt.
|
Profil
|
SophiaB
Junior
Dabei seit: 13.02.2022
Mitteilungen: 7
| Beitrag No.2, vom Themenstarter, eingetragen 2022-02-19
|
Hallo Bozzo,
ich bedanke mich für deine Antwort und entschuldige mich für die späte Antwort.
Wenn ich nun nach $\lambda$ umstelle
$\begin{equation*}
\begin{array}{ll@{}ll}
&\lambda_1 = 1+\kappa \\
&\lambda_2 = 1-\kappa \\
&\lambda_3 = -(1+\kappa)
\end{array}
\end{equation*}$
und dies in die Komplementaritätsbedingungen
$\begin{equation*}
\begin{array}{ll@{}ll}
&\lambda_1(-x) = 0
&\lambda_2(-y) = 0
&\lambda_3(-z) = 0
\end{array}
\end{equation*}$
einsetze kommt folgendes raus:
$\begin{equation*}
\begin{array}{ll@{}ll}
&(1+\kappa)(-x) = 0 \\
&(1-\kappa)(-y) = 0 \\
&(-(1+\kappa))(-z) = 0
\end{array}
\end{equation*}$
dann bekomme ich für $x,y,z = 0$ raus, was nicht sein kann, denn $x=1, y=0,z=0$ sollte die korrekte Lösung sein.
|
Profil
|
Bozzo
Senior
Dabei seit: 11.04.2011
Mitteilungen: 2289
Wohnort: Franken
| Beitrag No.3, eingetragen 2022-02-19
|
Dein Ergebnis für λ3 stimmt noch nicht ganz. x=y=z=0 erfüllt zwar die Komplementaritätsbedingungen, verletzt aber die Nebenbedingung. Du scheinst die Komplementaritätsbedingungen für alle κ erfüllen zu wollen, aber was ist, wenn sie nur für ein bestimmtes κ erfüllt wären? Was würde aus den Komplementaritätsbedingungen und der Nebenbedingung z. B. für κ=1 über x, y und z folgen?
|
Profil
|
| SophiaB hat die Antworten auf ihre/seine Frage gesehen. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
