konvexe Hülle < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:03 So 02.05.2010 | | Autor: | oeli1985 |
| Aufgabe | sei S [mm] \subseteq \IR^{n} [/mm] beliebig und nichtleer
S ist konvex [mm] \gdw [/mm] S = convS |
Hallo zusammen,
ich bereite mich gerade auf meine mündliche Examensprüfung u.a. in Operations Research vor.
Bzgl. obiger Aufgabe bereitet mir die Richtung "<=" keine Probleme. Bzgl. der Richtung "=>" schaffe ich es auch zu zeigen, dass S [mm] \subset [/mm] convS, jedoch fehlt mir der Durchblick bzgl. convS [mm] \subset [/mm] S.
Folglich komme ich nur bis zu folgendem Punkt:
z [mm] \in [/mm] convS [mm] \rightarrow z=\summe_{i=1}^{k} \lambda_{i} s_{i}, [/mm] wobei [mm] \lambda_{i} \ge [/mm] 0 und [mm] \summe_{i=1}^{k} [/mm] = 1, [mm] s_{i} \in [/mm] S
Ich denke, dass ich die Summe, die z beschreibt insofern umformen oder -sortieren muss, dass ich über die Eigenschaft der Konvexität die Anzahl ihrer Summanden Stück für Stück verringern kann bis nur noch 2 verbleiben und ich letztlich wiederum über die Konvexität zeigen kann, dass z [mm] \in [/mm] S
Allerdings habe ich keine Idee, wie ich das anstellen soll.
Ich würde mich freuen, wenn mir jemand weiterhelfen könnte.
Viele Grüße,
Patrick
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:14 So 02.05.2010 | | Autor: | pelzig |
Wie habt ihr [mm] $\operatorname{conv}(S)$ [/mm] definiert? In meiner Welt ist das [mm] $$\operatorname{conv}(S):=\bigcap\{C\subset\IR^n\mid S\subset C\text{ und }C\text{ konvex}\}.$$ [/mm] (Man kann sich leicht überlegen dass es immer eine konvexe Obermenge gibt (nämlich welche?) und dass der beliebige Schnitt konvexer Mengen konvex ist. Damit ist [mm] $\operatorname{conv}(S)$ [/mm] die kleinste konvexe Menge, die S enthält)
Offensichtlich ist stets [mm] $S\subset\operatorname{conv}(S)$. [/mm] Ist nun S selbst schon konvex, dann ist aber nach Definition auch [mm]\operatorname{conv}(S)\subset S[/mm], also insgesamt [mm] $$S\subset\operatorname{conv}(S)\subset S\Rightarrow S=\operatorname{conv}(S).$$ [/mm] Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:45 Mo 03.05.2010 | | Autor: | oeli1985 |
ok, danke schon einmal bis hierhin. das ist auch alles soweit einleuchtend.
allerdings haben wir convS nie auf diese weise definiert, weshalb mir wichtig ist, dass ich das ganze auch anhand der mittel zeigen kann, die ich zur verfügung habe.
unsere definition war: convS ist die Menge aller [mm] z\in \IR^{n}, [/mm] wobei [mm] z=\summe_{i=1}^{k} \lambda_{i} s_{i} [/mm] mit [mm] \lambda_{i} \ge [/mm] 0 und [mm] \summe_{i}^{k} \lambda_{i}=1 [/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:42 Mo 03.05.2010 | | Autor: | dormant |
Hi!
Du sollst die etwas offensichtliche Aussage, dass in einem konvexen Raum (konvexe Kombination von 2 Pkten) auch alle anderen endlichen konvexen Kombinationen enthalten sind.
Mach's doch über Induktion:
k=2 und für [mm] z\in [/mm] ConvS mit einer konvexen Kombination von zwei Pkten, so ist auch offensichtlich [mm] z\in [/mm] S, da S konvex.
Versuch nun den Induktionsschritt zu machen.
Grüße,
dormant
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:29 Di 04.05.2010 | | Autor: | pelzig |
Da ich jetzt auch eine Weile dafür gebraucht habe erlaube ich mir mal zu präzisieren, was dormant uns wohl sagen wollte:
Lemma Ist S konvex, dann gilt für alle [mm] $n\in\IN$: [/mm] sind [mm]s_1,...,s_n\in S[/mm] und [mm] $\mu_1,...,\mu_n\in[0,1]$ [/mm] mit [mm] $\sum_{i=1}^n\mu_i=1$, [/mm] dann ist auch [mm]\sum_{i=1}^n\mu_is_i\in S[/mm].
Beweis: Durch Induktion über $n$. Der Fall $n=1$ ist offensichtlich okay. Sei nun [mm]n\ge 2[/mm]. O.B.d.A. können wir [mm]\mu_n\ne 1[/mm] annehmen (Warum?). Wir schreiben [mm] $$s:=\sum_{i=1}^n\mu_is_i=\sum_{i=1}^{n-1}\mu_is_i [/mm] + [mm] \mu_ns_n=(1-\mu_n)\cdot\left(\sum_{i=1}^{n-1}\frac{\mu_i}{1-\mu_n}\cdot s_i\right)+\mu_ns_n=:(1-\mu_n)\cdot\tilde{s}+\mu_ns_n$$ [/mm] Nun zeige, dass gilt [mm] $$\sum_{i=1}^{n-1}\frac{\mu_i}{1-\mu_n}=1,$$ [/mm] denn dann folgt nach Induktionsvoraussetzung [mm]\tilde{s}\in S[/mm] und damit nach Definition der Konvexität [mm]s\in S[/mm]. q.e.d.
Wenn du eine nette Übungsaufgabe suchst dann kannst du dir ja mal überlegen, warum deine Definition der konvexen Hülle mit der von mir übereinstimmt. Die wesentliche Schwierigkeit in dem Beweis dafür ist genau dieses Lemma.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:13 Do 06.05.2010 | | Autor: | oeli1985 |
danke an euch,
hab alles verstanden. die induktion ist eigentlich echt einfach. habe aber gar nicht drüber nachgedacht und ob ich auf die idee gekommen wäre die summe so zu konstruieren, dass ich den einen koeffizienten entsprechend der definition einer konvexen hülle heruasziehen kann, ist zweifelhaft 
aber für ähnliche aufgaben bin ich in zukunft gerüstet.
grüße,
patrick
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:09 Fr 07.05.2010 | | Autor: | oeli1985 |
hallo nochmal,
ich habe doch noch ein problem. es geht um folgendes ...
> Nun zeige, dass gilt
> [mm]\sum_{i=1}^{n-1}\frac{\mu_i}{1-\mu_n}=1,[/mm] denn dann folgt
> nach Induktionsvoraussetzung [mm]\tilde{s}\in S[/mm]
zu zeigen, dass die summe gleich 1 ist, ist unproblematisch
aber warum darf ich jetzt die induktionsvoraussetzung anwenden? für den fall, dass die summe nur aus einem summanden besteht, ist alles klar, aber sobald sie aus mehr summanden besteht, gilt die induktionsvoraussetzung doch nur falls den elementen aus S koeffizienten kleiner als 1 vorgeschaltet sind, so dass die summe dieser koeffizienten 1 ergibt.
in unserem fall, wäre aber doch jeder koeffizient gleich 1!?
was übersehe ich?
grüße,
patrick
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:56 Fr 07.05.2010 | | Autor: | dormant |
Hi!
> siehe oben
> hallo nochmal,
> ich habe doch noch ein problem. es geht um folgendes ...
>
> > Nun zeige, dass gilt
> > [mm]\sum_{i=1}^{n-1}\frac{\mu_i}{1-\mu_n}=1,[/mm] denn dann folgt
> > nach Induktionsvoraussetzung [mm]\tilde{s}\in S[/mm]
Also... zu beweisen ist: [mm] x=\summe_{i=1}^{n}\alpha_i x_i [/mm] , [mm] x_i \in [/mm] S und [mm] \summe \alpha [/mm] = 1, so ist x schon in S.
Induktion über n. Induktionsanfang für n = 1, 2 ist klar (für 2, da S konvex).
Nun ist [mm] x=\summe_{i=1}^{n}\alpha_i x_i [/mm] + [mm] \alpha_{n+1}x_{n+1}=y_{n}+ \alpha_{n+1}x_{n+1}.
[/mm]
Dabei ist nach der Voraussetzung [mm] y_n [/mm] schon in S. Und [mm] \alpha_{n+1} [/mm] ist kleiner eins. Geeignet skalieren um die Konvexität zu benutzen und du bist fertig.
> zu zeigen, dass die summe gleich 1 ist, ist
> unproblematisch
>
> aber warum darf ich jetzt die induktionsvoraussetzung
> anwenden? für den fall, dass die summe nur aus einem
> summanden besteht, ist alles klar, aber sobald sie aus mehr
> summanden besteht, gilt die induktionsvoraussetzung doch
> nur falls den elementen aus S koeffizienten kleiner als 1
> vorgeschaltet sind, so dass die summe dieser koeffizienten
> 1 ergibt.
>
> in unserem fall, wäre aber doch jeder koeffizient gleich
> 1!?
>
> was übersehe ich?
>
> grüße,
> patrick
Grüße,
dormant
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:50 Fr 07.05.2010 | | Autor: | oeli1985 |
> Nun ist [mm]x=\summe_{i=1}^{n}\alpha_i x_i[/mm] +
> [mm]\alpha_{n+1}x_{n+1}=y_{n}+ \alpha_{n+1}x_{n+1}.[/mm]
>
> Dabei ist nach der Voraussetzung [mm]y_n[/mm] schon in S. Und
> [mm]\alpha_{n+1}[/mm] ist kleiner eins. Geeignet skalieren um die
> Konvexität zu benutzen und du bist fertig.
das ist mir alles klar ... wenn ich das ganze dann umskaliere, so dass ich letztlich folgendes dort stehen habe:
[mm] y_{n}=\summe_{i=1}^{n}\alpha_{}i x_{i}=(1-\alpha_{n+1})\summe_{i=1}^{n}x_{i}
[/mm]
also gilt für x:
[mm] x=(1-\alpha_{n+1})\summe_{i=1}^{n}x_{i} [/mm] + [mm] \alpha_{n+1}x_{n+1}
[/mm]
Nun habe ich so skaliert, dass ich prinzipiell die Konvexität anwenden kann. Aber dafür muss gelten, dass [mm] \summe_{i=1}^{n}x_{i} \in [/mm] S
Nach Induktionsvoraussetzung gilt aber doch nur, dass diese Summe inkl. ihres Koeffizienten aus S ist!?
>
> > zu zeigen, dass die summe gleich 1 ist, ist
> > unproblematisch
> >
> > aber warum darf ich jetzt die induktionsvoraussetzung
> > anwenden? für den fall, dass die summe nur aus einem
> > summanden besteht, ist alles klar, aber sobald sie aus mehr
> > summanden besteht, gilt die induktionsvoraussetzung doch
> > nur falls den elementen aus S koeffizienten kleiner als 1
> > vorgeschaltet sind, so dass die summe dieser koeffizienten
> > 1 ergibt.
> >
> > in unserem fall, wäre aber doch jeder koeffizient gleich
> > 1!?
> >
> > was übersehe ich?
> >
> > grüße,
> > patrick
>
> Grüße,
> dormant
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:10 So 09.05.2010 | | Autor: | pelzig |
Ehrlich gesagt versteh ich dein Problem überhaupt nicht. Es steht doch alles fein aufgeschrieben in dem Beweis. Wir zeigen doch [mm] $$\sum_{i=1}^{n-1}\frac{\mu_i}{1-\mu_n}=1$$ [/mm] Nach Induktionsvoraussetzung ist also die "Konvexkombination" von [mm]n-1[/mm] Punkten [mm] $$\sum_{i=1}^{n-1}\frac{\mu_i}{1-\mu_n}s_i$$ [/mm] ebenfalls in S.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:40 So 09.05.2010 | | Autor: | oeli1985 |
mein problem ist einfach folgendes:
$ [mm] y_{n}=\summe_{i=1}^{n}\alpha_{}i x_{i}=(1-\alpha_{n+1})\summe_{i=1}^{n}x_{i} [/mm] $ ist nach IV aus S
Das bedeutet aber doch nicht gleichzeitig, dass $ [mm] \summe_{i=1}^{n}x_{i} \in [/mm] $ S oder?
Genau das muss aber doch gelten damit ich die Df von Konvexität anwenden kann, so dass:
$ [mm] x=(1-\alpha_{n+1})\summe_{i=1}^{n}x_{i} [/mm] $ + $ [mm] \alpha_{n+1}x_{n+1} [/mm] $ [mm] \in [/mm] S
Möglicherweise hab ich nur eine dicke Blockade im Kopf, aber ich sehe noch nicht warum ich die Konvexität sonst anwenden dürfte.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:17 So 09.05.2010 | | Autor: | pelzig |
> [mm]y_{n}=\summe_{i=1}^{n}\alpha_{}i x_{i}=(1-\alpha_{n+1})\summe_{i=1}^{n}x_{i}[/mm]
Diese Gleichheit ist einfach völliger Unfug. Wie kommst du auf sowas?! Es muss eben heißen (wie ich jetzt schon zwei mal geschrieben habe): [mm] $$y_n=\sum_{n=1}^n\alpha_ix_i=(1-\alpha_{n+1})\cdot\sum_{i=1}^n\red{\frac{\alpha_i}{1-\alpha_{n+1}}}x_i.$$ [/mm] Und die Induktionsvoraussetzung besagt nun, dass die Summe [mm] $$\sum_{i=1}^n\frac{\alpha_i}{1-\alpha_{n+1}}x_i$$ [/mm] ein Element aus S ist! Über [mm] $y_n$ [/mm] selbst wissen wir nichts, und i.A. ist das auch keine Element aus S. Dormant hat das zwar in seinem letzten Beitrag behauptet, aber das ist einfach falsch.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:25 So 09.05.2010 | | Autor: | oeli1985 |
ich habe meinen denkfehler gefunden ... haben bissle aneinander vorbei geredet, sosnt wärs wahrscheinlich früher klar gewesen
jedenfalls danke
grüße,
patrick
|
|
|
|
