Везде
On the geometric median and other median-like points
Table of contents
Annotation Estimate Publication content
References Comments
Share
QR
Metrics
On the geometric median and other median-like points
Annotation
PII
S042473880010498-6-1
DOI
10.31857/S042473880010498-6
Publication type
Article
Status
Published
Authors
Peter Panov 
Occupation: Senior Lecturer,
Affiliation:
Higher School of Economics

Address: Moscow, Russia
Aleksei Savvateev
Occupation: Professor,
Affiliation:
Central Economics and Mathematics Institute, Russian Academy of Sciences
Adygeya StateUniversity
Dmitry Pozharsky University
Moscow Institute of Physics and Technology (State University)

Address: Russia
Edition
Volume 56 Issue 3
Pages
145-152
Abstract

 

The geometric median and some of its generalizations are widely used in economic theory, starting with the works of Wilhelm Launhardt and Alfred Weber on location theory.The most important property of the median of a numerical sample is that the median minimizes the sum of the distance to all elements of the sample.This minimizing property is the basis for determining the geometric median for finite sets of points on the plane.This definition is easily transferred to any metric space, including the Euclidean space Rn. Using integration, the concept of a geometric median extends to bounded submanifolds of any dimension inRn.There are effective numerical methods for finding the geometric median, but there are no General analytical formulas for calculating it. In this paper, we focus on the geometric medians of bounded domains located in the Euclidean space Rn.The main new results obtained in our work include the conclusion of a new convenient representation of the gradient system for finding the geometric median, as well as the extension of this approach to a wide class of similar optimization problems, where the distance function is replaced by functions of a more general form. It is the solutions to these problems that we call median-like points. They are the closest relatives of the geometric median and are also widely used in modern economic studies.

 

 

Keywords
geometric median, domain, triangular domain, gradient system, critical point.
Received
10.07.2020
Date of publication
04.09.2020
Number of purchasers
27
Views
1593
Readers community rating
0.0 (0 votes)
Cite   Download pdf
1 1. ВВЕДЕНИЕ
2 Напомним, что геометрической медианой конечного набора точек, расположенных в евклидовом пространстве Rn , называется точка  m∈Rn , суммарное расстояние от которой до точек набора минимально, т.е.
3 m=arg minX∈Rn∑i=1kPi-X. (1)
4 Первая задача о геометрической медиане была сформулирована Пьером Ферма в 1643 г. для случая n=2,    k=3, она была решена Еванджелиста Торричелли в 1646 г. (Fermat–Torricelli problem, 2019). При n=1 , когда мы имеем дело с набором чисел P1,  ...,  Pk , нетрудно проверить, что статистическая медиана m этого набора (выборки) удовлетворяет соотношению (1).
5 Геометрическая медиана и ее непосредственные обобщения активно использовались экономистами в теории размещения производства, начиная с XIX в. (Launhardt, 1882; Weber, 1909; Weber problem, 2012). Параллельно с экономическими приложениями проводились математические исследования свойств геометрической медианы конечных наборов точек и разрабатывались эффективные численные методы для ее нахождения (Wesolowsky, 1993). Ближе к нашему времени интерес исследователей смещается в сторону непрерывного случая — развиваются исследования, связанные с геометрическими медианами кривых и областей (Fekete, Mitchell, Beurer, 2005; Zhang, Carlsson, 2014; Savvateev, Sorokin, Weber, 2015; Панов 2017).
6 После этого краткого исторического экскурса дадим необходимые определения и коротко опишем основные результаты настоящей работы, являющиеся обобщением некоторых результатов, изложенных в статье (Панов, 2018). По аналогии с определением (1), геометрическая медиана ограниченной области Ω , расположенной в евклидовом пространстве Rn , определяется как точка m , являющаяся решением минимизационной задачи
7 m=arg minX∈Rn∫P∈ΩP-XdP, (2)
8 где P-X — обычное евклидово расстояние между точками X и P . Таким образом, геометрическая медиана — это точка в Rn , которая минимизирует суммарное расстояние от себя до всех точек области Ω (Fekete, Mitchell, Beurer, 2005; Savvateev, Sorokin, Weber, 2015). Существуют эффективные численные, в том числе градиентные, методы отыскания геометрической медианы (Zhang, Carlsson, 2014). В то же время общие аналитические формулы для ее вычисления отсутствуют.
9 Известно, что при n>1 для любой ограниченной области Ω в Rn  геометрическая медиана существует и она единственна (Kemperman, 1987). Таким образом, при n>1 медиана совпадает с единственной точкой X∈Rn , которая является решением градиентного уравнения ∇X∫P∈ΩP-XdP=0. В силу векторной природы данное уравнение называют градиентной системой. А так как ∇XP-X=X-P/P-X, эту градиентную систему можно записать и в виде
10 ∫P∈ΩX-PP-XdP=0. (3)
11 Мы предлагаем использовать для вычисления геометрической медианы другую, в некоторых случаях более удобную, форму записи градиентной системы (3), которая по крайней мере снижает кратность интеграла, необходимого для составления этой системы:
12 ∫P∈∂ΩP-Xn→PdP=0, (4)
13 где Ω — это ограниченная область с кусочно-гладкой границей, n→P — единичный нормальный вектор к границе ∂Ω в точке P .
14 Доказательство того, что геометрическая медиана является решением этого уравнения (теорема 3), — один из главных результатов настоящей работы. Мы продемонстрируем здесь индуктивный геометрический подход к доказательству этого утверждения, начиная с плоского случая и с треугольных и многоугольных областей. Затем мы обсудим распространение этого результата на другие медианоподобные точки, часто используемые в экономических исследованиях.
15 Пусть f — непрерывная функция аргумента P∈Rn . Для области Ω рассмотрим минимизационную задачу
16 mf=arg minX∈Rn∫P∈ΩfP-XdP. (5)
17 Оказывается, здесь работают те же аргументы, что и в случае геометрической медианы. Можно доказать (см. теорему 4), что точка mf является одним из решений уравнения ∫P∈∂ΩfP-Xn→PdP=0. В дальнейшем нам будет удобно использовать другую запись определений (2) и (5). Поэтому для заданной области Ω введем в рассмотрение функцию
18 ΣΩX=∫P∈ΩP-XdP (6)
19 и определим геометрическую медиану области Ω , как
20 m=arg minX∈RnΣΩX. (7)
21 Аналогично, положим ΣΩfX=∫P∈ΩfP-XdP, тогда можно записать
22 mf=arg minX∈RnΣΩfX. (8)
23 Приведем здесь несколько примеров, показывающих необходимость рассмотрения обобщенной оптимизационной задачи (5). Во-первых, в случае fP=P решением этой задачи будет геометрическая медиана области Ω . Далее, для fP=P2 , как в этом нетрудно убедиться, в качестве решения задачи (8) мы получаем центроид области Ω , т.е. ее центр масс. Кроме того в экономических исследованиях часто используется манхэттенское расстояние, соответствующее fP=∑i=1nPi , а также и другие метрики Минковского, соответствующие fP=∑i=1nPip1/p, для которых задача (8) тоже актуальна.
24 2. ГЕОМЕТРИЧЕСКАЯ МЕДИАНА ТРЕУГОЛЬНОЙ ОБЛАСТИ
25 В этом разделе мы обсудим свойства геометрической медианы простейшей двумерной, а именно треугольной, области. Треугольную область будем обозначать Δ , а ее вершины – P1,  P2,  P3 . Согласно определению (7) геометрическая медиана Δ вычисляется как m=arg minX∈R2ΣΔX, где ΣΔX=∫P∈ΔP-XdP.
26 Пусть P1 и P2 — некоторые точки на плоскости, по аналогии с (6) введем обозначение ΣP1P2X=∫P∈P1P2P-XdP, где интегрирование ведется по отрезку P1P2 . Заметим, что среднее расстояние от точки X до точек отрезка P1P2 равно ΣP1P2X/P2-P1 .
27 Теорема 1. Точка m=X тогда и только тогда будет геометрической медианой треугольной области Δ с вершинами P1,  P2,  P3 , когда выполняется равенство
28 ΣP1P2XP2-P1P1P2→+ΣP2P3XP3-P2P2P3→+ΣP3P1XP1-P3P3P1→=0. (9)
29 Доказательство. Из определения (7) следует, что геометрическая медиана m —критическая точка функции ΣΔ . Возьмем малый вектор δ→,    δ→=δ и вычислим приращение функции ΣΔ при смещении аргумента на этот вектор δΣΔX=ΣΔX+δ→-ΣΔX. В критической точке m оно должно иметь порядок oδ .
30 Положим P'i=Pi-δ→ и обозначим через Δ' сдвинутый на вектор -δ→ треугольник со штрихованными вершинами (рис. 1, знаки «+» и «–» соответствуют знакам, с которыми слагаемые ΣπiX входят в приращение δΣΔX ). На рис. 1 показано, что при смещении аргумента на вектор  δ→ мы можем записать приращение функции ΣΔ в виде δΣΔX=ΣΔ'X-ΣΔX.
31

Рис. 1. Исходный треугольник и его параллельный сдвиг
32 Обозначим параллелограмм с вершинами Pi,  Pi+1,  P'i,  P'i+1 через πi , а его площадь через |πi| . Тогда приращение функции ΣΔ представляется суммой трех слагаемых вида ΣπiX , взятых с подходящими знаками. Причем при δ→0 средние значения интегралов ΣπiX и ΣPiPi+1X сближаются друг с другом, а именно:
33 ΣπiX|πi| =ΣPiPi+1XPi+1-Pi+o1.
34 Вопрос о знаке, с которым слагаемое ΣπiX должно входить в приращение δΣΔX , решается следующим образом. Умножим обе части предыдущего равенства на ориентированную площадь параллелограмма πi , а именно на -δ→∧PiPi+1→ :
35 -δ→∧PiPi+1→πiΣπi=-δ→∧PiPi+1→ΣPiPi+1(X)Pi+1-Pi+o(δ).
36 Нетрудно проверить (см. рис. 1), что дробь, стоящая перед ΣπiX , определяет искомый знак. Таким образом,
37 δΣΔ(X)=-δ→∧ΣP1P2(X)P2-P1P1P2→+ΣP2P3(X)P3-P2P1P2→+ΣP3P1(X)P2-P1P1P2→+o(δ). (10)
38 Мы видим, что приращение δΣΔX в точке X в том и только в том случае будет иметь порядок oδ , когда выражение в скобках будет равно нулю.▄
39 Замечание 1. На самом деле соотношение (10) говорит о том, что вектор, расположенный в скобках, — это градиент функции ΣΔX , повернутый на -90° . Так что уравнение  (9) — это всего лишь удобная запись градиентной системы ∇ΣΔX=0 для нахождения геометрической медианы треугольной области Δ .
40 Градиентную систему (9) можно записать в более компактном и симметричном виде, так как из теоремы 1 вытекает следующее утверждение.
41 Предложение 1 (характеристическое свойство геометрической медианы треугольной области). Точка m=X тогда и только тогда будет медианой треугольной области Δ с вершинами P1,    P2,    P3  , когда выполняется соотношение
42 ΣP1P2XP2-P1=ΣP2P3XP3-P2=ΣP3P1XP1-P3. (11)
43 Таким образом, геометрическая медиана треугольной области — это точка, для которой три средних расстояния до трех сторон граничного треугольника равны между собой.
44 Доказательство. В треугольнике одну из сторон выразим через две другие P3P1→=-P1P2→-P2P3→ , тогда для него равенство (10) можно переписать в виде
45 ΣP1P2XP2-P1-ΣP3P1XP1-P3P1P2→+ΣP2P3XP3-P2-ΣP3P1XP1-P3P2P3→=0.
46 Из-за независимости векторов P1P2→ и P2P3→ следует, что соответствующие им коэффициенты должны быть равны 0 и, значит, соотношение (11) в критической точке выполняется. ▄
47 Замечание 2. Отметим, что все интегралы вида ΣPQX , содержащиеся в градиентных системах (9) и (11), вычисляются в элементарных функциях (Zhang, Carlsson, 2014; Панов, 2018).
48 Сейчас мы используем доказанное здесь характеристическое свойство для точного вычисления геометрической медианы для одного очень узкого класса треугольников. Рассмотрим вырожденный случай, в котором градиентная система решается в явном виде — это случай сплюснутого треугольника. Речь идет о треугольнике со сторонами α,    β,    γ, в котором γ=α-β , и имеется в виду следующее утверждение, являющееся следствием предложения 1.
49 Следствие 1. Рассмотрим семейство треугольников со сторонами α,    β,    γ, , где две большие стороны α и β фиксированы, а меньшая γ — является параметром. Обозначим геометрическую медиану области, ограниченной этим треугольником mγ . Пусть теперь γ стремится к α-β , тогда mγ стремится к точке m , которая отстоит от общей вершины сторон α и β на расстояние αβ/2 .
50 Это утверждение является простым следствие соотношения (11), примененного непосредственно к сплюснутому треугольнику со сторонами и γ=α-β , для которого оно имеет смысл, хотя само понятие геометрической медианы для его внутренности не совсем определено по причине отсутствия этой внутренности.
51

Доказательство. Расположим сплюснутый треугольник, как показано это на рис. 2. Рис. 2. Сплюснутая треугольная область
52 Медиана m этого треугольника лежит на отрезке 0,  minα,    β. Для ее вычисления воспользуемся формулой (11), которая в данном случае выглядит так
53 1α∫0αx-mdx=1β∫0βx-mdx=1α-β∫βαx-mdx.
54 После вычисления интегралов получаем систему
55 m2+α-m2α=m2+β-m2β=α-m2+β-m2α-β,
56 ее решением служит m=αβ/2 , при этом значении m все три выражения равны α-2αβ+β .▄
57 Добавим, что среди сплюснутых треугольников имеются два типа равнобедренных — это треугольники со сторонами α,  α/2,  α/2 и α,  α,  0 . В работе (Панов, 2018) содержится более точная, чем в следствии 1, асимптотическая информация о расположении соответствующих им геометрических медиан.
58 Замечание 3. Множество сплюснутых треугольных областей, для которых мы получили формулу точного местоположения геометрической медианы, пренебрежимо мало по сравнению с множеством всех треугольных областей. По-видимому, не существует простой аналитической формулы для нахождения расположения геометрической медианы треугольной области общего вида, и тем более произвольной области. Косвенно об этом можно судить по обширному списку центров треугольника, для которых известны формулы вычисления (Kimberling, 2020). Геометрическая медиана треугольной области там отсутствует.
59 3. ГРАДИЕНТНАЯ СИСТЕМА ДЛЯ ПРОИЗВОЛЬНОЙ ОБЛАСТИ В Rn
60 Здесь мы сначала закончим с двумерными областями, расположенными в R2 , а затем сформулируем основной результат, пригодный и для n-мерных областей, расположенных в Rn .
61 Вернемся к теореме 1, а именно к векторному уравнению (9), представляющему градиентную систему для отыскания геометрической медианы треугольной области. Глядя на это уравнение, нетрудно догадаться, как должна выглядеть градиентная система для геометрической медианы произвольной многоугольной области на плоскости.
62 Теорема 2. Точка m=X тогда и только тогда будет геометрической медианой односвязной многоугольной области Π с вершинами P1,  ...,  Pn , когда выполняется равенство
63 ΣP1P2XP2-P1P1P2→+…+ΣPnP1XP1-PnPnP1→=0. (12)
64 Доказательство этой теоремы дословно воспроизводит доказательство теоремы 2. Мы опустим его, приведем только рис. 3, отражающий данную ситуацию. Напомним, что как и в случае треугольной области, присутствующий в (12) вектор — это градиент функции ΣΠX, повернутый на -90° . Расположение точки X+δ→ в многоугольнике Π такое же, как расположение точки X в многоугольнике П´, являющемся сдвигом П на вектор -δ→ .
65

Рис. 3. Исходный многоугольник и его параллельный сдвиг
66 Из теоремы 2 вытекает следующее утверждение.
67 Следствие 2. Пусть задана ограниченная плоская область Ω с кусочно-гладкой границей. Точка m будет ее геометрической медианой тогда и только тогда, когда выполняется равенство
68 ∫P∈∂ΩP-mdP→=0, (13)
69 где интегрирование идет по границе области Ω . При этом уравнение (13) равносильно уравнению
70 ∫P∈∂ΩP-mn→PdP=0, (13´)
71 где n→P — единичный вектор внешней нормали к ∂Ω в точке P .
72 Набросок доказательства. Будем считать, что область Ω односвязная. Впишем в кривую ∂Ω ломаную Π , порядок точек на которой соответствует ориентации границы ∂Ω с помощью внешней нормали. Для геометрической медианы многоугольной области, ограниченной ломаной Π , запишем соотношение (12). Остается указать, что левая часть записанного соотношения будет являться интегральной суммой для интеграла, представленного в левой части соотношения (13), и после этого перейти к пределу при условии, что длины звеньев ломаной стремятся к нулю. Заметим, что при этом же условии геометрическая медиана вписанной многоугольной области будет стремиться к геометрической медиане области Ω .
73 Аналогичное доказательство проходит и для неодносвязной области Ω . Добавим, что для доказательства эквивалентности соотношений (13) и (13´) достаточно повернуть вектор dP→ на -90° .
74 Описанный подход позволяет доказать этот результат для евклидова пространства Rn любой размерности, а не только для n=2 .
75 Теорема 3. Пусть в евклидовом пространстве Rn задана ограниченная область Ω с кусочно-гладкой границей. Точка m будет ее геометрической медианой тогда и только тогда, когда выполняется равенство ∫P∈∂ΩP-mn→PdP=0, где интегрирование идет по границе Ω , n→P — единичный вектор внешней нормали к ∂Ω в точке P .
76 В следующем разделе мы приведем альтернативное доказательство более общего утверждения.
77 4. f -ОБОБЩЕНИЕ
78 Пусть задана функция f аргумента P∈Rn . По определению функции ΣΩf имеем ΣΩfX=∫P∈ΩfP-XdP . Можно сказать, что функция ΣΩfX представляет собой семейство интегралов, параметризованное точками X∈Rn . Следующее утверждение характеризует критические точки этой функции, в том числе и точку ее минимума mf .
79 Теорема 4. Пусть функция f непрерывна и Ω — ограниченная область в Rn с кусочно-гладкой границей. Тогда для функции ΣΩf условие критичности точки m равносильно равенству ∫P∈∂ΩfP-mn→PdP=0, где  n→P — единичный вектор внешней нормали к границе области Ω в точке P .
80 Замечание 4. Эта теорема может быть доказана в том же стиле, что и предыдущие, но мы предъявим здесь альтернативное доказательство, немного усилив условия, налагаемые на функцию f .
81 Доказательство теоремы 4. Мы наметим доказательство только для случая непрерывно дифференцируемой функции f .
82 Так как ∇XfP-X = -∇P fP-X , условие критичности ∇ΣΩf X=0 теперь можно записать в виде ∫P∈Ω∇PfP-mdP=0. После умножения левой и правой части этого равенства на произвольный постоянный вектор δ→ получаем ∫P∈Ω∇PfP-mδ→dP=0. Под знаком интеграла здесь расположена дивергенция векторного поля, поэтому после применения n-мерного варианта формулы Гаусса–Остроградского (Divergence theorem, 2014) получаем ∫P∈∂ΩfP-mδ→  n→PdP=0. В силу произвольности δ→ имеем ∫P∈∂ΩfP-mn→PdP=0. ▄
83 5. ЗАКЛЮЧЕНИЕ
84 Добавим несколько слов о возможных обобщениях полученных результатов. Функция FX,P=P-X , с помощью которой соотношениями (6) и (7) определяется геометрическая медиана, максимально симметрична. Она инвариантна относительно параллельных переносов T , а также изотропна, то есть инвариантна относительно вращений R пространства Rn . Это означает, что FTX,TP=FX,P и FRX,RP=FX,P .
85 Нетрудно убедиться, что при доказательстве теоремы 3 мы воспользовались только инвариантностью P-X относительно параллельных переносов. На самом деле такой же инвариантностью обладает и любая функция вида FX,P=fP-X . Именно это обстоятельство позволило сформулировать и доказать обобщение основного результата, содержащееся в теореме 4.
86 Хорошо известно, что при решении любой задачи, в том числе экономической, нужно использовать имеющиеся симметрии. В качестве дополнительного примера сошлемся здесь на работу (Zhang, Carlsson, 2014), где с помощью дополнительной симметрии в явном виде вычисляется функция ΣΩ для многоугольных областей Ω .

References

1. Divergence theorem (2014). Encyclopedia of Mathematics. Available at: http://www.encyclopediaofmath.org/index.php?title=Divergence_theorem&oldid=31341

2. Fekete S., Mitchell J., Beurer K. (2005). On the continuous Fermat — Weber problem. Oper. Res., 53, 1, 61–76.

3. Fermat–Torricelli problem (2012). Encyclopedia of Mathematics. Available at: https://www.encyclopediaofmath.org/index.php/Fermat-Torricelli_problem

4. Kemperman J.H.B. (1987). The median of a finite measure on a Banach space. In: Statistical data analysis based on the L1-norm and related methods. Amsterdam: North-Holland, 217–230.

5. Kimberling C. (2020). Encyclopedia of triangle centers. Available at: http://faculty.evansville.edu/ck6/encyclopedia/

6. Launhardt W. (1882). Die Bestimmung des zweckmassigsten Standortes einer gewerblichen An-lage. Zeitschrift des Vereines deutscher Ingenieure, 26, 106–115.

7. Panov P.A. (2017). Nash equilibria in the facility location problem with externalities. Journal of the New Economic Association, 1 (33), 28–42 (in Russian).

8. Panov P.A. (2018). On the geometric median of convex, triangular and other polygonal domains. The Bulletin of Irkutsk State University. Series “Mathematics”, 26, 62–75 (in Russian).

9. Savvateev A., Sorokin C., Weber S.? (2015).? Multidimensional? free-mobility? equilibrium: Tiebout ?revisited.?Preprint.

10. Weber A. (1909). Uber den Standort der Industrien. Erster Teil. Reine Theorie des Standorts. Ver-lag von J.C.B. Mohr (Paul Siebeck). Tubingen.

11. Weber problem (2014) Encyclopedia of Mathematics. Available at: https://www.encyclopediaofmath.org/index.php/Weber_problem

12. Wesolowsky G.O. (1993). The Weber problem: History and perspectives. Location Sciense, 1, P. 5–23.

13. Zhang T., Carlsson J. (2014). On the Continuous Fermat – Weber Problem for a Convex Polygon Using Euclidean Distance, http://arxiv.org/abs/1403.3715

Comments

No posts found

Write a review
Translate