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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

скорее, вот эту ссылку надо смотреть http://uchimatchast.ru/teory/mediana.php

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

Возможно, но механически совсем неочевидным.

Куда более наглядно единственность увидеть с помощью еще одной механической аналогии, не указанной в Википедии.

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

Аналогия хорошая, но из неё не следует выпуклость.

Математически строгое доказательство выпуклости состоит из двух утверждений:

1) Функция f(r)=|r-a| (r,a - вектора) выпукла.
2) Сумма выпуклых функция является выпуклой функцией.

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

>>но из неё не следует выпуклость.

Ну я как бы в курсе, я же и подчеркнул, что речь о визуализации единственности, а не выпуклости.

любопытно, а как из визуализации следует единственность?

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

Еще как причем. Без выпуклости можно засунуть численный метод нахождения в жопу.

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

Да, можно и так, даже проще вышло.

Никак не следует. Но в голове появляется надежный образ для обкатывания свойств.

Ну вы даёте. Если минимум единственен, то любой разумный метод будет к нему сходиться. При этом требование выпуклости совсем не обязательно.

>>Ну вы даёте.

Блин, мы же делаем вид что про единственность не знаем и доказываем её с помощью выпуклости.

>Ну вы даёте. Если минимум единственен, то любой разумный метод будет к нему сходиться. При этом требование выпуклости совсем не обязательно.

Да. Че-то я ступил совсем на ночь глядя.

>Да. Че-то я ступил совсем на ночь глядя.

Но в данном случае это используется в качесте достаточного условия сходимости.