[матан] сумма расстояний

Тупо перебором N*(N-1) циклов :)

Найти все минимумы и посчитать фунцию в них?

А не вы ли недавно эту же задачку приводили и спрашивали, как быстрее найти нужную точку? И совет был - искать центр тяжести множества точек, а потом перебирать только точки вблизи него?..

Их можно найти только численно. А значит, что ты не знаешь все нашел или нет. Задача - найти минимум. Численно его найти легко. А вот как доказать, что он единственный?

>А не вы ли недавно эту же задачку приводили и спрашивали, как быстрее найти нужную точку? И совет был - искать центр тяжести множества точек, а потом перебирать только точки вблизи него?..

Да-да. Было. Но теперь проблема не найти, а доказать, что это он и есть.

Сложновато это будет, знаете ли... Численными методами намного проще, нежели аналитически.

Только перебор N*(N-1) расстояний. Больше никак, наверное...

>Сложновато это будет, знаете ли... Численными методами намного проще, нежели аналитически.

вопрос не в поиске, а в утверждении, что если точка найдена, то она единственна.

А точка и не должна быть единственной.

>А точка и не должна быть единственной.

Прикол в том, что она таки единственная.

>Прикол в том, что она таки единственная.

наверное...

Надо график построить.

М-м-м, может туплю, но хочется наугад сказать, что сумма расстояний до точки — выпуклая функция. Надо думать, это уже опровергнуто?

Если пораскинуть мозгами, в симметричных случаях точек может быть несколько. Возьмем, к примеру, точки, расположенные на пересечении нескольких симметричных лучей, проведенных из центра концентрических окружностей. По идее, все точки внутренней окружности подпадают под требования минимума суммы расстояний до остальных точек.

>М-м-м, может туплю, но хочется наугад сказать, что сумма расстояний до точки — выпуклая функция. Надо думать, это уже опровергнуто?

Это скорей всего так. Но как доказать?

через вторые частные производные чтоли?

>Если пораскинуть мозгами, в симметричных случаях точек может быть несколько. Возьмем, к примеру, точки, расположенные на пересечении нескольких симметричных лучей, проведенных из центра концентрических окружностей. По идее, все точки внутренней окружности подпадают под требования минимума суммы расстояний до остальных точек.

Не совсем понимаю.

> через вторые частные производные чтоли?
Я другого способа не знаю, кроме как проверять матрицу из вторых производных на положительную определенность. Попробовал на листике, но мотивации не хватило. :)

См. рисунок в левом верхнем углу

возьми тогда два перпендикулярных луча. Точка минимума будет как раз посерединке. Все остальные будут давать большое значение.

>Я другого способа не знаю, кроме как проверять матрицу из вторых производных на положительную определенность. Попробовал на листике, но мотивации не хватило. :)

так жесть получается.

Ну, я имел в виду, что точка минимума не обязательно должна быть единственной. Все зависит от общей конфигурации.

но в твоем примере совершенно не очевидно, что эта точка не единственна.

PS построил только что график. Функция выпукла. Shit...

Единственность такого минимума сразу следует из геометрического смысла. Ведь это точка, из которой направления на точки множества образуют правильный N-угольник.

В какой бы сектор мы ни сдвинули пробную точку, размах соответствующих отрезков будет больше чем 360/N.

Про выпуклость замечание metar очень дельное, но доказать сходу трудно.

>Единственность такого минимума сразу следует из геометрического смысла. Ведь это точка, из которой направления на точки множества образуют правильный N-угольник.

Интересно. А почему именно так?

есть контрпример для центра масс?

>>Интересно. А почему именно так?

Да, точно, я все-таки всех жестоко обманул. Не ведитесь.

>Да, точно, я все-таки всех жестоко обманул. Не ведитесь.

угу. Проверил на примере. Это не верно.

центр масс минимизует квадрат расстояния (если все точки равной массы)

>есть контрпример для центра масс?

а причем тут центр масс?

Вот. точка найдена численным методом. Построил лучи. может у кого-то идеи будут по этому поводу...

http://ompldr.org/vOG0wcA

У меня получается, что при одной фиксированной координате для второй частная производная равна нулю на некотором отрезке. То есть варьируя ее получаем область ограниченную двумя кривыми (зависимость непрерывная?). Делаем тоже самое по второй координате, пересекаем, получается одна связная область. Мог что-то не учесть, я с первого раза редко верно нахожу решение.

А вот график. Видно, что функция выпукла. Множество взято из 20 точек (то же, что и на предыдущей картинке.

http://ompldr.org/vOG0wcQ

первая производная по x получилась:

sum((x-x_i)/sqrt((x-x_i)²+(y-y_i)²))

Как ты доказал, что это равно нулю лишь в единственном x при фиксированном y?

Для начала нужно заметить, что это точка не обязательно должна быть единственной. Пример банальный: множество из двух точек. Каждая точка отрезка их соединяющего минимизирует сумму расстояний.

Еще несложно понять, что если метрика порождена нормой, то заданная функция будет нестрого выпуклой. Другими словами

f (a * x1 + (1-a) * x2) <= a * f (x1) + (1-a) * f (x2)

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

>Пример банальный: множество из двух точек. Каждая точка отрезка их соединяющего минимизирует сумму расстояний.

Это лишь в случае, если точки лежат на одном отрезке. То есть в подпространстве R². А значит и обобщить нельзя никак.

(получится правило треугольника),

Точнее модуль суммы меньше или равен суммы модулей.

>Для доказательства можно выписать неравенство для каждой точки отдельно (получится правило треугольника), а потом их просуммировать.

Хм. А ты уверен, что получится? Я этот метод отбросил заранее. Показалось, что безнадега.

Когда найдёте — скажите пжлст, будет ли эта точка заодно и центром масс.

>Когда найдёте — скажите пжлст, будет ли эта точка заодно и центром масс.

Могу сразу сказать - не будет.

А ты уверен, что получится?

|c + a* x1 + (1-a) * x2| <= a * |c - x1| + (1-a) |c - x2|

Разве это не тривиально?

Это лишь в случае, если точки лежат на одном отрезке. То есть в п

подпространстве R². А значит и обобщить нельзя никак.

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

>Разве это не тривиально?

Хм. Мне пришлось минут 15 думать, как доказать. Но получилось. Спасибо!!

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

гугл нашёл ответ за две секунды.

http://en.wikipedia.org/wiki/Geometric_median

По ссылке ответы на все Ваши вопросы

Википедия ссылается на статьи в журналах. Если понадобится, но я смогу достать их электронные копии.

Там доказательства выпуклости нет. Но уже доказали. Спасибо ival. Надо вики поправить на эту тему.

Зато там написано, что

The geometric median is unique whenever the points are not collinear.

А также указан эффективный способ нахождения минимума. А выпуклость в этой задаче совсем не при чем.

Небольшая коррекция:

|c - (a* x1 + (1-a) * x2)| <= a * |c - x1| + (1-a) |c - x2|

с - радиус-вектор точки множества, x1 и x2 - радиус-векторы двух пробных точек плоскости.

А так - красиво, четко, чего тут скажешь.

>>А выпуклость в этой задаче совсем не при чем.

А единственность решения откуда возьмется? Википедия это хорошо, но тут тов. ival непосредственно показал.

> А единственность решения откуда возьмется? Википедия это хорошо, но тут тов. ival непосредственно показал.

Это математическая теорема. Несложно найти в литературе её доказательство.

Откровенно говоря, доказательство ival'а выпуклости суммы расстояний как функции положения точки я не понял.

Извиняюсь, утверждение о выпуклости оказалось элементарным.