Konvexität von Mengen < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | 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.
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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
|
|
|
| |
|
| Status: |
(Antwort) fertig | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | 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
|
|
|
|
