www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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:

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.vorhilfe.de