Optimierung unter Nebenbedingung, Definitheit

06.07.2006, 11:22	jay-jay	Auf diesen Beitrag antworten »
Optimierung unter Nebenbedingung, Definitheit Hallo zusammen, ich bräuchte eure Hilfe bei einer Herleitung, und zwar ist mir nicht klar, warum bei der Bedingung 2. Ordnung die Hesse-Matrix definit sein muss für alle h für die grad g(x) h=0. g(x) ist hier die NB. Danke für eure Hilfe
06.07.2006, 13:50	Abakus	Auf diesen Beitrag antworten »
RE: Optimierung unter Nebenbedingung, Definitheit Was sind denn g und h ? Und um welches Problem geht es (was soll optimiert werden) ? Grüße Abakus
06.07.2006, 14:19	jay-jay	Auf diesen Beitrag antworten »
Es geht um optimierung von f(x) unter der NB g(x)=0 Lagrange-Verfahren ... Die hinreichende Bedingung zweiter Ordnung für ein globales beschränktes Optimum ist doch dann, dass die Hesse-Matrix, also die zweiten Ableitungen der Lagrange-Funktion nach dem Vektor x positiv bzw negativ definit ist für bestimmte Vektoren h Also: $\begin{eqnarray} D^2L(x)=\begin{pmatrix} d^2L/dx_1^2 & d^2L/dx_1x_2 \\ d^2L/dx_1x_2 & d^2L / dx_2 ^2 \end{pmatrix} \end{eqnarray}$ ist die Hesse-Matrix und $\begin{eqnarray} h^TD^2L(x) h < (>) 0 \end{eqnarray}$ für $\begin{eqnarray} grad [g(x)]h=0 \end{eqnarray}$ , also dem Produkt von dem Gradienten von g(x) und dem Vektor h. Darauf bezieht sich jetzt meine Frage, warum muss die Hesse-Matrix nur für diese h definit sein und wie kann ich das zeigen?
06.07.2006, 22:04	Abakus	Auf diesen Beitrag antworten »
Du kannst die zweite Ableitung der Lagrange-Funktion ähnlich wie hier angegeben ausrechnen (die Ableitung von y musst du nach der Formel über implizite Funktionen ersetzen). Dann kommst du nach längerer Rechnung auf folgende Darstellung für die 2-te Ableitung (y ist hier implizit von x aufgrund der Nebenbedingung abhängig): $\begin{eqnarray} \hat{f}_{xx}(x, y) = \begin{pmatrix} g'_1(x, y) \\ g'_2(x, y) \end{pmatrix} \cdot \begin{pmatrix} \begin{vmatrix} g'_1(x, y) & L''_{12}(x, y) \\ g'_2(x, y) & L''_{22}(x, y) \end{vmatrix} \\ \ & \ \\ - \begin{vmatrix} g'_1(x, y) & L''_{11}(x, y) \\ g'_2(x, y) & L''_{21}(x, y) \end{vmatrix} \end{pmatrix} \end{eqnarray}$ Entscheidend für die Konvexität oder Konkavität ist nun lediglich, ob dieser Ausdruck positiv oder negativ ist. Vektoren, die linear von $\begin{eqnarray} grad~ g \end{eqnarray}$ abhängig sind (hier jeweils die 2-te Spalte der beiden Determinanten betrachtet), machen die beiden Determinanten jeweils zu 0. Entscheidend ist für den Wert dieser beiden Determinanten demnach nur die zu $\begin{eqnarray} grad~ g \end{eqnarray}$ orthogonale Komponente (Determinantenrechenregeln), woraus letztlich die von dir angegebene Bedingung $\begin{eqnarray} h \cdot grad~ g = 0 \end{eqnarray}$ resultiert. Grüße Abakus PS: es mag durchaus sein, dass du eine einfachere Begründung als diese hier findest. EDIT: 1 Gradient zuviel korrigiert
08.07.2006, 13:19	jay-jay	Auf diesen Beitrag antworten »
Ich kann dir bis hierhin folgen: $\begin{eqnarray} L''_{xx}=\frac{1}{(g'_x)^2} \left[L''_{xx}(g'_y)^2-2L''_{xy}g'_xg'_y +L''_{yy}(g'_x)^2\right] \end{eqnarray}$ und daraus dann den Vektor $\begin{eqnarray} \begin{pmatrix} g'_y \begin{vmatrix} L''_{xx} & g'_x \\ L'_xy & g'_y \end{vmatrix} \\ g'_x \begin{vmatrix} L''_{yy} & g'_y \\ L'_xy & g'_x \end{vmatrix} \end{pmatrix} \end{eqnarray}$ Woher nimmst du denn den Gradienten davor? Und außerdem verstehe ich deine Argumentation nicht, warum grad g deshalb orthogonal zu h sein muss (klar damit grad g * h =0, aber wieso ist dann der Wert der Matrix bestimmt?
08.07.2006, 20:04	Abakus	Auf diesen Beitrag antworten »
Mal langsam das Ganze und von Vorne (ich brauche das etwas ausführlicher): zu lösen: $\begin{eqnarray} Opt.~ \stackrel{!}{=}~ f(x, y),~\ \ udN.:~ g(x, y)~ = 0 \end{eqnarray}$ g definiert nun unter geeigneten Umständen implizit eine Funktion y(x), etwa dann, wenn $\begin{eqnarray} g_1(x, y) \ne 0 \end{eqnarray}$ . Insbesondere lässt sich - nach dem Satz über implizite Funktionen - die Ableitung von y nach x wie folgt schreiben: $\begin{eqnarray} y'(x) = - \frac{g_1(x, y)}{g_2(x, y)} \end{eqnarray}$ Demzufolge ist es möglich f nur als Funktion von x zu betrachten, also $\begin{eqnarray} M(x) := f(x, y(x)) \end{eqnarray}$ und stattdessen M zu betrachten. Nun ist: $\begin{eqnarray} M'(x) = f_1(x, y) - f_2(x, y) \cdot \frac{g_1(x, y)}{g_2(x, y)} \end{eqnarray}$ Dies lässt sich nochmals nach x differenzieren, zur Abkürzung lasse ich hier die Argumente jeweils weg: $\begin{eqnarray} M''(x) = f_{11} + f_{12} \cdot (- \frac{g_1}{g_2}) -(f_{21} + f_{22} \cdot (- \frac{g_1}{g_2}) ) \cdot \frac{g_1}{g_2} - f_2 \cdot \frac{g_2 \cdot (g_{11} + g_{12} \cdot (- \frac{g_1}{g_2}) ) - g_1 \cdot (g_{21} + g_{22} \cdot (- \frac{g_1}{g_2})) }{(g_2)^2} \end{eqnarray}$ Dieser Ausdruck wird nun vereinfacht: zunächst werden nur die stationären Punkte der Lagrange-Funktion betrachtet (um die geht es uns ja), dafür gilt: $\begin{eqnarray} f_1 = \lambda g_1,~f_2 = \lambda g_2 \end{eqnarray}$ . Ferner gilt nach dem Satz v. Schwarz: $\begin{eqnarray} f_{12} = f_{21},~g_{21} = g_{12} \end{eqnarray}$ . Dies eingesetzt und geeignet geklammert ergibt: $\begin{eqnarray} M''(x) = \frac{1}{g_2^2} \cdot (g_2^2 \cdot (f_{11} - \lambda g_{11}) - 2g_1g_2 \cdot(f_{12} - \lambda g_{12}) + g_1^2 \cdot (f_{22} - \lambda g_{22}) ) \end{eqnarray}$ $\begin{eqnarray} = \frac{1}{g_2^2} \cdot (g_2^2 \cdot L_{11} - 2g_1g_2 \cdot L_{12} + g_1^2 \cdot L_{22}) \end{eqnarray}$ $\begin{eqnarray} = \frac{1}{g_2^2} \cdot \begin{pmatrix} g_1 \\ g_2 \end{pmatrix} \cdot \begin{pmatrix} \begin{vmatrix} g_1 & L_{12} \\ g_2 & L_{22}\end{vmatrix} \\ \ & \ \\ - \begin{vmatrix} g_1 & L_{11} \\ g_2 & L_{21} \end{vmatrix} \end{pmatrix} = - \frac{1}{g_2^2} \cdot \begin{vmatrix} 0 & g_1 & g_2 \\ g_1 & L_{11} & L_{12} \\ g_2 & L_{12} & L_{22} \end{vmatrix} \end{eqnarray}$ Dies hast du im Prinzip soweit auch (ich hatte oben einen Gradienten zuviel und es jetzt richtig editiert). Wenn dies nun < 0 ist, ist f ( unter Berücksichtigung der Nebenbedingung betrachtet) konkav und hat ein Maximum, bei > 0 ist f konvex und es liegt ein Minimum vor. Ebenso sehen wir, dass der Term deutlich vom Gradienten von g abhängt. Für die Prüfung auf diese Eigenschaft (konvex, konkav) reicht es nun aus, nur mit zu $\begin{eqnarray} \begin{pmatrix} g_1 \\ g_2 \end{pmatrix} \end{eqnarray}$ orthogonalen Vektoren zu prüfen. Dies liegt an folgendem: Sei $\begin{eqnarray} \begin{pmatrix} h_1 \\ h_2 \end{pmatrix} = \mu_1 \cdot \begin{pmatrix} g_1 \\ g_2 \end{pmatrix} + \mu_2 \cdot \begin{pmatrix} i_1 \\ i_2 \end{pmatrix} \end{eqnarray}$ und die Vektoren $\begin{eqnarray} g \end{eqnarray}$ und $\begin{eqnarray} i \end{eqnarray}$ seien orthogonal. Dann gilt: $\begin{eqnarray} \begin{vmatrix} g_1 & h_1 \\ g_2 & h_2\end{vmatrix} = \begin{vmatrix} g_1 & \mu_1 \cdot (g_1 + i_1) \\ g_2 & \mu_2 \cdot (g_2 + i_2)\end{vmatrix} = \begin{vmatrix} g_1 & \mu_1 g_1 \\ g_2 & \mu_2 g_2 \end{vmatrix} + \begin{vmatrix} g_1 & \mu_1 i_1 \\ g_2 & \mu_2 i_2\end{vmatrix} = 0 + \mu \cdot \begin{vmatrix} g_1 & i_1 \\ g_2 & i_2\end{vmatrix} \end{eqnarray}$ Es reicht demnach aus, nur die orthogonale Komponente $\begin{eqnarray} i \end{eqnarray}$ zu betrachten. Genau das wird in deinem Satz gemacht. Grüße Abakus EDIT 1+2: Latex
Anzeige

09.07.2006, 15:13	jay-jay	Auf diesen Beitrag antworten »
Danke erstmal bis hierhin. Verstehe ich das so richtig: M''(x) lässt sich doch ausdrücken durch: $\begin{eqnarray} \left( g_2 ; -g_1 \right) \begin{pmatrix} L_{11} & L_{12} \\ L_{12} & L_{22} \end{pmatrix} \begin{pmatrix} g_2 \\ -g_1\end{pmatrix} \end{eqnarray}$ Der Satz um den es geht sagt jetzt: $\begin{eqnarray} h^T\begin{pmatrix} L_{11} & L_{12} \\ L_{12} & L_{22} \end{pmatrix} h < (>) 0 \end{eqnarray}$ für alle Vektoren h, die $\begin{eqnarray} grad g(x) h=0 \end{eqnarray}$ erfüllen, weil $\begin{eqnarray} grad g(x) * (g_2 ; -g_1) =0 \end{eqnarray}$ $\begin{eqnarray} h=\lambda \begin{pmatrix} g_2 \\ -g_1 \end{pmatrix} \end{eqnarray*}$
09.07.2006, 18:47	Abakus	Auf diesen Beitrag antworten »
So ist es, wobei M''(x) noch einen zusätzlichen Vorfaktor mit bekanntem Vorzeichen besitzt. Grüße Abakus EDIT: Text

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »