Везде
О геометрической медиане и других медианоподобных точках
Оглавление
Аннотация Оценить Содержание публикации
Библиография Комментарии
Поделиться
QR
Метрика
О геометрической медиане и других медианоподобных точках
Аннотация
Код статьи
S042473880010498-6-1
DOI
10.31857/S042473880010498-6
Тип публикации
Статья
Статус публикации
Опубликовано
Авторы
Панов Петр Алексеевич 
Должность: старший преподаватель
Аффилиация: НИУ ВШЭ,
Адрес: Москва, Российская Федерация
Савватеев Алексей Алексеевич
Должность: профессор,
Аффилиация: Центральный экономико-математический институт, Адыгейский государственный университет, Университет Дмитрия Пожарского, Московский физико-технический институт,,
Адрес: Российская Федерация
Выпуск
Том 56 Номер 3
Страницы
145-152
Аннотация

Геометрическая медиана и некоторые ее обобщения широко используются в экономической теории, начиная с работ Вильгельма Лаунхардта и Альфреда Вебера по теории размещения производства. Важнейшее свойство медианы числовой выборки заключается в том, что медиана минимизирует суммарное расстояние до всех элементов выборки. Это минимизирующее свойство положено в основу определения геометрической медианы для конечных наборов точек на плоскости. Далее это определение легко переносится на произвольное метрическое пространство, в том числе и на евклидово пространствоRn. А с помощью интегрирования понятие геометрической медианы распространяется на ограниченные подмногообразия любой размерности вRn. Существуют эффективные численные методы отыскания геометрической медианы, но отсутствуют общие аналитические формулы для ее вычисления. В настоящей работе основное внимание уделено геометрическим медианам ограниченных областей, расположенных в евклидовом пространстве Rn. Основной результат настоящей работы — это вывод нового удобного представления градиентной системы для нахождения геометрической медианы. Этот результат распространяется на широкий класс аналогичных оптимизационных задач, где функция расстояния заменяется на функции более общего вида. Именно решения этих задач мы называем медианоподобными точками, они являются ближайшими родственниками геометрической медианы и широко используются в современных экономических исследованиях.

Ключевые слова
геометрическая медиана, область, треугольная область, градиентная система, критическая точка.
Классификатор
Получено
10.07.2020
Дата публикации
04.09.2020
Всего подписок
27
Всего просмотров
1581
Оценка читателей
0.0 (0 голосов)
Цитировать   Скачать 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), где с помощью дополнительной симметрии в явном виде вычисляется функция ΣΩ для многоугольных областей Ω .

Библиография

1. Панов П.А. (2017). Равновесные расположения центров благ по городу // Журнал Новой эко-номической ассоциации. № 1?(33). С. 28–42.

2. Панов П.А. (2018). О геометрической медиане выпуклых, а также треугольных и других многоугольных областей // Известия Иркутского государственного университета. Се-рия Математика. Т. 26. С. 62–75.

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

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

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

6. 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.

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

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

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

Комментарии

Сообщения не найдены

Написать отзыв
Перевести