Minimierung mit Nebenbed. < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:40 Fr 30.01.2009 | | Autor: | Irmchen |
Hallo alle zusammen!
Ich beschäftige mich mit einem Satz aus der Vorlesung, und habe leider ein Paar Verständnisfragen zum Beweis. Ich hoffe, dass mir jemand dabei behilflich sein kann!
Satz :
Sei [mm] f: \mathbb R^n \to \mathbb R [/mm] differenzierbar,
[mm] h_i : \mathbb R^n \to \mathbb R [/mm] stetig differenzierbar für [mm] 1 \le i \le m [/mm] und [mm] C := [mm] \{ x \ | \ h_i (x) = 0 \ fuer \ 1 \le i \le m \}.
[/mm]
Wenn [mm] \overline{x} [/mm] ein lokales Minimum von f auf C ist und
[mm] \nabla h_1( \overline{x} ), ... , \nabla h_m( \overline{x} ) [/mm] linear unabhängig sind, so existiert [mm] \overline{\lambda} = ( \overline{\lambda_1}, ... ,\overline{\lambda_m} } )^{T} \in \mathbb R^m : [/mm]
[mm] \nabla f( \overline{x} ) + \summe_{i=1}^{m} \overline{\lambda_i } \nabla h_i ( \overline{x}) = 0 [/mm]
Die [mm] \lambda_i [/mm] heißen Lagrange - Multiplikatoren.
Beweis :
Für den Beweis wird erstmal der Begriff des Tangentialkegels definiert und eine Bemerkung verwendet:
Definition:
[mm] T(C, \overline{x} ) := \{ d \in \mathbb R^n \ | \ \exists d^k \in \mathbb R^n, \ \exists \alpha_k > 0 \in \mathbb R: \ \overline{x}+ \alpha_k d^k \in C , \ \lim_{k \to \infty } \alpha_k = 0, \ \lim_{k \to \infty} d^k = d \} [/mm]
ist der Tangentialkegel von C in [mm] \overline{x} [/mm].
Bemerkung:
[mm] T(C, \overline{x} ) = \{ d \ | \ \nabla h_i ( \overline{x} )^T d = 0 , \ 1 \le i \le m \} =: \hat T [/mm]
Beweis :
[mm] ( \hat T )^{ \bot } = \{ \summe_{ j = 1 }^{m} \lambda_j \nabla h_j \ | \ \lambda_j \in \mathbb R \} [/mm]
Wie kann ich imit dieses [mm] ( \hat T )^{ \bot } [/mm] vorstellen?
Behauptung: Für [mm] d \in \hat T [/mm] gilt : [mm] \nabla f( \overline{x}) d = 0 [/mm].
Widerspruchsannahme:
Sei o.B.d.A [mm] \nabla f( \overline{x}) d < 0 [/mm].
Da [mm] d \in T (C, \overline{x} ) : \exists d^k , \alpha_k: \overline{x} + \alpha_k d^k \in C, \lim_{k \to \infty } \alpha_k = 0, \ \lim_{k \to \infty} d^k = d \} [/mm]
[mm] \Rightarrow 0> \nabla f ( \overline{x} ) ^T d = \lim_{k \to \infty } \bruch{f( \overline{x} + \alpha_k d^k ) - f ( \overline{x} ) }{ \alpha_k } [/mm]
[mm] \Rightarrow [/mm] Für große k ist [mm] f( \overline{x} + \alpha_k d^k ) < f ( \overline{x} ) [/mm]
[mm] \Rightarrow \ \overline{x} [/mm] ist kein lokales Minimum von f auf C, und dies ist ein WIDERSPRUCH!
Also ist [mm] \nabla f ( \overline{x} ) ^T d = 0 \ \forall d \in \hat T [/mm]
[mm] [mm] \Rightarrow \nabla [/mm] f ( [mm] \overline{x} [/mm] ) [mm] \in [/mm] ( [mm] \hat [/mm] T [mm] )^{\bot} [/mm] Warum gilt diese Folgerung ?
[mm] \Rightarrow \exists \lambda_j \ \Rightarrow [/mm] Behauptung.
Ich sehe leider nicht, warum wir die Menge [mm] ( \hat T )^{\bot} [/mm] benutzen? Und wo verwenden wir die lineare Unabhängigkeit der [mm] \nabla h_i [/mm] ?
Ich hoffe, dass mir jemand behilflich sein kann.
Vielen Dank!
Viele Grüße
Irmchen
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:37 Sa 31.01.2009 | | Autor: | rainerS |
Hallo Irmchen!
> Hallo alle zusammen!
>
> Ich beschäftige mich mit einem Satz aus der Vorlesung, und
> habe leider ein Paar Verständnisfragen zum Beweis. Ich
> hoffe, dass mir jemand dabei behilflich sein kann!
>
> Satz :
>
> Sei [mm]f: \mathbb R^n \to \mathbb R[/mm] differenzierbar,
> [mm]h_i : \mathbb R^n \to \mathbb R[/mm] stetig differenzierbar für [mm]1 \le i \le m[/mm] und [mm]C := \{ x \ | \ h_i (x) = 0 \ fuer \ 1 \le i \le m \}.[/mm]
> Wenn [mm]\overline{x}[/mm] ein lokales Minimum von f auf C ist und
> [mm]\nabla h_1( \overline{x} ), ... , \nabla h_m( \overline{x} )[/mm] linear unabhängig sind, so existiert[mm]\overline{\lambda} = ( \overline{\lambda_1}, ... ,\overline{\lambda_m} } )^{T} \in \mathbb R^m :[/mm]
> [mm]\nabla f( \overline{x} ) + \summe_{i=1}^{m} \overline{\lambda_i } \nabla h_i ( \overline{x}) = 0[/mm]
>
> Die [mm]\lambda_i[/mm] heißen Lagrange - Multiplikatoren.
>
> Beweis :
>
> Für den Beweis wird erstmal der Begriff des Tangentialkegels definiert und eine Bemerkung verwendet:
>
> Definition:
>
> [mm]T(C, \overline{x} ) := \{ d \in \mathbb R^n \ | \ \exists d^k \in \mathbb R^n, \ \exists \alpha_k > 0 \in \mathbb R: \ \overline{x}+ \alpha_k d^k \in C , \ \lim_{k \to \infty } \alpha_k = 0, \ \lim_{k \to \infty} d^k = d \}[/mm]
>
> ist der Tangentialkegel von C in [mm]\overline{x} [/mm].
>
> Bemerkung:
>
> [mm]T(C, \overline{x} ) = \{ d \ | \ \nabla h_i ( \overline{x} )^T d = 0 , \ 1 \le i \le m \} =: \hat T[/mm]
>
>
> Beweis :
>
> [mm]( \hat T )^{ \bot } = \{ \summe_{ j = 1 }^{m} \lambda_j \nabla h_j \ | \ \lambda_j \in \mathbb R \}[/mm]
>
> Wie kann ich imit dieses [mm]( \hat T )^{ \bot }[/mm] vorstellen?
Dsa ist sogar sehr anschaulich:
Für jede der Nebenbedingungen [mm] $h_j(x)=0$ [/mm] ist [mm] $\nabla h_j [/mm] $ eine Richtung sozusagen senkrecht zur Nebenbedingung, das heisst, eine Verschiebung in Richtung von [mm] $\nabla h_j [/mm] $ verletzt diese Nebenbedingung. Alle m verschiedenen [mm] $\nabla h_j [/mm] $ zusammen ergeben also einen Untervektorraum, der sozusagen am Punkt [mm] $\overline{x}$ [/mm] senkrecht auf der Fläche C steht.
Beispiel: Nimm im [mm] $\IR^3$ [/mm] die beiden Nebenbedingungen [mm] $h_1(x,y,z) [/mm] = [mm] x^2+y^2+z^2-1$ [/mm] und $h2(x,y,z) = z$. Die erste definiert die Oberfläche der Einheitskugel, die zweite die xy-Ebene. Zusammen definieren sie den Einheitskreis in der xy-Ebene. Die beiden Gradienten sind
[mm] \nabla h_1 = \vektor{2x\\2y\\2z} [/mm] und [mm] \nabla h_2 = \vektor{0\\0\\1} [/mm].
Der erste der beiden steht immer senkrecht auf der Oberfläche der Einheitskugel, der zweite auf der xy-Ebene.
> Behauptung: Für [mm]d \in \hat T[/mm] gilt : [mm]\nabla f( \overline{x}) d = 0 [/mm].
>
> Widerspruchsannahme:
> Sei o.B.d.A [mm]\nabla f( \overline{x}) d < 0 [/mm].
> Da [mm]d \in T (C, \overline{x} ) : \exists d^k , \alpha_k: \overline{x} + \alpha_k d^k \in C, \lim_{k \to \infty } \alpha_k = 0, \ \lim_{k \to \infty} d^k = d \}[/mm]
>
> [mm]\Rightarrow 0> \nabla f ( \overline{x} ) ^T d = \lim_{k \to \infty } \bruch{f( \overline{x} + \alpha_k d^k ) - f ( \overline{x} ) }{ \alpha_k }[/mm]
>
> [mm]\Rightarrow[/mm] Für große k ist [mm]f( \overline{x} + \alpha_k d^k ) < f ( \overline{x} )[/mm]
>
> [mm]\Rightarrow \ \overline{x}[/mm] ist kein lokales Minimum von f auf C, und dies ist ein WIDERSPRUCH!
>
> Also ist [mm]\nabla f ( \overline{x} ) ^T d = 0 \ \forall d \in \hat T[/mm]
[mm]\Rightarrow \nabla f ( \overline{x} ) \in ( \hat T )^{\bot}[/mm] Warum gilt diese Folgerung ?
[mm]\nabla f ( \overline{x} ) ^T d = 0 \ \forall d \in \hat T[/mm] bedeutet doch, dass [mm] $\nabla [/mm] f ( [mm] \overline{x} [/mm] )$ orthogonal zu jedem [mm] $d\in \hat{T}$ [/mm] ist. das ist aber gerade die Definition des orthogonalen Komplements $( [mm] \hat{T} )^{\bot}$.
[/mm]
> [mm]\Rightarrow \exists \lambda_j \ \Rightarrow[/mm] Behauptung.
>
> Ich sehe leider nicht, warum wir die Menge [mm]( \hat T )^{\bot}[/mm] benutzen? Und wo verwenden wir die lineare Unabhängigkeit der [mm]\nabla h_i[/mm] ?
Wenn die [mm]\nabla h_i[/mm] in einem Punkt [mm] $\overline{x}$ [/mm] linear abhängig sind, dann sind die [mm] $\lambda_j$ [/mm] nicht eindeutig bestimmt.
Ich glaube, es gibt auch dann Probleme, wenn die [mm]\nabla h_i[/mm] in einem Punkt [mm] $\overline{x}$ [/mm] linear abhängig sind, in einer Umgebung davon aber linear unabhängig. Nur fällt mir im Moment kein Beispiel dafür ein.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:41 So 01.02.2009 | | Autor: | Irmchen |
Hallo!
Vielen lieben Dank für die Antwort!
Jetzt habe ich meine Frage geklärt, aber leider verstehe ich jetzt nicht, warum wir den Satz bewiesen haben, wenn wir die Behauptung:
Für [mm]d \in \hat T[/mm] gilt : [mm]\nabla f( \overline{x}) d = 0 [/mm].
gezeigt haben???
Vielen Dank!
Viele Grüße
Irmchen
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:23 So 01.02.2009 | | Autor: | rainerS |
Hallo Irmchen!
> Hallo!
>
> Vielen lieben Dank für die Antwort!
> Jetzt habe ich meine Frage geklärt, aber leider verstehe
> ich jetzt nicht, warum wir den Satz bewiesen haben, wenn
> wir die Behauptung:
>
>
> Für [mm]d \in \hat T[/mm] gilt : [mm]\nabla f( \overline{x}) d = 0 [/mm].
>
> gezeigt haben???
Damit ist doch [mm] $\nabla [/mm] f( [mm] \overline{x})\in [/mm] ( [mm] \hat [/mm] T [mm] )^{ \bot }$, [/mm] und da $ ( [mm] \hat [/mm] T [mm] )^{ \bot } [/mm] = [mm] \{ \summe_{ j = 1 }^{m} \lambda_j \nabla h_j \ | \ \lambda_j \in \mathbb R \} [/mm] $ die lineare Hülle der [mm] $\nabla h_j$ [/mm] ist, ist [mm] $\nabla [/mm] f( [mm] \overline{x})$ [/mm] eine Linearkombination der [mm] $\nabla h_j$.
[/mm]
Und damit gibt es [mm] $\overline{\lambda_j}$, [/mm] sodass
$ [mm] \nabla [/mm] f( [mm] \overline{x} [/mm] ) + [mm] \summe_{i=1}^{m} \overline{\lambda_i } \nabla h_i [/mm] ( [mm] \overline{x}) [/mm] = 0 $
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:45 So 01.02.2009 | | Autor: | Irmchen |
Oh super  ! Jetzt habe ich es endlich komplett verstanden!
Vielen herzlichen Dank!
Viele Grüße
Irmchen
|
|
|
|
