matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Schulmathe
  Status Primarstufe
  Status Mathe Klassen 5-7
  Status Mathe Klassen 8-10
  Status Oberstufenmathe
    Status Schul-Analysis
    Status Lin. Algebra/Vektor
    Status Stochastik
    Status Abivorbereitung
  Status Mathe-Wettbewerbe
    Status Bundeswettb. Mathe
    Status Deutsche MO
    Status Internationale MO
    Status MO andere Länder
    Status Känguru
  Status Sonstiges

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenOperations Researchkonvexe Hülle
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Operations Research" - konvexe Hülle
konvexe Hülle < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Operations Research"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

konvexe Hülle: S ist konvex <=> S = convS
Status: (Frage) beantwortet Status 
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

        
Bezug
konvexe Hülle: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
konvexe Hülle: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:45 Mo 03.05.2010
Autor: oeli1985

Aufgabe
siehe oben

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]



Bezug
                        
Bezug
konvexe Hülle: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                
Bezug
konvexe Hülle: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                        
Bezug
konvexe Hülle: Danke
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                                        
Bezug
konvexe Hülle: induktionsvoraussetzung
Status: (Frage) beantwortet Status 
Datum: 17:09 Fr 07.05.2010
Autor: oeli1985

Aufgabe
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]

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

Bezug
                                                
Bezug
konvexe Hülle: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                        
Bezug
konvexe Hülle: df konvexe hülle
Status: (Frage) beantwortet Status 
Datum: 22:50 Fr 07.05.2010
Autor: oeli1985

Aufgabe
siehe oben

> 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


Bezug
                                                                
Bezug
konvexe Hülle: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                                        
Bezug
konvexe Hülle: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

Bezug
                                                                                
Bezug
konvexe Hülle: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                                                                        
Bezug
konvexe Hülle: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Operations Research"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.schulmatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]