Menge der Optimallösungen konvex

26.03.2018, 15:18	LuciaSera	Auf diesen Beitrag antworten »
Menge der Optimallösungen konvex Meine Aufgabe lautet: Gegeben sei die Optimierungsaufgabe $\begin{eqnarray} min_{x\in K} f(x) \end{eqnarray}$ mit einer nichtleeren konvexen Menge $\begin{eqnarray} K \subseteq \mathbb R^{n} \end{eqnarray}$ und einer konvexen Funktion $\begin{eqnarray} f: K \to \mathbb R \end{eqnarray}$ . Beweisen Sie, dass die Menge $\begin{eqnarray} \left\{ x \in K: f(x) \leq f(y), \forall y\in K \right\} \end{eqnarray}$ der Optimallösungen eine konvexe Menge ist. Die Aufgabe scheint mir nicht besonders schwierig zu sein, ich denke, dass ich einfach nur einen Stoß in die richtige Richtung brauche. Ich habe meine zu zeigende Menge als A definiert und von meinem x und y weiß ich, dass sie Vektoren der Länge n sind. zz: $\begin{eqnarray} S(a,b)= \left\{ \lambda a+(1-\lambda)b \| \lambda \in (0,1) \right\} \end{eqnarray}$ mit $\begin{eqnarray} a,b \in A \end{eqnarray}$ Stimmt das? Und wenn ja, wie fange ich dann am besten an?
26.03.2018, 16:13	IfindU	Auf diesen Beitrag antworten »
RE: Menge der Optimallösungen konvex Ich weiß nicht wirklich was der Ansatz soll. Fall 1: Die Menge der Optimallösungen ist leer. Fall 2: Sei $\begin{eqnarray} L = \min_{x\in K} f(x) \end{eqnarray}$ . Dann ist $\begin{eqnarray} \{ x \in K : f(x) \leq f(y) \forall y \in K \} = \{ x \in K : f(x) = L \} \end{eqnarray}$ . Zu zeigen ist also, falls $\begin{eqnarray} x,y \in K \end{eqnarray}$ mit $\begin{eqnarray} f(x) = L \end{eqnarray}$ sind, so ist auch $\begin{eqnarray} f(\lambda x + (1-\lambda)y) = L \end{eqnarray}$ für alle $\begin{eqnarray} \lambda \in [0,1] \end{eqnarray}$ . Das folgt sehr leicht mit Konvexität und der Minimalität von $\begin{eqnarray} L \end{eqnarray}$ .
26.03.2018, 17:06	LuciaSera	Auf diesen Beitrag antworten »
Okay.. da habe ich ja ganz falsch gedacht anscheinend.. Würde das so stimmen: $\begin{eqnarray} f(x)=M \Rightarrow M \leq f(y)<br /> <br /> \Rightarrow f(\lambda x+(1-\lambda)y) \leq \lambda f(x)+(1-\lambda)f(y)<br /> \end{eqnarray}$ Weil f(x)=M: $\begin{eqnarray} <br /> \Leftrightarrow f(\lambda x+(1-\lambda)y)-(1-\lambda)f(y) \leq \lambda M<br /> \end{eqnarray}$ Wegen Minimalität und $\begin{eqnarray} \lambda \in (0,1) \end{eqnarray}$ : $\begin{eqnarray} <br /> \Leftrightarrow f(\lambda x+(1-\lambda)y)-(1-\lambda)f(y) \leq M<br /> \end{eqnarray}$ Weil $\begin{eqnarray} M \leq f(y) \end{eqnarray}$ und $\begin{eqnarray} \lambda \in (0,1) \end{eqnarray}$ : $\begin{eqnarray} <br /> \Leftrightarrow f(\lambda x+(1-\lambda)y)-M = M<br /> \Leftrightarrow f(\lambda x+(1-\lambda)y) = 2M<br /> \end{eqnarray}$ Wenn M minimal, dann auch 2M minimal: $\begin{eqnarray} <br /> \Leftrightarrow f(\lambda x+(1-\lambda)y) = M<br /> \end{eqnarray}$ Stimmt das so? Also auch von der Argumentation der einzelnen Schritte oder bin ich auf einem falschen Weg?
26.03.2018, 17:20	IfindU	Auf diesen Beitrag antworten »
Ich hatte oben etwas vergessen: Es ist $\begin{eqnarray} x, y\in K \end{eqnarray}$ mit $\begin{eqnarray} f(x) = f(y) = M \end{eqnarray}$ . Zu zeigen $\begin{eqnarray} f( \lambda x+ (1-\lambda) y) = M \end{eqnarray}$ für alle $\begin{eqnarray} \lambda \in [0,1] \end{eqnarray}$ . In Worten: Die Menge der optimalen Lösungen ist konvex heißt, dass für je zwei optimalen Lösungen auch jeder Punkt der Verbindungsstrecke optimal ist.
26.03.2018, 17:44	LuciaSera	Auf diesen Beitrag antworten »
Ausgehend davon habe ich nun: $\begin{eqnarray} f(x)=f(y)=M \end{eqnarray}$ $\begin{eqnarray} <br /> \Rightarrow f(\lambda x+(1-\lambda)y) \leq \lambda f(x)+(1-\lambda)f(y)<br /> \Leftrightarrow f(\lambda x+(1-\lambda)y) \leq \lambda M +(1-\lambda)M<br /> \Leftrightarrow f(\lambda x+(1-\lambda)y) \leq \lambda M +M-\lambda M<br /> \Leftrightarrow f(\lambda x+(1-\lambda)y) \leq M<br /> \end{eqnarray}$ Das heißt doch nun, dass meine Funktionswerte unter diesem Minimum M liegen. Das heißt, ich kann daraus doch auch folgern, dass meine Menge konvex ist oder denke ich falsch? Muss wirklich Gleichheit herrschen?
26.03.2018, 17:51	IfindU	Auf diesen Beitrag antworten »
Überlege mal: Kann der Funktionswert wirklich echt kleiner sein als das Minimum? Und ja, Gleichheit ist wichtig. $\begin{eqnarray} \{ f(x) = M + 1\} \end{eqnarray}$ ist im Allgemeinen nicht mehr konvex. Siehe $\begin{eqnarray} K = (-2,2) \end{eqnarray}$ , $\begin{eqnarray} f(x) = x^2 \end{eqnarray}$ . Dann ist $\begin{eqnarray} M= 0 \end{eqnarray}$ , wir haben $\begin{eqnarray} \{ f(x) = M \} = \{ 0\} \end{eqnarray}$ (konvex) und $\begin{eqnarray} \{ f(x) = M + 1\} = \{ -1, 1\} \end{eqnarray}$ nicht konvex.
Anzeige

26.03.2018, 18:03	LuciaSera	Auf diesen Beitrag antworten »
Stimmt.. das Minimum ist ja minimal.. Und ansonsten hätte ich etwas gefunden, das kleiner ist als das Minimum und dann wäre mein urpsrüngliches ja nicht mehr minimal. Das heißt $\begin{eqnarray} f(\lambda x+(1-\lambda)y) = M \end{eqnarray}$ , wenn ich nun richtig denke oder? Gilt das als Begründung: Entweder ist $\begin{eqnarray} f(\lambda x+(1-\lambda)y) = M \end{eqnarray}$ , dann bin ich fertig. Oder $\begin{eqnarray} f(\lambda x+(1-\lambda)y) < M \end{eqnarray}$ , doch dann wäre M nicht mehr mein Minimum sondern $\begin{eqnarray} f(\lambda x+(1-\lambda)y) \end{eqnarray}$ wobei ich wieder beim vorherigen wäre.
26.03.2018, 19:04	IfindU	Auf diesen Beitrag antworten »
Wichtig hier ist, dass die Menge konvex ist. Aber ja, im wesentlichen stimmt das.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »