Fermat-Weber-Problem

24.10.2011, 19:49	Tobi_semseg	Auf diesen Beitrag antworten »
Fermat-Weber-Problem Meine Frage: Hey, ich soll zeigen dass das Fermat-Weber-Problem $\begin{eqnarray} \min f(x):=\sum\limits_{i=1}^m w_{i}\| \|x-a_{i} \| \| _{2} \end{eqnarray}$ wobei $\begin{eqnarray} f:\mathbb R ^{2}->\mathbb R, \\ w_{i}\in \mathbb R,\\ <br /> a_{i}\in \mathbb R ^{2} \end{eqnarray}$ stets eine Lösung besitzt. Meine Ideen: Ich muss also zeigen, dass stets ein Minimum existiert. Doch wenn ich versuche, den Gradienten zu bilden und 0 zu setzen, kann ich beide Gleichungen nicht nach x1 oder x2 auflösen, somit auch nicht testen, ob es sich um Minimum/a oder Maximum/a handelt. Hat jemand eine Idee, wie ich das vielleicht anders zeigen kann, dass stets eine Lösung hierfür existiert? Liebe Grüße, Tobi.
24.10.2011, 20:07	sergej88	Auf diesen Beitrag antworten »
Hallo, Betrachte die Abschätzung $\begin{eqnarray} f(x) = \sum \limits_{i=1}^{m}w_i\Vert x - a_i \Vert_2 \geq \sum \limits_{i=1}^{m}w_i \| \Vert x \Vert_2 - \Vert a_i \Vert_2\| \to \infty, \ \ \Vert x \Vert_2 \to \infty \end{eqnarray}$ Das heisst auf grossen Kugeln weit ausserhalb wird f sehr gross. Was heisst das für das Minimum und so weiter. Insbesondere darf man sich auf eine Kugel um den Ursprung beschränken, diese ist jedoch kompakt. (Hier natürlich unter der Annahme $\begin{eqnarray} w_i \geq 0 \end{eqnarray}$ ) Ist dieses nicht der Fall so gibt es im allgemeinen das Minimum sowieso nicht wie $\begin{eqnarray} f(x) = -\Vert x \Vert_2 \end{eqnarray}$ zeigt, also ( $\begin{eqnarray} m=1, w_1 = -1, a_1 = 0 \end{eqnarray}$ ) Oder fehlen dort andere Voraussetzungen? mfg
24.10.2011, 21:38	Tobi_semseg	Auf diesen Beitrag antworten »
Hey, also sorry die w_i sind >0 vorausgesetzt hatte ich vergessen. Ich verstehe die Abschätzung nicht, soll \|..\| außen wieder die 2-Norm sein? Wenn f weit außerhalb sehr groß wird, kann ein globales Minimum nur nahe der 0 erreicht werden. Wieso reicht es, eine Kugel um den Ursprung zu betrachten und wieso ist diese dann kompakt? Auf einem Kompaktum nimmt f sein globales Minimum an, damit hätte man eins.
25.10.2011, 10:25	sergej88	Auf diesen Beitrag antworten »
In etwa ja, Für eine Norm $\begin{eqnarray} \Vert \cdot \Vert \end{eqnarray}$ gilt immer die Abschätzung $\begin{eqnarray} \| \ \Vert x \Vert - \Vert y \Vert \| \leq \Vert x - y \Vert \end{eqnarray}$ Denn es ist ja $\begin{eqnarray} \Vert x \Vert = \Vert (x -y) + y\Vert \leq \Vert x - y \Vert + \Vert y \Vert \end{eqnarray}$ also $\begin{eqnarray} \Vert x \Vert - \Vert y \Vert \leq \Vert x - y \Vert \end{eqnarray}$ Machst du dasselbe mit x und y Vertauscht so bekommst du $\begin{eqnarray} \Vert y \Vert - \Vert x \Vert \leq \Vert x-y\Vert \end{eqnarray}$ welches zusammen den Normalen Betrag ergibt also das was oben bereits steht. Hast du jetzt diese Abschätzung so zeigst du wie bereits angegeben, dass f weit draussen gross wird. Daraus folgerst du, dass es iwan eine Kugel geben muss, sodass f in dieser Kugel das globale Minimum annimmt. Die Existenz des Minimums folgt da f stetig ist und eine abgeschossene Kugel als beschränkte Teilmenge nach .... kompakt ist. mfg

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »