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 Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

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
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenUni-SonstigesKonvexität von Mengen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Uni-Sonstiges" - Konvexität von Mengen
Konvexität von Mengen < Sonstiges < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Konvexität von Mengen: Idee
Status: (Frage) beantwortet Status 
Datum: 13:08 Mo 23.11.2015
Autor: mathstu

Aufgabe
Beweisen oder widerlegen Sie, dass die folgenden Mengen konvex sind:

[mm] M_{1} [/mm] := {x [mm] \in \IR^{n} [/mm] : [mm] a_{1}x_{1}+...+a_{n}x_{n} [/mm] > [mm] a_{0} [/mm] } für gegebene [mm] a_{0},...,a_{n} \in \IR. [/mm]

[mm] M_{2} [/mm] := {x [mm] \in \IR^{n} [/mm] : [mm] ||x||_{2} [/mm] = 1}

[mm] M_{3} [/mm] := {x [mm] \in \IR^{n} [/mm] : [mm] (a_{11}x_{1}+...+a_{1n}x_{n})^{2} [/mm] + ... + [mm] (a_{n1}x_{1}+...+a_{nn}x_{n})^{2} \le [/mm] 1} für gegebene [mm] a_{ij} \in \IR [/mm] , i,j=1,...,n.

[mm] M_{4} [/mm] := [mm] \alpha [/mm] * A + [mm] \beta [/mm] * B, wobei A, B [mm] \subset \IR^{n} [/mm] konvexe Mengen und [mm] \alpha [/mm] , [mm] \beta \in \IR. [/mm]

Guten Tag,

ich soll diese Aufgabe in Lineare Optimierung lösen. [mm] M_{2} [/mm] und [mm] M_{4} [/mm] habe ich alleine gelöst, allerdings weiß ich bei [mm] M_{1} [/mm] und [mm] M_{3} [/mm] nicht weiter.

Für [mm] M_{1} [/mm] gilt: Seien x, y [mm] \in M_{1}, [/mm] dann gilt: [mm] a_{1}x_{1}+...+a_{n}x_{n} [/mm] > [mm] a_{0} [/mm] und [mm] a_{1}y_{1}+...+a_{n}y_{n} [/mm] > [mm] a_{0}. [/mm]
Um Konvexität zu zeigen muss gelten, dass [mm] \lambda [/mm] x + (1- [mm] \lambda [/mm] ) y [mm] \in M_{1}, [/mm] für alle x, y [mm] \in M_{1}. [/mm]

Heißt das ich muss in diesem Fall zeigen, dass [mm] \lambda [/mm] x + (1- [mm] \lambda [/mm] y) > [mm] a_{0} [/mm] gilt?

Wenn ja, dann habe ich schon mal folgendes durchgerechnet:
[mm] \lambda [/mm] x + (1- [mm] \lambda [/mm] ) y
= [mm] \lambda a_{1}x_{1}+...+a_{n}x_{n} [/mm] + (1- [mm] \lambda a_{1}y_{1}+...+a_{n}y_{n}) [/mm]

> [mm] \lambda a_{0} [/mm] + (1- [mm] \lambda) a_{0} [/mm]

= 1
Aber damit kann man nicht viel anfangen, denn man weiß somit nur, dass [mm] \lambda [/mm] x + (1- [mm] \lambda [/mm] ) y > [mm] a_{0} [/mm] wenn [mm] a_{0} \le [/mm] 1. Oder weißt dies schon darauf hin, dass [mm] M_{1} [/mm] nicht konvex ist und dass ich das widerlegen muss. Allerdings weiß ich nicht wie ich das noch umformen kann, damit ich das beweisen kann.

Bei [mm] M_{3} [/mm] habe ich genau das gleiche Problem.

Bitte nur Lösungsideen und keine ganze Lösung hier drunter schreiben.

Viele Grüße, mathstu

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

        
Bezug
Konvexität von Mengen: Antwort
Status: (Antwort) fertig Status 
Datum: 13:45 Mo 23.11.2015
Autor: fred97

[mm] M_1 [/mm] bist Du völlig falsch angegeangen !

Seien [mm] x=(x_1,...,x_n), y=(y_1,...,y_n) \in M_1 [/mm] und [mm] \lambda \in [/mm] [0,1].

Dann ist $ [mm] \lambda x+(1-\lambda)y=( \lambda x_1+(1-\lambda)y_1,..., \lambda x_n+(1-\lambda)y_n)$ [/mm]

Um zu prüfen, ob

    $ [mm] \lambda x+(1-\lambda)y \in M_1$ [/mm]

gilt, musst Du prüfen, ob

   [mm] $a_1( \lambda x_1+(1-\lambda)y_1) +...+a_n( \lambda x_n+(1-\lambda)y_n) >a_0$ [/mm]

ist.

Es ist so, zeige dies !


Bei [mm] M_3 [/mm] sieht man mehr und rechnet wesentlich weniger, wenn man die Sache so betrachtet:

Sei   $ A:=( [mm] a_{ij}) [/mm] $  (nxn -Matrix) und [mm] $f:\IR^n \to \IR^n$ [/mm] def. durch

  $f(x)=Ax$   (Matrix -Vektor- Produkt).

Damit haben wir:

   [mm] M_3=\{x \in \IR^n: ||f(x)||_2 \le 1\}, [/mm]

wobei [mm] $||*||_2$ [/mm] die euklidische Norm auf [mm] \IR^n [/mm] sein soll.

[mm] M_3 [/mm] ist konvex.

Zeige dies.

FRED



Bezug
                
Bezug
Konvexität von Mengen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:58 Mo 23.11.2015
Autor: mathstu

Vielen Dank für die Hilfestellung.

Zu [mm] M_{1} [/mm] habe ich nun folgendes:

[mm] a_{1}( \lambda x_{1} [/mm] + (1- [mm] \lambda)y_{1}) [/mm] + ... + [mm] a_{n}( \lambda x_{n} [/mm] + (1- [mm] \lambda)y_{n}) [/mm]
= [mm] \lambda a_{1} x_{1} [/mm] + ... + [mm] \lambda a_{n} x_{n} [/mm] + (1- [mm] \lambda) a_{1} y_{1} [/mm] + ... + (1- [mm] \lambda) a_{n} y_{n} [/mm]
= [mm] \lambda (a_{1} x_{1} [/mm] + ... + [mm] a_{n} x_{n}) [/mm] + (1- [mm] \lambda)(a_{1} y_{1} [/mm] + ... + [mm] a_{n} y_{n}) [/mm]

> [mm] \lambda a_{0} [/mm] + (1- [mm] \lambda) a_{0} [/mm]

[mm] =a_{0} [/mm]

[mm] \Rightarrow M_{1} [/mm] ist konvex.


Zu [mm] M_{3}: [/mm]
Es gilt zu zeigen, dass || [mm] \lambda [/mm] f(x) + (1- [mm] \lambda) [/mm] f(y)|| [mm] \le [/mm] 1.
|| [mm] \lambda [/mm] f(x) + (1- [mm] \lambda) [/mm] f(y)||
[mm] \le [/mm] || [mm] \lambda [/mm] f(x)|| + ||(1- [mm] \lambda) [/mm] f(y)||
[mm] \le [/mm] | [mm] \lambda| [/mm] ||f(x)|| + |(1- [mm] \lambda)| [/mm] ||f(y)||
[mm] \le [/mm] | [mm] \lambda| [/mm] * 1 + |(1- [mm] \lambda)| [/mm] * 1
= 1, da [mm] \lambda \in [/mm] [0,1]

[mm] \Rightarrow M_{3} [/mm] ist konvex

Viele Grüße, mathstu

Bezug
                        
Bezug
Konvexität von Mengen: Antwort
Status: (Antwort) fertig Status 
Datum: 22:21 Mo 23.11.2015
Autor: Marcel

Hallo,

> Vielen Dank für die Hilfestellung.
>  
> Zu [mm]M_{1}[/mm] habe ich nun folgendes:

Du hast die Voraussetzungen hier nicht notiert, sie stehen ja aber bei Fred:
Seien x, y $ [mm] \in M_{1}, [/mm] $ dann gilt: $ [mm] a_{1}x_{1}+...+a_{n}x_{n} [/mm] $ > $ [mm] a_{0} [/mm] $ und $ [mm] a_{1}y_{1}+...+a_{n}y_{n} [/mm] $ > $ [mm] a_{0};$ [/mm] ferner $0 [mm] \le \lambda \le [/mm] 1$ fest.

Dann folgt für [mm] $\lambda x+(1-\lambda)y=(\lambda x_k+(1-\lambda)y_k)_{k=1}^n$, [/mm] dass

> [mm]a_{1}( \lambda x_{1}[/mm] + (1- [mm]\lambda)y_{1})[/mm] + ... + [mm]a_{n}( \lambda x_{n}[/mm]
> + (1- [mm]\lambda)y_{n})[/mm]
>  = [mm]\lambda a_{1} x_{1}[/mm] + ... + [mm]\lambda a_{n} x_{n}[/mm] + (1-
> [mm]\lambda) a_{1} y_{1}[/mm] + ... + (1- [mm]\lambda) a_{n} y_{n}[/mm]
>  =
> [mm]\lambda (a_{1} x_{1}[/mm] + ... + [mm]a_{n} x_{n})[/mm] + (1-
> [mm]\lambda)(a_{1} y_{1}[/mm] + ... + [mm]a_{n} y_{n})[/mm]
>  > [mm]\lambda a_{0}[/mm]

> + (1- [mm]\lambda) a_{0}[/mm]
>  [mm]=a_{0}[/mm]

Nach Definition von [mm] $M_1$ [/mm] also [mm] $\lambda x+(1-\lambda)y \in M_1$. [/mm] Da $x,y [mm] \in M_1$ [/mm]
und [mm] $\lambda \in [/mm] [0,1]$ beliebig waren:

> [mm]\Rightarrow M_{1}[/mm] ist konvex.
>  
>
> Zu [mm]M_{3}:[/mm]
>  Es gilt zu zeigen, dass || [mm]\lambda[/mm] f(x) + (1- [mm]\lambda)[/mm]
> f(y)|| [mm]\le[/mm] 1.

Das ist zu weit gedacht, und ich glaube nicht, dass Du Dir da wirklich bewußt
bist, warum das tatsächlich stimmt.
Erstmal:
Unter der Voraussetzung, dass [mm] $\lambda \in [/mm] [0,1]$ und $x,y [mm] \in M_3$, [/mm] also [mm] $x=(x_1,...,x_n)^T$, $y=(y_1,...,y_n)^T$ [/mm] beide in [mm] $\IR^n$ [/mm] mit

    [mm] $\|f(x)\| \le [/mm] 1$ und [mm] $\|f(y)\| \le [/mm] 1$,

sind, ist nachzuweisen, dass

    [mm] $\lambda x+(1-\lambda)y \in M_3$ [/mm]

ist; das geht nach Definition von [mm] $M_3$, [/mm] indem

    [mm] $\|f(\lambda x+(1-\lambda)y)\| \le [/mm] 1$

begründet wird! (Klar: [mm] $\lambda x+(1-\lambda)y \in \IR^n$.) [/mm]

Nun gilt

    [mm] $\|f(\lambda x+(1-\lambda)y)\|$ [/mm]

ist gleich mit

>  || [mm]\lambda[/mm] f(x) + (1- [mm]\lambda)[/mm] f(y)||

weil eben $f$ eine lineare Funktion ist, so dass "ja sogar"

    [mm] $f(\lambda x+(1-\lambda)y=\lambda [/mm] f(x) + (1- [mm] \lambda)f(y)$ [/mm]

gilt!

Weiter:

> || [mm]\lambda[/mm] f(x) + (1- [mm]\lambda)[/mm] f(y)||
>  [mm]\le[/mm] || [mm]\lambda[/mm] f(x)|| + ||(1- [mm]\lambda)[/mm] f(y)||
>  [mm]\le[/mm] | [mm]\lambda|[/mm] ||f(x)|| + |(1- [mm]\lambda)|[/mm] ||f(y)||
>  [mm]\le[/mm] | [mm]\lambda|[/mm] * 1 + |(1- [mm]\lambda)|[/mm] * 1
>  = 1, da [mm]\lambda \in[/mm] [0,1]
>  
> [mm]\Rightarrow M_{3}[/mm] ist konvex
>  
> Viele Grüße, mathstu

Btw.: Bei [mm] $M_1$ [/mm] hätte man sich das auch etwas einfacher machen können.
Setze

    [mm] $a:=(a_1,...,a_n)^T$ [/mm]

und seien [mm] $x:=(x_1,...,x_n)^T$ [/mm] sowie [mm] $y:=(y_1,...,y_n)^T$ [/mm] in [mm] $M_1$. [/mm]

Sei

    [mm] $g(\tilde{x}):=a^T*\tilde{x}$ [/mm] (Zeilenvektor [mm] $a^T$ [/mm] mal Spaltenvektor [mm] $\tilde{x} \in \IR^n$; [/mm]
               Stichwort: Standardskalarprodukt zwischen dem festen Vektor $a$ und dem variablen Vektor [mm] $\tilde{x}$) [/mm]

Dann ist

    $x [mm] \in M_1$ $\iff$ [/mm] $g(x) > [mm] a_0\,.$ [/mm]

Also $x,y [mm] \in M_1$ $\iff$ [/mm] $g(x) > [mm] a_0$ [/mm] und $g(y) > [mm] a_0\,.$ [/mm]

Um für [mm] $\lambda \in [/mm] [0,1]$ nun [mm] $z:=\lambda x+(1-\lambda)y \in M_1$ [/mm] nachzuweisen,
ist zu belegen, dass $g(z)=a^Tz > [mm] a_0$ [/mm] ist.

Weil [mm] $g\,$ [/mm] linear ist, folgt mit den obigen Voraussetzungen (beachte auch, dass
[mm] $\lambda \ge [/mm] 0$ und [mm] $1-\lambda \ge [/mm] 0$ gelten)

    [mm] $g(z)=g(\lambda x+(1-\lambda)y)=\lambda g(x)+(1-\lambda)g(y) [/mm] > [mm] \lambda a_0+(1-\lambda)g(y) [/mm] > [mm] \lambda a_0+(1-\lambda)a_0=a_0$ [/mm]

Gruß,
  Marcel

Bezug
                
Bezug
Konvexität von Mengen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 22:44 Mo 23.11.2015
Autor: Marcel

Hallo,

> [mm]M_1[/mm] bist Du völlig falsch angegeangen !
>  
> Seien [mm]x=(x_1,...,x_n), y=(y_1,...,y_n) \in M_1[/mm] und [mm]\lambda \in[/mm]
> [0,1].
>  
> Dann ist [mm]\lambda x+(1-\lambda)y=( \lambda x_1+(1-\lambda)y_1,..., \lambda x_n+(1-\lambda)y_n)[/mm]
>  
> Um zu prüfen, ob
>
> [mm]\lambda x+(1-\lambda)y \in M_1[/mm]
>  
> gilt, musst Du prüfen, ob
>  
> [mm]a_1( \lambda x_1+(1-\lambda)y_1) +...+a_n( \lambda x_n+(1-\lambda)y_n) >a_0[/mm]
>  
> ist.
>  
> Es ist so, zeige dies !
>  
>
> Bei [mm]M_3[/mm] sieht man mehr und rechnet wesentlich weniger, wenn
> man die Sache so betrachtet:
>
> Sei   [mm]A:=( a_{ij})[/mm]  (nxn -Matrix) und [mm]f:\IR^n \to \IR^n[/mm]
> def. durch
>  
> [mm]f(x)=Ax[/mm]   (Matrix -Vektor- Produkt).
>  
> Damit haben wir:
>  
> [mm]M_3=\{x \in \IR^n: ||f(x)||_2 \le 1\},[/mm]

ich ergänze hierbei noch die *Banalität*

    [mm] $\|f(x)\|_2 \le [/mm] 1$ [mm] $\iff$ ${\|f(x)\|_2}^2 \le [/mm] 1$

(Die rechteste Seite steht ja eigentlich dann in [mm] $M_3$.) [/mm]

Gruß,
  Marcel

Bezug
                        
Bezug
Konvexität von Mengen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 09:12 Di 24.11.2015
Autor: mathstu

Danke Marcel für die Erklärungen.
Dass  

> ich ergänze hierbei noch die *Banalität*
>  
> [mm]\|f(x)\|_2 \le 1[/mm] [mm]\iff[/mm] [mm]{\|f(x)\|_2}^2 \le 1[/mm]
>  
> (Die rechteste Seite steht ja eigentlich dann in [mm]M_3[/mm].)

gilt habe ich schon auf meinem Übungsblatt stehen, das hatten wir schon in Ana bewiesen.

Viele Grüße, mathstu

Bezug
                                
Bezug
Konvexität von Mengen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:50 Di 24.11.2015
Autor: Marcel

Hallo,

> Danke Marcel für die Erklärungen.
>  Dass  
> > ich ergänze hierbei noch die *Banalität*
>  >  
> > [mm]\|f(x)\|_2 \le 1[/mm] [mm]\iff[/mm] [mm]{\|f(x)\|_2}^2 \le 1[/mm]
>  >  
> > (Die rechteste Seite steht ja eigentlich dann in [mm]M_3[/mm].)
>  
> gilt habe ich schon auf meinem Übungsblatt stehen, das
> hatten wir schon in Ana bewiesen.

naja, das ist wirklich banal, weil Du schnell für eine reelle Zahl $r [mm] \ge [/mm] 0$ siehst

    $r < [mm] 1\,$ $\iff$ $r^2 [/mm] < [mm] 1\,.$ [/mm]

Würde man das wirklich nochmal beweisen wollen, so geht das in Sekunden:

[mm] "$\Rightarrow$": [/mm] $r < 1$ liefert $r*r < r*1 < 1$

[mm] "$\Leftarrow$": $r^2<1$ $\iff$ $1^2-r^2 [/mm] > 0$ [mm] $\iff$ [/mm] $(1+r)(1-r) > [mm] 0\,.$ [/mm] Also muss

    entweder sowohl $1+r > 0$ als auch $1-r > 0$

oder

    sowohl $1+r < 0$ als auch $1-r < 0$

gelten. Der zweite Fall liefert $r < [mm] -1\,,$ [/mm] was wegen $r [mm] \ge [/mm] 0$ nicht geht. Also
gilt der erste bzw.

    $r > -1$ und $r < [mm] 1\,,$ [/mm] also $-1 < r < [mm] 1\,$ [/mm]

bzw. weil ja $r [mm] \ge [/mm] 0$ war:

    $0 [mm] \le [/mm] r < [mm] 1\,.$ [/mm]

Insbesondere $r < [mm] 1\,.$ [/mm]
    
Sieht jetzt hier nach viel mehr aus als eigentlich nötig. ;-)

Nebenbei: Der zweite Fall wäre sowieso unmöglich, denn wie sollte

    zugleich $r > [mm] 1\,$ [/mm] als auch $r < [mm] -1\,$ [/mm]

sein? ;-)

Gruß,
  Marcel

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


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