Задана система датчиков в точках $x_i\in {\mathbb{R}}^2$ с положительными весами $w_i>0$. Требуется найти точку $x\in {\mathbb{R}}^2$, минимизирующую суммарное взвешенное расстояние
$$f(x)=\sum _i{w}_i\Vert x-x_i\Vert .$$
Геометрический критерий (условие равновесия)
- Внутренняя точка-минимум $x\notin \{x_i\}$ удовлетворяет уравнению равновесия векторов сил
$$\sum _i{w}_i\frac{x-x_i}{\Vert x-x_i\Vert }=0.$$ Это означает, что векторы от искомой точки к датчикам, нормированные и умноженные на веса, компенсируют друг друга.
- Если оптимум совпадает с некоторым датчиком $x_j$, то субградиентное условие даёт критерий
∥∑i≠jwixj−xi∥xj−xi∥∥≤wj. \Big\|\sum_{i\ne j} w_i\frac{x_j-x_i}{\|x_j-x_i\|}\Big\|\le w_j.
i=j∑ wi ∥xj −xi ∥xj −xi ≤wj .
Свойства
- Функция $f$ выпукла; при том, если точки не лежат на одной прямой, минимум единственен.
- Вырожденные частные случаи:
- Для трёх точек и равных весов: если все углы треугольника меньше $120^{\circ }$, оптимум — точка Ферма (Торричелли), образующая углы $120^{\circ }$ между лучами к вершинам; если есть угол $\ge 120^{\circ }$, оптимум — соответствующая вершина.
- Для точек на одной прямой задача сводится к одномерному случаю; оптимум — взвешенная медиана, минимизирующая сумму модулей отклонений.
- Центр масс $\bar{x}=\frac{{\sum }_i{w}_i{x}_i}{{\sum }_i{w}_i}$ минимизирует сумму взвешенных квадратов расстояний ${\sum }_i{w}_i\Vert x-x_i{\Vert }^2$, но не сумму модулей; поэтому центр масс — не решение данной задачи в общем случае.
Методы построения / вычисления
- Итеративный метод Вайцфельда (Weiszfeld):
$$x^{(k+1)}=\frac{{\sum }_i{w}_i\frac{x_i}{\Vert x^{(k)}-x_i\Vert }}{{\sum }_i{w}_i\frac{1}{\Vert x^{(k)}-x_i\Vert }}.$$ При достижении $x^{(k)}=x_j$ требуется модификация (избежать деления на ноль) или проверка субградиентного условия; модифицированные версии обеспечивают сходимость к глобальному минимуму для положительных весов (при обычных условиях).
- Альтернативы: градиентные/субградиентные методы, методы выпуклой оптимизации и геометрические построения для малого числа точек (для трёх точек — классические геометрические конструкции точки Ферма).
Краткое заключение
- Геометрический критерий: в точке минимума векторная сумма взвешенных единичных векторов к датчикам равна нулю (или выполняется указанная неравенство при совпадении с датчиком).
- Практический метод: итерация Вайцфельда с обработкой вырожденных случаев; задача выпукла, решение обычно единственно и вычисляется эффективно.