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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Автор, а ты каким методом задачу решал?

Если не сложно, поделись кодом программы.

>Автор, а ты каким методом задачу решал?

Если не сложно, поделись кодом программы.

Я реализацией не заморачивался. Решал тупо в octave. Функция многовариантной минимизации fmincon

Если подробности все еще интересуют - могу написать.

У меня подобная задача была/есть, только три точки (задача Ферма/локационный треугольник/треугольник Лаунхардта (Вебера)). Я решал методом Ньютона, который эту задачу не решает, потом стал подыскивать квазиНьютоновские методы и тут научрук потребовал от меня свести эту задачу к линейной...