Konvexität verschiedener Mengen

Neue Frage »

21.10.2011, 13:21	Lea	Auf diesen Beitrag antworten »
Konvexität verschiedener Mengen Hallo, ich hätte eine Frage: Ich will die Konvexität folgender Mengen zeigen: 1) Hyperebenen 2) Halbräumen 3) Polyeder Ich weiß, dass eine Menge $\begin{eqnarray} S \subseteq \mathbb R^n \end{eqnarray}$ konvex ist, wenn für alle $\begin{eqnarray} x,y \in S \end{eqnarray}$ und $\begin{eqnarray} \lambda \leq 1 \end{eqnarray}$ gilt $\begin{eqnarray} \lambda x+(1- \lambda)y \in S \end{eqnarray}$ . Es fällt mir allerdings schwer dies auf die genannten Mengen zu übertragen. Definitionen wären: Hyperebene: für $\begin{eqnarray} a \in \mathbb R^n, \beta \in \mathbb R \end{eqnarray}$ gilt $\begin{eqnarray} \{x \in \mathbb R^n\|<a,x>= \beta \} \end{eqnarray}$ Halbraum: für $\begin{eqnarray} \lambda: V \to \mathbb R, \beta \in \mathbb R \end{eqnarray}$ heißt die Teilmenge $\begin{eqnarray} \{ \nu \in V\| \lambda (\nu) \geq \beta \} \end{eqnarray}$ bzw. $\begin{eqnarray} \{ \nu \in V\| \lambda (\nu) > \beta \} \end{eqnarray}$ Polyeder: für $\begin{eqnarray} m \in \mathbb N, A \in K^{(m,n)}, b \in K^m \end{eqnarray}$ heißt $\begin{eqnarray} P= \{x \in K^n \| Ax \leq b \} \end{eqnarray}$ Polyeder. Kann mir da jemand einen Tipp geben? Wäre sehr dankbar dafür.
21.10.2011, 15:10	Cel	Auf diesen Beitrag antworten »
Hallo, hast du denn eine Vorstellung, wie diese Mengen aussehen? Was bedeutet konvex, in eigenen Worten? Stichwort: Verbindungstrecke. Und dann nehme dir zwei Vektoren, die in der Menge sind und versuche zu zeigen, dass die Konvexkombi drin liegt. Denk dabei an die Eigenschaften des Skalarproduktes, der Linearformen und der Matrixmultiplikation.
21.10.2011, 15:25	Lea	Auf diesen Beitrag antworten »
Danke für die Antwort. Genau das ist das Problem, dass es an der Vorstellung dieser Mengen mangelt. Konvex bedeutet, dass 2 von beliebigen Punkten, die zur Menge gehören, auch stets deren Verbindungsstrecke ganz in der Menge liegt. Das kann ich mir einigermaßen vorstellen. Noch eine Frage: Wenn ich mir einfach 2 Punkte aus der Menge nehme, habe ich das dann auch allgemein gezeigt? Es kann doch für manche funktionieren und für andere nicht oder?
21.10.2011, 16:36	Cel	Auf diesen Beitrag antworten »
Wenn es für manche funktioniert und für manche nicht, dann ist die Menge nicht konvex. Ich musste gerade feststellen, dass mir deine Definition von Halbraum eher nicht geläufig ist. Was ist V, was $\begin{eqnarray} \lambda \end{eqnarray}$ ? Ich vermute, dass das Linearformen sind, aber bin mir jetzt nicht mehr sicher. Kannst du das mal verlinken oder noch besser hochladen? Edit: Brauchst du doch nicht. Steht ja auf Wikipedia. Ich hatte also Recht. 1) und 3) ist jedenfalls kein Problem. Nimm dir zwei Punkte, die in der Menge liegen und zeige, dass die Linearkombi ebenfalls drinliegt. Also bei 1) seien x und y in der Hyperebene., d.h. $\begin{eqnarray} \langle a, x \rangle = \beta \end{eqnarray}$ und $\begin{eqnarray} \langle a, y \rangle = \beta \end{eqnarray}$ . Zeige nun $\begin{eqnarray} \langle a, \lambda x + (1-\lambda) y \rangle = \beta \end{eqnarray}$ . Damit wäre die Ebene dann konvex. Und wie gesagt: Denk an die Eigenschaften eines Skalarproduktes.
21.10.2011, 18:25	Lea	Auf diesen Beitrag antworten »
Also ich glaube ich habe das jetzt. $\begin{eqnarray} < \lambda a,x>+ < a, (1- \lambda), y> = <\lambda a, x> + <(a-a \lambda), y>= < \lambda a, x>+ <a,y> - <a,y \lambda>= \lambda (<a,x>-<a,y>)+<a,y> = \beta \end{eqnarray}$ Ich hoffe ich habs so richtig aufgeschrieben. Hatte es noch ausführlicher aufgeschrieben. Beim Polyeder muss ich dann auch 2 Punkte wählen? Weiß irgendwie nicht so genau wie die aussehen könnten.
22.10.2011, 19:30	Cel	Auf diesen Beitrag antworten »
Die Rechnung stimmt, aber wieso hast du nicht mit dem Ausdruck angefangen, den ich aufgeschrieben habe? Den sehe ich auch nicht bei dir ... Für den Polyeder das gleiche: Seien x und y im Polyeder, gelte also $\begin{eqnarray} Ax \leq b \end{eqnarray}$ und $\begin{eqnarray} Ay \leq b \end{eqnarray}$ . Zeige: $\begin{eqnarray} A (\lambda x + (1-\lambda y)) \leq b \end{eqnarray}$ . Hierbei brauchst du die Regeln für Matrix-Vektormultiplikation.
Anzeige

23.10.2011, 10:56	Lea	Auf diesen Beitrag antworten »
Ich hatte damit angefangen. Habe es am Anfang vllt. ein bisschen blöd aufgeschrieben. Hier noch mal ein bisschen anders: $\begin{eqnarray} <a, \lambda x + (1- \lambda ) y> = < a, \lambda x>+ < a, (1- \lambda) y> = <\lambda a, x> + <(a-a \lambda), y>= < \lambda a, x>+ <a,y> - <a,y \lambda>= \lambda (<a,x>-<a,y>)+<a,y> = \beta \end{eqnarray}$ Stimmt das dann so auch? Zum Polyeder: Dann hätte ich folgendes: $\begin{eqnarray} A( \lambda x + (1- \lambda) y) \leq b \Leftrightarrow A \lambda x + A (1- \lambda ) y \leq b \Leftrightarrow \lambda Ax + Ay - \lambda Ay \leq b \Leftrightarrow \lambda (Ax-Ay) + Ay \leq b \end{eqnarray}$ Ich habe es jetzt etwas verkürzt aufgeschrieben. Hatte es mir selbst ausführlicher aufgeschrieben. Wäre der Beweis dafür dann so richtig? Aber Halbräumen ist das doch etwas komplizierter oder? Vorallem welche von den 2 Definitionen muss ich da nehmen? Die mit dem größer gleich oder die nur mit dem größer?
23.10.2011, 14:05	Cel	Auf diesen Beitrag antworten »
OK, die Hyperebene sieht gut aus. Es geht aber auch viel kürzer: $\begin{eqnarray} \langle a, \lambda x + (1- \lambda ) y \rangle = \langle a, \lambda x\rangle + \langle a, (1- \lambda) y \rangle = \lambda \underbrace{\langle a, x \rangle}_{= \beta} + (1-\lambda) \underbrace{\langle a, y \rangle}_{= \beta} = \beta \end{eqnarray}$ Polyeder ist auch gut, aber auch hier geht es kürzer. $\begin{eqnarray} A( \lambda x + (1- \lambda) y) = A \lambda x + A (1- \lambda ) y = \lambda \underbrace{A x}_{\leq b} + (1- \lambda) \underbrace{Ay}_{\leq b} \leq b \end{eqnarray}$ Das heißt aber nicht, dass deine Rechnungen falsch sind. Für den Halbraum kannst du eine Rechnung nehmen und überall statt $\begin{eqnarray} > \end{eqnarray}$ später $\begin{eqnarray} \geq \end{eqnarray}$ schreiben.
23.10.2011, 14:23	Lea	Auf diesen Beitrag antworten »
Vielen Danke für die Hilfe. Hat mir sehr weitergeholfen. Ich habe für den Halbraum doch eine andere Definition benutzt: $\begin{eqnarray} H= \{x \in \mathbb R ^n: a ^Tx \leq \alpha\} \end{eqnarray}$ und habe die Konvexität ähnlich wie bei den anderen Mengen bewiesen.
23.10.2011, 14:26	Cel	Auf diesen Beitrag antworten »
Ja, geht auch wunderbar.
23.10.2011, 14:48	Lea	Auf diesen Beitrag antworten »
Nochmal vielen vielen Dank.

Neue Frage »

Antworten »

Konvexität verschiedener Mengen

Verwandte Themen