Дискретная теорема о неподвижной точке - Discrete fixed-point theorem

В дискретная математика, а дискретная фиксированная точка это фиксированная точка для функций, определенных на конечных наборах, обычно подмножествах целочисленной сетки ${\displaystyle \mathbb {Z} ^{n}}$.

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

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

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

Непрерывные теоремы о неподвижной точке часто требуют выпуклый набор. Аналогом этого свойства для дискретных множеств является цело-выпуклое множество.

Для функций на дискретных множествах

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

Теорема Иимуры-Муроты-Тамуры:^[2] Если Икс конечный цело-выпуклое подмножество из ${\displaystyle \mathbb {Z} ^{n}}$, и ${\displaystyle f:X\to {\text{ch}}(X)}$ это гиперкубическое сохранение направления (HDP) функция, тогда ж имеет фиксированную точку.

Теорема Чен-Дэн:^[3] Если Икс конечное подмножество ${\displaystyle \mathbb {R} ^{n}}$, и ${\displaystyle f:X\to {\text{ch}}(X)}$ является симплициально сохраняющий направление (SDP), тогда ж имеет фиксированную точку.

Теоремы Янга:^[4]

• [3.6] Если Икс конечный цело-выпуклое подмножество из ${\displaystyle \mathbb {Z} ^{n}}$, ${\displaystyle f:X\to \mathbb {R} ^{n}}$ является симплициально грубое сохранение направления (SGDP), и для всех Икс в Икс есть некоторые грамм(Икс)> 0 такое, что ${\displaystyle x+g(x)f(x)\in {\text{ch}}(X)}$, тогда ж имеет нулевую точку.
• [3.7] Если Икс является конечным гиперкубическим подмножеством ${\displaystyle \mathbb {Z} ^{n}}$, с минимальной точкой а и максимальная точка б, ${\displaystyle f:X\to \mathbb {R} ^{n}}$ это SGDP, и для любого Икс в Икс: ${\displaystyle f_{i}(x_{1},\ldots ,x_{i-1},a_{i},x_{i+1},\ldots ,x_{n})\leq 0}$ и ${\displaystyle f_{i}(x_{1},\ldots ,x_{i-1},b_{i},x_{i+1},\ldots ,x_{n})\geq 0}$, тогда ж имеет нулевую точку. Это дискретный аналог Теорема Пуанкаре – Миранды. Это следствие предыдущей теоремы.
• [3.8] Если Икс конечный цело-выпуклое подмножество из ${\displaystyle \mathbb {Z} ^{n}}$, и ${\displaystyle f:X\to {\text{ch}}(X)}$ таково, что ${\displaystyle f(x)-x}$ является SGDP, тогда ж имеет фиксированную точку.^[5] Это дискретный аналог Теорема Брауэра о неподвижной точке.
• [3.9] Если X = ${\displaystyle \mathbb {Z} ^{n}}$, ${\displaystyle f:X\to \mathbb {R} ^{n}}$ ограничен и ${\displaystyle f(x)-x}$ это SGDP, то ж имеет неподвижную точку (это легко следует из предыдущей теоремы, если взять Икс быть подмножеством ${\displaystyle \mathbb {Z} ^{n}}$ это границы ж).
• [3.10] Если Икс конечный цело-выпуклое подмножество из ${\displaystyle \mathbb {Z} ^{n}}$, ${\displaystyle F:X\to 2^{X}}$ а отображение точек на множество, и для всех Икс в Икс: ${\displaystyle F(x)={\text{ch}}(F(x))\cap \mathbb {Z} ^{n}}$ , и есть функция ж такой, что ${\displaystyle f(x)\in {\text{ch}}(F(x))}$ и ${\displaystyle f(x)-x}$ есть SGDP, то есть точка у в Икс такой, что ${\displaystyle y\in F(y)}$. Это дискретный аналог Теорема Какутани о неподвижной точке, а функция ж является аналогом непрерывного функция выбора.
• [3.12] Предположим Икс конечный цело-выпуклое подмножество из ${\displaystyle \mathbb {Z} ^{n}}$, а также симметричный в том смысле, что Икс в Икс если и только -Икс в Икс. Если ${\displaystyle f:X\to \mathbb {R} ^{n}}$ это SGDP w.r.t. а слабосимметричный триангуляция ch (Икс) (в том смысле, что если s является симплексом на границе триангуляции тогда и только тогда, когда -s есть), и ${\displaystyle f(x)\cdot f(-y)\leq 0}$ для каждой пары симплициально связанных точек Икс, у на границе ch (Икс), тогда ж имеет нулевую точку.
• Посмотреть опрос^[4] для получения дополнительных теорем.

Для разрывных функций на непрерывных множествах

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

Теорема Херингса-Лаана-Талмана-Янга о неподвижной точке:^[6] Позволять Икс - непустой многогранник в ${\displaystyle \mathbb {R} ^{n}}$. Позволять ж: Икс → Икс быть локально грубое сохранение направления (LGDP) функция: в любой момент Икс это не фиксированная точка ж, направление ${\displaystyle f(x)-x}$ грубо сохранился в некоторых район из Икс, в том смысле, что для любых двух точек у, z в этом районе его внутренний продукт неотрицателен, то есть: ${\displaystyle (f(y)-y)\cdot (f(z)-z)\geq 0}$. Обратите внимание, что каждый непрерывная функция является LGDP, но функция LGDP может быть прерывистой. Функция LGDP может быть даже ни верхней, ни нижней. полунепрерывный. потом ж имеет фиксированную точку в Икс. Более того, существует конструктивный алгоритм аппроксимации этой неподвижной точки.

Приложения

Дискретные теоремы о неподвижной точке были использованы для доказательства существования равновесие по Нэшу в дискретной игре и существование Вальрасовское равновесие на дискретном рынке.^[7]

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

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. Чен, Си; Дэн, Сяотэ (2006). Чен, Дэнни З .; Ли, Д. Т. (ред.). «Симплициальный подход для дискретных теорем о неподвижной точке». Вычислительная техника и комбинаторика. Конспект лекций по информатике. Берлин, Гейдельберг: Springer. 4112: 3–12. Дои:10.1007/11809678_3. ISBN  978-3-540-36926-4.
4. Ян, Зайфу (2009-12-01) [2004 (рабочий документ FBA № 210, Йокогамский национальный университет)]. «Дискретный анализ фиксированной точки и его приложения». Журнал теории фиксированной точки и приложений. 6 (2): 351–371. Дои:10.1007 / s11784-009-0130-9. ISSN  1661-7746. S2CID  122640338.
5. Ян, Зайфу (2008-11-01). «О решениях дискретной нелинейной дополнительности и смежных задач». Математика исследования операций. 33 (4): 976–990. Дои:10.1287 / moor.1080.0343. ISSN  0364-765X.
6. Jean-Jacques Herings, P .; ван дер Лаан, Жерар; Талман, Дольф; Ян, Зайфу (01.01.2008). «Теорема о неподвижной точке для разрывных функций». Письма об исследованиях операций. 36 (1): 89–93. Дои:10.1016 / j.orl.2007.03.008. ISSN  0167-6377.
7. Иимура, Такуя; Ян, Зайфу (2009-12-01). «Исследование соответствий спроса и отклика при наличии неделимости». Журнал теории фиксированной точки и приложений. 6 (2): 333–349. Дои:10.1007 / s11784-009-0131-8. ISSN  1661-7746. S2CID  121519442.