Mehrdimensionale Extrema bestimmen

Question

Aufgabe:

Es seien n,k ∈ ℕ. Ferner seien x₁,...,x_n ∈ ℝⁿ . Bestimmen Sie den Extremwert von

\(f:\mathbb{R}^n \to \mathbb{R}, \, x\mapsto f(x)=\sum \limits_{i=1}^{k}||x-x_i||_{2}^2\)

Problem/Ansatz:

Kann mir jemand sagen, wie man so einen Ausdruck ableitet? Die groben Schritte bei der Aufgabe verstehe ich. Nur die Ableitung macht mir Schwierigkeiten.

Mit freundlichen Grüßen,

hexadezimal

Comments

Geht die Summe echt bis \( \infty\)?

---

Hallo,

eine Frage zum Problem: Ist der Faktor k nicht irgendwie überflüssig? Steht er wirklich da?

Eine Frage zur Lösung: Kennt Ihr "nur" partielle Ableitungen oder die allgemeine Definition von Ableitung ("totale ABleitung" oder "Frechet-Ableitung" oder....)?

Gruß

---

Geht die Summe echt bis ∞?

Meiner Meinung nach darf die Summe nur bis n laufen, ansonsten ist xi doch nicht definiert.

Da k konstant ist, lässt sich k als konstanter Faktor auch vor die Summe ziehen und konstante Faktoren beeinflussen das Maximum oder Minimum nicht.

Gesucht ist hier der Ortsvektor x bei dem Die Summe aller Abstandsquadrate zu den gegebenen n Vektoren minimal wird.

---

Es tut mir leid, da ist ein Fehler unterlaufen. Die Summe sieht so aus:

\( \sum\limits_{i=1}^{k}{} \) ||x - xi||²₂.

Wir haben uns nur mit der partiellen Ableitung beschäftigt.

Drop here!

---

Meiner Meinung nach darf die Summe nur bis n laufen, ansonsten ist xi doch nicht definiert.

Das ist mir bewusst, daher die Nachfrage.

Answer 1

$$f(x)=\sum \limits_{i=1}^{k}||x-x_i||_{2}^2=||x-x_1||_2^2+||x-x_2||_2^2+\cdots +||x-x_k||_2^2$$Leite jeden Term separat ab, dann folgt$$\operatorname{grad}f(x)=2\sum \limits_{i=1}^{k}x-x_i=0 \Longleftrightarrow x=\frac{1}{k}\sum \limits_{i=1}^{k}x_i$$ Wegen \(f(x)\to \infty\) muss \(f\) im \(\mathbb{R}^n\) ein globales Minimum besitzen. \(f\) nimmt also sein globales Minimum im arithmetischen Mittel an.

Comments

Das i vor der Summe, muss ein k sein,

ja, das Arithmetische Mittel ist der Wert, für den die Abweichungsquadrare zum Minimum werden. Was mich verwirrt hatte, war die Bedeutung der tief gestellten 2.  Wenn das k in der ursprünglichen Aufgabe ein

k _i gewesen wäre, hätte es sich um das gewogenen Mittel handeln können,

\( \frac{\sum\limits_{i=1}^{\m}{ki (x-x_i)}}{\sum\limits_{i=1}^{\m}{k_i}} \) 

Klappt leider nicht mit der Darstellung, nachdem ich die Summationsgrenze geändert hatte funktionierte die Vorschau nicht mehr.

---

Ich weiß nicht genau, was du mit mit "Das i vor der Summe, muss ein k sein" meinst.

Der Fragesteller hat sich berichtigt, vgl. Kommentare.

Die tiefgestellte 2 steht für die \(2\)-Norm, auch besser bekannt als die Euklidische Norm.

In der Analysis gibt es einen Oberbegriff für derartige Normen, die sogenannten p-Normen. Die Euklidische Norm ist p=2.

https://de.wikipedia.org/wiki/P-Norm

https://de.wikipedia.org/wiki/Euklidische_Norm

---

Vor deinem letzten Summenzeichen steht ein 1 / i ich denke 1 / k ist dort richtig.

---

Da hast du vollkommen recht, gut gesehen.

---

Mir ist es leider unmöglich die Ableitung noch den letzten Schritt nach zu vollziehen.

Müsste für das Minimum nicht zuerst die Hessematrix aufgestellt und dann auf ihre Definitheit untersucht werden?

$$ \text{Betrachte ich beispielsweise } ||x-x_1||^2_2 = \sum \limits_{j=1}^{k}|x_j-x_1|^2 \\ \text{Dann wäre meine Ableitung: } \\ 2|x_j-x_1| * \frac{x_j-x_1}{|x_j-x_1|}*...$$

"..." Da ich "meine" Ableitung gar nicht weiter betrachten muss um zu sehen, dass es ein Problem mit dieser gibt.

Wäre es möglich die Ableitung einmal genauer auszuführen?

---

Hallo,

nein, der Gradient muss gleich Null gesetzt werden. Das ist die notwendige Bedingung. Die hinreichende Bedingung ist die Definitheit der Hessematrix. Das habe ich aber durch folgendes Argument übergangen:

Wegen f(x)→∞ muss f im Rn ein globales Minimum besitzen.

Zur Ableitung:$$f(x)=\sum \limits_{i=1}^{k}||x-x_i||_{2}^2=||x-x_1||_2^2+||x-x_2||_2^2+\cdots +||x-x_k||_2^2$$ Ich picke mir jetzt mal einen Summanden raus, nehmen wir \(||x-x_1||_2^2\). Schreiben wir das genauer aus, steht da:$$||x-x_1||_2^2=\left(\sqrt{(x_1-x_1)^2+(x_2-x_1)^2+\cdots + (x_n-x_1)^2}\right)^2=(x_2-x_1)^2+\cdots + (x_j-x_1)^2+\cdots +(x_n-x_1)^2$$ Leitet man dies nach der \(j\)-ten Komponente partiell ab, so folgt \(\partial _j ||x-x_1||_2^2=2(x_j-x_1)\). Analog gilt das für alle anderen Summanden. Es gilt also:$$\partial_j f(x)=2(x_j-x_1)+2(x_j-x_2)+\cdots + 2(x_j-x_k)=2\sum \limits_{i=1}^{k}x_j-x_i$$ Der Gradient ist nun definiert über \(\operatorname{grad}f(x)=(\partial _  1f(x), ..., \partial _k f(x))\), d. h. es gilt:$$\operatorname{grad}f(x)=2\sum \limits_{i=1}^{k}x-x_i$$

---

Hallo,

ich damit habe ich es (fast) verstanden.

In der mir vorliegenden Definition hat die Euklidische Norm Betragsstriche innerhalb der Wurzel und ich verstehe noch nicht ganz, warum diese hier verschwinden.

---

Betragsstriche sind mir nicht bekannt, da ja quadriert wird. Die Summanden \(x_1^2,x_2^2,...\) sind alle größer gleich Null wegen des Quadrats.

---

Ah, du meinst vermutlich die komplexe Variante, vgl. hier

Die vorliegende Funktion ist aber reellwertig und damit so.

---

Nach kurzem Blick auf Wikipedia handelt es sich wohl um das Betragsquadrat, was mir die Frage dann auch beantwortet.

Zuletzt würde ich noch gerne sicherstellen, dass ich keinen dummen letzten Fehler gemacht habe. Die 2. Ableitung müsste doch 2*k sein, bzw. jeweils 2.

---

Du brauchst die 2. Ableitung nicht. Es ist ein globales Minimum, da \(f(x)\geq 0\) für alle \(x\in \mathbb{R}^n\). Das ist eine Konsequenz aus der Tatsache, dass alle Summanden \(||x-x_i||_2^2=\sum \limits_{i=1}^{k}\left|\left |x-x_i \right |\right |^2\geq 0\) nichtnegativ sind.

---

Vielen dank.