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

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

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

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 думать, как доказать. Но получилось. Спасибо!!

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

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

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

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

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