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

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

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

Основные понятия [ править ]

Мы сосредотачиваемся на функциях , где область определения X является конечным подмножеством евклидова пространства . ч ( Х ) обозначает выпуклую оболочку из X . ${\ displaystyle f: X \ to \ mathbb {R} ^ {n}}$ ${\ Displaystyle \ mathbb {R} ^ {п}}$

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

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

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

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

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

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

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

Клетка представляет собой подмножество , которое может быть выражено для некоторых . Например, квадрат - это ячейка. ${\ Displaystyle \ mathbb {R} ^ {п}}$ ${\ Displaystyle к + [0,1] ^ {п}}$ ${\ Displaystyle к \ ин \ mathbb {Z} ^ {п}}$ ${\ Displaystyle [2,3] \ раз [6,7]}$

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

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

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

е называется гиперкубическим направлением сохранения (HDP) , если для любой пары клеток соединенных точек х , у в X, для всех : . Вместо этого часто используется термин локальное сохранение направления (LDP) . ^[1] Функция f ^a справа - это DP. ${\ Displaystyle я \ в [п]}$ ${\ Displaystyle е_ {я} (х) \ cdot f_ {я} (у) \ geq 0}$

Некоторые авторы ^[4]^{: Def.1} использовать вариант , требующий , что для любой пары клеток-связных точек х , у в X, для всех : . Функция f ( x ) является HDP по второму варианту, если и только если функция g ( x ): = f ( x ) - x является HDP по первому варианту. ${\ Displaystyle я \ в [п]}$ ${\ Displaystyle (е_ {я} (х) -x_ {я}) \ cdot (f_ {я} (у) -y_ {я}) \ geq 0}$

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

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

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

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

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

Триангуляции некоторого подмножества называется интегралом , если все его симплексов являются неотъемлемой частью. ${\ Displaystyle \ mathbb {R} ^ {п}}$

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

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

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

е называется симплициальным направлением сохранения (SDP) , если для некоторых интегрального триангуляции X , для любой пары симплициально-связанных точек х , у в X, для всех : . ^[4]^{: По}^{умолчанию 4} ${\ Displaystyle я \ в [п]}$ ${\ Displaystyle (е_ {я} (х) -x_ {я}) \ cdot (f_ {я} (у) -y_ {я}) \ geq 0}$

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

е называется симплициально валовое направление сохраняющего (SGDP) или симплициально-местное валовое направление с сохранением (SLGDP) , если существует интегральную триангуляцию ч ( Х ) такое , что для любой пары симплициально-соединенных точек х , у в X, . ^[6]^[7]^[8] ${\ Displaystyle е (х) \ CDOT е (у) \ geq 0}$

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

Ссылки [ править ]

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

[:0-1] Иимура, Такуя (01.09.2003). «Дискретная теорема о неподвижной точке и ее приложения» . Журнал математической экономики . 39 (7): 725–742. DOI : 10.1016 / S0304-4068 (03) 00007-7 . ISSN 0304-4068 .

[2] Иимура, Такуя; Мурота, Кадзуо; Тамура, Акихиса (01.12.2005). «Пересмотр теоремы о дискретной неподвижной точке» . Журнал математической экономики . 41 (8): 1030–1036. DOI : 10.1016 / j.jmateco.2005.03.001 . ISSN 0304-4068 .

[:1-3] Ян, Зайфу (2009-12-01) [2004 (рабочий документ FBA № 210, Йокогамский национальный университет)]. «Дискретный анализ фиксированной точки и его приложения». Журнал теории и приложений фиксированной точки . 6 (2): 351–371. DOI : 10.1007 / s11784-009-0130-9 . ISSN 1661-7746 . S2CID 122640338 .

[:2-4] а б в Чен, Си; Дэн, Сяотэ (2006). Чен, Дэнни З .; Ли, Д.Т. (ред.). «Симплициальный подход для дискретных теорем о неподвижной точке». Вычислительная техника и комбинаторика . Конспект лекций по информатике. Берлин, Гейдельберг: Springer. 4112 : 3–12. DOI : 10.1007 / 11809678_3 . ISBN 978-3-540-36926-4.

[sciencedirect.com-5] Jean-Jacques Herings, P .; ван дер Лаан, Жерар; Талман, Дольф; Ян, Зайфу (01.01.2008). «Теорема о неподвижной точке для разрывных функций» . Письма об исследовании операций . 36 (1): 89–93. DOI : 10.1016 / j.orl.2007.03.008 . ISSN 0167-6377 .

[6] Иимура, Такуя; Ян, Зайфу (2009-12-01). «Исследование соответствий спроса и отклика при наличии неделимости». Журнал теории и приложений фиксированной точки . 6 (2): 333–349. DOI : 10.1007 / s11784-009-0131-8 . ISSN 1661-7746 . S2CID 121519442 .

[7] ван дер Лаан, Жерар; Талман, Дольф; Ян, Зайфу (01.01.2007). «Метод векторной маркировки для решения задач дискретного нуля и дополнительности» (PDF) . SIAM Journal по оптимизации . 18 (1): 290–308. DOI : 10.1137 / 050646378 . ISSN 1052-6234 .

[8] Ян, Зайфу (2008-11-01). «О решениях дискретной нелинейной дополнительности и смежных задач». Математика исследования операций . 33 (4): 976–990. DOI : 10.1287 / moor.1080.0343 . ISSN 0364-765X .

[1]