Функция сохранения направления - Direction-preserving function

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

Концепция была впервые определена Иимурой.^[1][2] Некоторые варианты этого позже были определены Яном,^[3] Чен и Дэн,^[4] Херингс, ван-дер-Лаан, Талман и Ян,^[5] и другие.

Базовые концепты

Делаем упор на функции ${\displaystyle f:X\to \mathbb {R} ^{n}}$, где область X - конечное подмножество евклидова пространства ${\displaystyle \mathbb {R} ^{n}}$. ch (Икс) обозначает выпуклый корпус из Икс.

Есть много вариантов свойств сохранения направления, в зависимости от того, как точно определить «резкое изменение» и «соседние точки». По поводу «кардинального изменения» есть два основных варианта:

• Сохранение направления (DP) означает, что если Икс и y смежны, то для всех ${\displaystyle i\in [n]}$: ${\displaystyle f_{i}(x)\cdot f_{i}(y)\geq 0}$. Прописью: каждый компонент функции ж нельзя переключать знаки между соседними точками.
• Сохранение общего направления (ВВП) означает, что если Икс и y смежны, то ${\displaystyle f(x)\cdot f(y)\geq 0}$. На словах: направление функции ж (как вектор) не изменяется более чем на 90 градусов между соседними точками. Обратите внимание, что DP подразумевает ВВП, но не наоборот.

По поводу «соседних точек» есть несколько вариантов:

• Гиперкубический Значит это Икс и y смежны тогда и только тогда, когда они содержатся в некотором параллельном осям гиперкубе со стороной 1.
• Симплициальный Значит это Икс и y смежны тогда и только тогда, когда они являются вершинами одного симплекса в некоторой триангуляции области. Обычно симплициальная смежность намного сильнее гиперкубической смежности; соответственно, гиперкубическая ДП намного сильнее симплициальной ДП.

Конкретные определения представлены ниже. Все примеры ниже предназначены для ${\displaystyle n=2}$ размеры и для Икс = { (2,6), (2,7), (3, 6), (3, 7) }.

Свойства и примеры

Сохранение гиперкубического направления

А клетка это подмножество ${\displaystyle \mathbb {R} ^{n}}$ что может быть выражено ${\displaystyle k+[0,1]^{n}}$ для некоторых ${\displaystyle k\in \mathbb {Z} ^{n}}$. Например, квадрат ${\displaystyle [2,3]\times [6,7]}$ это клетка.

Две точки в ${\displaystyle \mathbb {R} ^{n}}$ называются ячейка подключена если есть ячейка, содержащая их обоих.

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

ж^а	6	7
2	(2,1)	(1,1)
3	(0,1)	(0,0)

ж называется гиперкубическое направление с сохранением (HDP) если для любой пары точек, соединенных ячейками Икс,y в ИКС, для всех ${\displaystyle i\in [n]}$: ${\displaystyle f_{i}(x)\cdot f_{i}(y)\geq 0}$. Период, термин локально с сохранением направления (LDP) вместо этого часто используется.^[1] Функция ж^а справа ДП.

• Некоторые авторы^[4]:Def.1 используйте вариант, требующий этого, для любой пары точек, соединенных ячейками Икс,y в ИКС, для всех ${\displaystyle i\in [n]}$: ${\displaystyle (f_{i}(x)-x_{i})\cdot (f_{i}(y)-y_{i})\geq 0}$. Функция ж(Икс) является HDP по второму варианту, если функция грамм(Икс):=ж(Икс)-Икс это HDP по первому варианту.

ж^б	6	7
2	(2,1)	(1,1)
3	(1,-1)	(0,0)

ж называется гиперкубическое сохранение направления (HGDP), или же локально валовое сохранение направления (LGDP), если для любой пары клеточно-связанных точек Икс,y в ИКС, ${\displaystyle f(x)\cdot f(y)\geq 0}$.^{[3]:По умолчанию 2.2} Каждая функция HDP является HGDP, но обратное неверно. Функция ж^б - это HGDP, поскольку скалярное произведение каждых двух векторов в таблице неотрицательно. Но это не HDP, поскольку второй компонент переключает знак между (2,6) и (3,6): ${\displaystyle f_{2}^{b}(2,6)\cdot f_{2}^{b}(3,6)=-1<0}$.

• Некоторые авторы^[5] используйте вариант, требующий этого, для любой пары точек, соединенных ячейками Икс,y в ИКС, ${\displaystyle (f(x)-x)\cdot (f(y)-y)\geq 0}$. Функция ж(Икс) является HGDP по второму варианту, если функция грамм(Икс):=ж(Икс)-Икс это HGDP по первому варианту.

Симплициальное сохранение направления

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

А триангуляция некоторого подмножества ${\displaystyle \mathbb {R} ^{n}}$ называется интеграл если все его симплексы целые.

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

Обратите внимание, что в интегральной триангуляции все симплициально-связанные точки также являются клеточно-связными, но обратное неверно. Например, рассмотрим ячейку ${\displaystyle [2,3]\times [6,7]}$. Рассмотрим интегральную триангуляцию, которая разбивает его на два треугольника: {(2,6), (2,7), (3,7)} и {(2,6), (3,6), (3,7)} . Точки (2,7) и (3,6) клеточно-связны, но не симплициально связаны.

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

ж называется симплициальное сохранение направления (SDP) если для некоторой интегральной триангуляции Икс, для любой пары симплициально-связанных точек Икс,y в ИКС, для всех ${\displaystyle i\in [n]}$: ${\displaystyle (f_{i}(x)-x_{i})\cdot (f_{i}(y)-y_{i})\geq 0}$.^[4]:Def.4

ж^c	6	7
2	(2,1)	(1,1)
3	(1,-2)	(0,0)

ж называется симплициально грубое сохранение направления (SGDP) или же симплициально-локальное сохранение общего направления (SLGDP) если существует целая триангуляция ch (Икс) такое, что для любой пары симплициально-связанных точек Икс,y в ИКС, ${\displaystyle f(x)\cdot f(y)\geq 0}$.^[6][7][8]

Каждая функция HGDP - это SGDP, но HGDP намного сильнее: он эквивалентен SGDP w.r.t. все возможное интегральные триангуляции ch (Икс), тогда как SGDP относится к Один триангуляция.^{[3]:По умолчанию 2.3} Например, функция ж^c справа - SGDP посредством триангуляции, которая делит ячейку на два треугольника {(2,6), (2,7), (3,7)} и {(2,6), (3,6), ( 3,7)}, поскольку в каждом треугольнике скалярное произведение каждых двух векторов неотрицательно. Но это не HGDP, поскольку ${\displaystyle f^{c}(3,6)\cdot f^{c}(2,7)=-1<0}$.

Рекомендации

1. Иимура, Такуя (01.09.2003). «Дискретная теорема о неподвижной точке и ее приложения». Журнал математической экономики. 39 (7): 725–742. Дои:10.1016 / S0304-4068 (03) 00007-7. ISSN  0304-4068.
2. Иимура, Такуя; Мурота, Кадзуо; Тамура, Акихиса (01.12.2005). «Пересмотр теоремы о дискретной неподвижной точке». Журнал математической экономики. 41 (8): 1030–1036. Дои:10.1016 / j.jmateco.2005.03.001. ISSN  0304-4068.
3. Ян, Зайфу (2009-12-01) [2004 (рабочий документ FBA № 210, Йокогамский национальный университет)]. «Дискретный анализ фиксированной точки и его приложения». Журнал теории фиксированной точки и приложений. 6 (2): 351–371. Дои:10.1007 / s11784-009-0130-9. ISSN  1661-7746. S2CID  122640338.
4. Чен, Си; Дэн, Сяотэ (2006). Чен, Дэнни З .; Ли, Д. Т. (ред.). «Симплициальный подход для дискретных теорем о неподвижной точке». Вычислительная техника и комбинаторика. Конспект лекций по информатике. Берлин, Гейдельберг: Springer. 4112: 3–12. Дои:10.1007/11809678_3. ISBN  978-3-540-36926-4.
5. Jean-Jacques Herings, P .; ван дер Лаан, Жерар; Талман, Дольф; Ян, Зайфу (01.01.2008). «Теорема о неподвижной точке для разрывных функций». Письма об исследованиях операций. 36 (1): 89–93. Дои:10.1016 / j.orl.2007.03.008. ISSN  0167-6377.
6. Иимура, Такуя; Ян, Зайфу (2009-12-01). «Исследование соответствий спроса и отклика при наличии неделимости». Журнал теории фиксированной точки и приложений. 6 (2): 333–349. Дои:10.1007 / s11784-009-0131-8. ISSN  1661-7746. S2CID  121519442.
7. ван дер Лаан, Жерар; Талман, Дольф; Ян, Зайфу (01.01.2007). «Метод векторной маркировки для решения задач дискретного нуля и дополнительности» (PDF). SIAM Journal по оптимизации. 18 (1): 290–308. Дои:10.1137/050646378. ISSN  1052-6234.
8. Ян, Зайфу (2008-11-01). «О решениях дискретной нелинейной дополнительности и смежных задач». Математика исследования операций. 33 (4): 976–990. Дои:10.1287 / moor.1080.0343. ISSN  0364-765X.