Минимизация расстояния: формула расстояния

Question

Я пишу программу на C. Я хочу найти решение путем минимизации выражения

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

где Di - расстояния, рассчитанные по формуле расстояния между 2 точками. Вышеупомянутое выражение в переменных x & y

Теперь я дифференцирую это выражение и найду решение. Мое сомнение:

, так как в вышеприведенном выражении все Di будут представлены в виде квадратных корней, которые будет трудно решить. Таким образом, вместо этого мы можем решить для этого выражения:

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

Будет ли ответ, полученный с помощью вышеприведенного выражения, таким же, как и ответ на исходный вопрос?

Я проверил простые тестовые случаи, такие как n = 2. Это дает правильный ответ. Это правда в целом?

Если нет, то как решить эту проблему?

Answer 1

Даже для двумерных расстояний, как правило, не верно, что минимум a^2 + b^2 находится в том же месте, что и минимум a + b. Конечно, это может быть верно для некоторого очень специфического ограниченного набора проблем. Если вы пытаетесь найти контрпример, обратите внимание, что квадраты чрезмерно перенапрягаются на большие расстояния; если вы построите пример с минимумом, содержащим хотя бы одно большое расстояние, у вас есть хороший шанс, что сумма квадратов будет иметь другой минимум.

Какую проблему вы пытаетесь решить? Вполне возможно, что для вашей проблемы различие не имеет значения, конечно; или что минимум суммы квадратов является более дешевой задачей и более простым первым приближением к окончательному решению.

Это может быть очевидно, но если различные расстояния не связаны , то для каждого отдельного расстояния квадрат минимален, когда расстояние равно, и, таким образом, сумма несвязанных расстояний минимальна, когда сумма квадратов есть.

Редактировать сообщение Обновление: Вы пытаетесь найти центроид с ограничением, которое лежит на определенной линии. Тогда в общих чертах: у вас есть только одна степень свободы, и вы можете провести простую дифференциацию. Тем не менее, результат будет иметь сумму дробей с sqrt в знаменателе; решить это алгебраически в общем случае невозможно (AFAIK). Я не уверен на 100%, но я думаю, что вам повезло в том, что ваша дистанционная сумма не имеет локального минимума, кроме глобального; в этом случае метод Ньютона будет быстро и надежно сходиться.

Итак, если вы можете проверить предположение, что существует только один локальный минимум, вы свободны дома, и даже если вы можете, вы можете достичь довольно хорошего результата довольно надежно и обнаружить , когда это идет не так просто, сравнивая вычисленный минимум по методу Ньютона с несколькими точками проверки реальности (скажем, ортогональной проекцией каждой точки на линию).

Answer 2

Вы немного неясны относительно происхождения ваших D1, D2, .. Dn, но я предполагаю, что у вас есть набор точек P1, P2, ..., Pn в плоскости xy, и вы хотите найти точку p0 = (x0, y0), который минимизирует сумму расстояний между каждой точкой P1 .. Pn и p0.

Итак, ваш D1 .. Dn на самом деле:

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 и y1 ... yn известны, а x0, y0 неизвестны. И вы хотите минимизировать D0:

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

Если это правильно, то вы хотите найти Геометрическую медиану . Статья в Википедии должна помочь вам найти решение.

Обновление: в комментарии вы утверждаете, что точка P0 должна лежать на заданной строке (пожалуйста, добавьте это в исходное описание проблемы). Это означает, что вы можете переписать y0 как функцию x0:

y0 = a*x0 + b

где даны a и b. Это уменьшает сложность ваших дистанционных функций и делает деривацию серьезной возможностью.

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)

Но если количество точек n не слишком велико, я бы просто провел поиск грубой силы * в области линии, где x близко к среднему значению x1 .. xn, чтобы найти точку x- , y0, который минимизирует D0.

Answer 3

Вы недостаточно протестировали. Минимизация D1 + D2 - это не то же самое, что минимизация D1^2 + D2^2 в целом, хотя может быть для некоторых конкретных D1 и D2.

РЕДАКТИРОВАТЬ после того, как вы напомнили мне, что вас интересуют только расстояния в плоскости:

В случае, когда D1 и D2 являются расстояниями в геометрической плоскости, точка на плоскости, которая минимизирует D1^2 + D2^2, также минимизирует D1 + D2, но оно разбивается на три части.

Попробуйте это с тремя точками (0,0), (1,0) и (10, 0): Минимизация |x|+|x-1|+|x-10| - это не то же самое, что минимизация x^2+(x-1)^2+(x-10)^2

Answer 4

Ваша проблема - минимизация целевой функции, заданной некоторой нормой ваших расстояний. Расстояния евклидовы, и как таковые представляют евклидову норму между двумя векторами. Чтобы понять разницу между минимизацией суммы (ai) и суммы (ai ^ 2), я рекомендую прочитать запись Википедии по нормам ; нижняя строка, обратите внимание на следующее:

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

Где ||x||2 - евклидова норма, ||x||1 - sum(abs(x1)+abs(x2)+...+abs(xn)) и ||x||_\infty - max(abs(x1),abs(x2),...,abs(xn)). В вашем случае все числа положительны (у вас уже есть евклидова норма, поэтому вы можете увидеть разницу.

Также может быть полезно (хотя гораздо труднее полностью понять) прочитать фантастическую книгу Голуба и Ван Лоан, Матричные вычисления .

Answer 5

контрпример:

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

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

Сумма увеличилась, но сумма квадратов уменьшилась.