Abstand minimieren: Abstandsformel

Question

Ich schreibe ein Programm in C. Ich möchte eine Lösung finden, indem ich den Ausdruck

D1+D2+......+Dn

wobei Di die nach der Entfernungsformel berechneten Entfernungen zwischen 2 Punkten sind. Der obige Ausdruck ist in x & y Variablen

Jetzt werde ich diesen Ausdruck differenzieren und die Lösung finden. Mein Zweifel ist:

da in dem obigen Ausdruck alle Di's als Quadratwurzeln auftreten, was schwierig zu lösen ist. Also können wir stattdessen diesen Ausdruck lösen:

D1^2 + D2^2 + ......+ Dn^2

Wird die Antwort, die sich aus dem obigen Ausdruck ergibt, dieselbe sein wie die, die sich aus der Lösung des ursprünglichen Ausdrucks ergeben hätte?

Ich habe für einfache Testfälle wie n=2 geprüft. Das Ergebnis ist richtig. Stimmt das allgemein?

Wenn nicht, wie kann dieses Problem gelöst werden?

Answer 1

Selbst für 2d-Entfernungen gilt im Allgemeinen nicht, dass das Minimum von a^2 + b^2 befindet sich an der gleichen Stelle wie das Minimum von a + b . Das mag natürlich für einige sehr spezifische, begrenzte Probleme zutreffen. Wenn Sie versuchen, ein Gegenbeispiel zu finden, beachten Sie, dass die Quadrate lange Strecken überpenalisieren; wenn Sie ein Beispiel mit einem Minimum konstruieren, das mindestens eine lange Strecke enthält, haben Sie eine gute Chance, dass die Summe der Quadrate ein anderes Minimum hat.

Was ist das Problem, das Sie zu lösen versuchen? Es ist durchaus möglich, dass für Ihr Problem die Unterscheidung keine Rolle spielt oder dass das Minimum der Quadratsumme ein billigeres Problem und eine einfachere erste Annäherung an eine endgültige Lösung ist.

Es mag offensichtlich sein, aber wenn die verschiedenen Entfernungen Unabhängig dann ist für jeden einzelnen Abstand das Quadrat minimal, wenn der Abstand gleich ist, und somit ist die Summe der unverbundenen Abstände minimal, wenn die Summe der Quadrate gleich ist.

Edit Post update: Sie versuchen, einen Schwerpunkt mit der Einschränkung zu finden, dass er auf einer bestimmten Linie liegt. In allgemeinen Umrissen: Sie haben nur einen Freiheitsgrad und können einfach differenzieren. Allerdings wird das Ergebnis eine Summe von Brüchen mit sqrt im Nenner sein; das algebraisch zu lösen ist im allgemeinen Fall nicht möglich (AFAIK). Ich bin mir nicht 100%ig sicher, aber ich denke, Sie haben Glück, denn Ihre Abstandssumme hat kein lokales Minimum außer dem globalen; in diesem Fall konvergiert die Newton-Methode zuverlässig und schnell.

Wenn Sie also die Annahme verifizieren können, dass es nur ein lokales Minimum gibt, sind Sie auf der sicheren Seite, und selbst wenn das der Fall ist, können Sie ziemlich zuverlässig ein gutes Ergebnis erzielen und Folgendes feststellen wenn Wenn Sie das mit der Newton-Methode berechnete Minimum mit einigen Punkten vergleichen, die der Realität entsprechen (z. B. die orthogonale Projektion jedes Punktes auf die Linie), geht es schief.

Answer 2

Sie haben nicht genug getestet. Minimierung D1 + D2 ist nicht dasselbe wie die Minimierung D1^2 + D2^2 im Allgemeinen, auch wenn es für einige bestimmte D1 y D2 .

EDIT nachdem Sie mich daran erinnert haben, dass Sie nur an den Entfernungen im Flugzeug interessiert sind:

In dem Fall, dass D1 y D2 sind Abstände in der geometrischen Ebene, wobei der Punkt in der Ebene, der die D1^2 + D2^2 minimiert auch D1 + D2 aber er scheitert an drei Punkten.

Versuchen Sie es mit den drei Punkten (0,0), (1,0) und (10, 0): Minimierung |x|+|x-1|+|x-10| ist nicht dasselbe wie die Minimierung x^2+(x-1)^2+(x-10)^2

Answer 3

Sie sind etwas unklar, was den Ursprung Ihrer D1, D2, ... Dn angeht, aber ich nehme an, dass Sie eine Reihe von Punkten P1, P2, ..., Pn in der x-y-Ebene haben und den Punkt p0=(x0,y0) finden wollen, der die Summe der Abstände zwischen jedem Punkt P1... Pn und p0 minimiert.

Also Ihr D1. Dn sind eigentlich:

D1 = sqrt((x0-x1)^2 + (y0-y1)^2)
D2 = sqrt((x0-x2)^2 + (y0-y2)^2)
..
Dn = sqrt((x0-xn)^2 + (y0-yn)^2)

どこ x1 .. xn y y1 ... yn bekannt sind und x0, y0 sind unbekannt. Und Sie wollen so wenig wie möglich D0 :

D0 = D1+D2+......+Dn

Wenn dies richtig ist, müssen Sie die Geometrischer Median . Der Wikipedia-Artikel sollte Ihnen helfen, eine Lösung zu finden.

Aktualisierung: Sie erklären in einem Kommentar, dass Punkt P0 auf einer bestimmten Linie liegen sollte (bitte fügen Sie dies Ihrer ursprünglichen Problemstellung hinzu). Das heißt, Sie können umschreiben y0 in Abhängigkeit von x0 :

y0 = a*x0 + b

wobei a und b gegeben sind. Dies reduziert die Komplexität Ihrer Abstandsfunktionen und macht die Ableitung zu einer ernsthaften Möglichkeit.

D1 = sqrt((x0-x1)^2 + (ax0+b-y1)^2)
D2 = sqrt((x0-x2)^2 + (ax0+b-y2)^2)
..
Dn = sqrt((x0-xn)^2 + (ax0+b-yn)^2)

Aber wenn die Anzahl der Punkte n nicht zu groß ist, würde ich in dem Bereich der Linie, in dem x nahe am Mittelwert von x1 xn liegt, eine rohe Suche* durchführen, um den Punkt x-, y0 zu finden, der D0 minimiert.

Answer 4

Gegenbeispiel:

d1=1 & d2=10 (sum=11 & sumOfSquares=101)

d1=6 & d2=6 (sum=12 & sumOfSquares=72)

Die Summe stieg, aber die Summe der Quadrate sank.

Answer 5

Ihr Problem ist die Minimierung einer Zielfunktion, die durch eine Norm Ihrer Abstände gegeben ist. Die Abstände sind euklidisch und stellen somit die euklidische Norm zwischen zwei Vektoren dar. Um den Unterschied zwischen der Minimierung von Summe(ai) und Summe(ai^2) zu verstehen, empfehle ich Ihnen die Lektüre der Wikipedia-Eintrag zu Normen Unterm Strich ist Folgendes zu beachten:

||x||2       <= ||x||1 <= sqrt(n)||x||2
||x||_\infty <= ||x||2 <= sqrt(n)||x||_\infty
||x||_\infty <= ||x||1 <=       n||x||_\infty

Wo ||x||2 ist die euklidische Norm, ||x||1 でございます sum(abs(x1)+abs(x2)+...+abs(xn)) und ||x||_\infty でございます max(abs(x1),abs(x2),...,abs(xn)) . In Ihrem Fall sind alle Zahlen positiv (Sie haben bereits die euklidische Norm, so dass Sie den Unterschied sehen können.

Es kann auch hilfreich sein (auch wenn es viel schwieriger ist, es vollständig zu verstehen), das fantastische Buch von Golub und Van Loan zu lesen, Matrix-Berechnungen .