www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

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
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.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]