Вычисление с фиксированной точкой

Вычисление фиксированной точки относится к процессу вычисления точной или приблизительной фиксированной точки заданной функции. В наиболее распространенной форме данная функция $f$ удовлетворяет условию теоремы Брауэра о неподвижной точке : то есть, $f$ непрерывен и отображает единичный d -куб в себя. Теорема Брауэра о неподвижной точке гарантирует, что $f$ имеет неподвижную точку, но доказательство неконструктивно . Были разработаны различные алгоритмы для вычисления приближенной фиксированной точки. Такие алгоритмы используются в экономике для расчета рыночного равновесия , в теории игр для расчета равновесия Нэша и в анализе динамических систем .

Определения

График примерной функции с тремя неподвижными точками

Единичный интервал обозначается $E:=[0,1]$, а единичный d -мерный куб обозначается через $E^{d}$. функция Непрерывная $f$ определяется на $E^{d}$ (от $E^{d}$ самому себе) . Зачастую предполагается, что $f$ не только непрерывен, но и липшицев непрерывен , т. е. для некоторой постоянной $L$, $|f(x)-f(y)|\leq L\cdot |x-y|$ для всех $x,y$ в $E^{d}$.

точка Фиксированная ​ $f$ это точка $x$ в $E^{d}$ такой, что $f(x)=x$. По теореме Брауэра о неподвижной точке любая непрерывная функция из $E^{d}$ для себя имеет фиксированную точку. Но для общих функций невозможно точно вычислить неподвижную точку, поскольку это может быть произвольное действительное число. Алгоритмы вычислений с фиксированной точкой ищут приблизительные фиксированные точки. Существует несколько критериев приблизительной фиксированной точки. Несколько общих критериев:

• Остаточный критерий : задан параметр аппроксимации $\varepsilon >0$ , ε -невязкая неподвижная точка $f$ это точка $x$ в $E^{d}$'такой, что $|f(x)-x|\leq \varepsilon$, где здесь $|\cdot |$ обозначает максимальную норму . То есть все $d$ координаты разницы $f(x)-x$ должно быть не более ε .
• Абсолютный критерий : задан параметр аппроксимации $\delta >0$, δ-абсолютная неподвижная точка $f$ это точка $x$ в $E^{d}$ такой, что $|x-x_{0}|\leq \delta$, где $x_{0}$ любая фиксированная точка $f$.
• Относительный критерий : задан параметр аппроксимации $\delta >0$, δ-относительная неподвижная точка $f$ это точка x в $E^{d}$ такой, что $|x-x_{0}|/|x_{0}|\leq \delta$, где $x_{0}$ любая фиксированная точка $f$.

Для липшицево-непрерывных функций абсолютный критерий сильнее критерия невязки: если $f$ непрерывен по Липшицу с постоянной $L$, затем $|x-x_{0}|\leq \delta$ подразумевает $|f(x)-f(x_{0})|\leq L\cdot \delta$. С $x_{0}$ является фиксированной точкой $f$, это подразумевает $|f(x)-x_{0}|\leq L\cdot \delta$, так $|f(x)-x|\leq (1+L)\cdot \delta$. Следовательно, δ-абсолютная неподвижная точка является также ε -остаточной неподвижной точкой с $\varepsilon =(1+L)\cdot \delta$.

Самый основной шаг алгоритма вычисления с фиксированной запятой — это запрос значения : при любом $x$ в $E^{d}$, алгоритм снабжен оракулом ${\tilde {f}}$ к $f$ который возвращает значение $f(x)$. Точность приблизительной фиксированной точки зависит от ошибки оракула. ${\tilde {f}}(x)$.

Функция $f$ доступен через оценочные запросы: для любого $x$, алгоритм может оценить $f(x)$. Сложность алгоритма во время выполнения обычно определяется количеством необходимых вычислений.

Контрактивные функции

Липшицево-непрерывная функция с константой $L$ называется сжимающим, если $L<1$; он называется слабосжимающим, если $L\leq 1$. Каждая сжимающая функция, удовлетворяющая условиям Брауэра, имеет единственную неподвижную точку. Более того, вычисление фиксированной точки для сжимающих функций проще, чем для общих функций.

Вычисление фиксированной точки с использованием итерации функции

Первым алгоритмом вычислений с фиксированной точкой был с фиксированной точкой итерационный алгоритм Банаха . Теорема Банаха о неподвижной точке подразумевает, что, когда итерация с фиксированной точкой применяется к сжимающему отображению, ошибка после $t$ итерации находятся в $O(L^{t})$. Таким образом, количество оценок, необходимых для $\delta$-относительная фиксированная точка приблизительно равна $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$. Сикорский и Возняковский показал, что алгоритм Банаха оптимален, когда размерность велика. В частности, когда $d\geq \log(1/\delta )/\log(1/L)$, количество требуемых оценок любого алгоритма для $\delta$-относительная фиксированная точка превышает 50% количества оценок, требуемых итерационным алгоритмом. Обратите внимание, что когда $L$ приближается к 1, количество оценок стремится к бесконечности. Ни один конечный алгоритм не может вычислить $\delta$-абсолютная фиксированная точка для всех функций с $L=1$.

Когда $L$ < 1 и d = 1, оптимальным алгоритмом является алгоритм конверта с фиксированной точкой (FPE) Сикорского и Возняковского. Он находит δ -относительную фиксированную точку, используя $O(\log(1/\delta )+\log \log(1/(1-L)))$ запросы и δ -абсолютную фиксированную точку, используя $O(\log(1/\delta ))$ запросы. Это быстрее, чем алгоритм итерации с фиксированной точкой.

Когда $d>1$ но не слишком большой и $L\leq 1$, оптимальным алгоритмом является алгоритм внутреннего эллипсоида (на основе метода эллипсоида ). Он находит ε -невязкую фиксированную точку, используя $O(d\cdot \log(1/\varepsilon ))$ оценки. Когда $L<1$, он находит $\delta$-абсолютная фиксированная точка с использованием $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ оценки.

Шеллман и Сикорский представил алгоритм под названием BEFix (фиксированная точка огибающей пополам) для вычисления ε -остаточной фиксированной точки двумерной функции с ' $L\leq 1$, используя только $2\lceil \log _{2}(1/\varepsilon )\rceil +1$ запросы. Они позже представил улучшение под названием BEDFix (бисекционный конверт с глубокой фиксированной точкой) с той же гарантией наихудшего случая, но с лучшими эмпирическими характеристиками. Когда $L<1$, BEDFix также может вычислить $\delta$-абсолютная фиксированная точка с использованием $O(\log(1/\varepsilon )+\log(1/(1-L)))$ запросы.

Шеллман и Сикорский представил алгоритм под названием PFix для вычисления ε -остаточной неподвижной точки d -мерной функции с L ≤ 1, используя $O(\log ^{d}(1/\varepsilon ))$ запросы. Когда $L$ < 1, PFix может быть выполнен с помощью $\varepsilon =(1-L)\cdot \delta$, и в этом случае он вычисляет δ-абсолютную фиксированную точку, используя $O(\log ^{d}(1/[(1-L)\delta ]))$ запросы. Он более эффективен, чем итерационный алгоритм, когда $L$ близко к 1. Алгоритм является рекурсивным: он обрабатывает d -мерную функцию путем рекурсивного вызова ( d -1)-мерных функций.

Алгоритмы для дифференцируемых функций

Когда функция $f$ дифференцируема, и алгоритм может вычислить ее производную (не только $f$ сам по себе), можно использовать метод Ньютона , и он намного быстрее.

Общие функции

Для функций с константой Липшица $L$ > 1, вычисление фиксированной точки намного сложнее.

Одно измерение

Для одномерной функции ( d = 1) a $\delta$-абсолютную фиксированную точку можно найти с помощью $O(\log(1/\delta ))$ запросы с использованием метода деления пополам : начните с интервала $E:=[0,1]$; на каждой итерации пусть $x$ быть центром текущего интервала и вычислить $f(x)$; если $f(x)>x$ затем рекурсивно пройдите к подинтервалу справа от $x$; в противном случае выполните рекурсию на интервале слева от $x$. Обратите внимание, что текущий интервал всегда содержит фиксированную точку, поэтому после $O(\log(1/\delta ))$ запросов, любая точка в оставшемся интервале является $\delta$-абсолютная фиксированная точка $f$ Параметр $\delta :=\varepsilon /(L+1)$, где $L$ — константа Липшица, дает ε -невязкую фиксированную точку, используя $O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))$ запросы.

Два или более измерений

Для функций в двух или более измерениях проблема гораздо сложнее. Шеллман и Сикорский доказал, что для любых целых d ≥ 2 и $L$ > 1, находя δ-абсолютную неподвижную точку d -мерного $L$-Липшицевы функции могут потребовать бесконечно много вычислений. Идея доказательства состоит в следующем. Для любого целого числа T > 1 и любой последовательности T запросов оценки (возможно, адаптивных) можно построить две функции, непрерывные по Липшицу с константой $L$и дают один и тот же ответ на все эти запросы, но один из них имеет уникальную фиксированную точку в ( x , 0), а другой имеет уникальную фиксированную точку в ( x , 1). Любой алгоритм, использующий T -оценки, не может различать эти функции, поэтому не может найти δ-абсолютную фиксированную точку. Это верно для любого конечного целого числа T .

Было разработано несколько алгоритмов, основанных на вычислении функций, для нахождения ε -невязки с фиксированной точкой.

• Первый алгоритм аппроксимации неподвижной точки общей функции был разработан Гербертом Скарфом в 1967 году. Алгоритм Скарфа находит ε -остаточную фиксированную точку путем нахождения полностью помеченного «примитивного множества» в конструкции, аналогичной лемме Спернера .
• Более поздний алгоритм Гарольда Куна вместо наборов примитивов использовались симплексы и симплициальные разбиения.
• Развивая далее симплициальный подход, Орин Харрисон Меррилл представил алгоритм перезапуска .
• Б. Кертис Ивз представил гомотопический алгоритм . Алгоритм работает, начиная с аффинной функции, которая аппроксимирует $f$, и деформируя его в сторону $f$ следуя за фиксированной точкой . Книга Майкла Тодда рассматривает различные алгоритмы, разработанные до 1976 года.
• Дэвид Гейл показал, что вычисление неподвижной точки n -мерной функции (на единичном d -мерном кубе) эквивалентно решению того, кто является победителем в d -мерной игре Hex (игра с d игроками, каждому из которых необходимо соединить две противоположные грани d -куба). При заданной точности ε
  • Постройте шестигранную доску размера kd , где $k>1/\varepsilon$. Каждая вершина z соответствует точке z / k в единичном n- кубе.
  • Вычислите разницу $f$( з / к ) - з / к ; обратите внимание, что разница представляет собой n -вектор.
  • Пометьте вершину z меткой 1, ..., d , обозначающей наибольшую координату в векторе разности.
  • Полученная маркировка соответствует возможной игре в d -мерную гекс-игру среди d игроков. В этой игре должен быть победитель, и Гейл представляет алгоритм построения выигрышного пути.
  • В выигрышном пути должна быть точка, в которой f _i ( z / k ) - z / k положительна, и соседняя точка, в которой f _i ( z / k ) - z / k отрицательна. Это означает, что существует фиксированная точка $f$ между этими двумя точками.

В худшем случае количество вычислений функций, необходимых для всех этих алгоритмов, экспоненциально в двоичном представлении точности, то есть в $\Omega (1/\varepsilon )$.

Сложность запроса

Хирш, Пападимитриу и Вавасис доказали, что любой алгоритм, основанный на вычислении функций, который находит ε -невязкую фиксированную точку f, требует $\Omega (L'/\varepsilon )$ оценки функций, где $L'$ – константа Липшица функции $f(x)-x$ (Обратите внимание, что $L-1\leq L'\leq L+1$). Точнее:

• Для двумерной функции ( d =2) они доказывают точную оценку $\Theta (L'/\varepsilon )$.
• Для любого d ≥ 3 для нахождения ε -невязкой неподвижной точки d -мерной функции требуется $\Omega ((L'/\varepsilon )^{d-2})$ запросы и $O((L'/\varepsilon )^{d})$ запросы.

Последний результат оставляет пробел в показателе степени. Чен и Дэн закрыл пробел. Они доказали, что для любых d ≥ 2 и $1/\varepsilon >4d$ и $L'/\varepsilon >192d^{3}$, количество запросов, необходимых для вычисления ε -остаточной фиксированной точки, находится в $\Theta ((L'/\varepsilon )^{d-1})$.

Дискретное вычисление с фиксированной точкой

– Дискретная функция это функция, определенная на подмножестве $\mathbb {Z} ^{d}$ ( d -мерная целочисленная сетка). Существует несколько дискретных теорем о неподвижной точке , устанавливающих условия, при которых дискретная функция имеет неподвижную точку. Например, теорема Иимура-Мурота-Тамура утверждает, что (в частности), если $f$ является функцией из прямоугольного подмножества $\mathbb {Z} ^{d}$ себе, и $f$ является гиперкубическим , сохраняющим направление , то $f$ имеет фиксированную точку.

Позволять $f$ быть функцией, сохраняющей направление, из целочисленного куба $\{1,\dots ,n\}^{d}$ самому себе. Чен и Дэн докажите, что для любого d ≥ 2 и n > 48 d вычисление такой фиксированной точки требует $\Theta (n^{d-1})$ функциональные оценки.

Чен и Дэн определяют другую задачу дискретной фиксированной точки, которую они называют 2D-BROUWER . Он рассматривает дискретную функцию $f$ на $\{0,\dots ,n\}^{2}$ такой, что для каждого x в сетке $f$( x ) - x равно (0, 1), или (1, 0), или (-1, -1). Цель — найти в сетке квадрат, в котором встречаются все три метки. Функция $f$ должен нанести на карту квадрат $\{0,\dots ,n\}^{2}$самому себе, поэтому он должен сопоставить линии x = 0 и y = 0 либо с (0, 1), либо с (1, 0); линия x = n равна (-1, -1) или (0, 1); и линия y = n либо (-1, -1), либо (1,0). Задачу можно свести к 2D-SPERNER (вычисление полностью помеченного треугольника в триангуляции, удовлетворяющей условиям леммы Спернера ), и, следовательно, она PPAD-полна . Это означает, что вычисление приближенной фиксированной точки является PPAD-полным даже для очень простых функций.

Связь между вычислениями с фиксированной точкой и алгоритмами поиска корня

Дана функция $g$ от $E^{d}$ в R , корень ​ $g$ это точка x в $E^{d}$ такой, что $g$( х )=0. ε g — -корень это точка x в $E^{d}$ такой, что $g(x)\leq \varepsilon$.

Вычисление с фиксированной точкой — это частный случай поиска корня: если задана функция $f$ на $E^{d}$, определять $g(x):=|f(x)-x|$. X — фиксированная точка $f$ тогда и только тогда, когда x является корнем $g$, а x — ε -невязкая неподвижная точка $f$ тогда и только тогда, когда x является ε -корнем $g$. Следовательно, любой алгоритм поиска корня (алгоритм, который вычисляет приблизительный корень функции) может использоваться для поиска приближенной фиксированной точки.

Обратное неверно: найти приблизительный корень общей функции может быть сложнее, чем найти приблизительную неподвижную точку. В частности, Сикорский доказал, что для нахождения ε -корня требуется $\Omega (1/\varepsilon ^{d})$ функциональные оценки. Это дает экспоненциальную нижнюю оценку даже для одномерной функции (напротив, ε -невязкая фиксированная точка одномерной функции может быть найдена с помощью $O(\log(1/\varepsilon ))$ запросы с использованием метода деления пополам ). Вот эскиз-доказательство. Создайте функцию $g$ что немного больше, чем ε везде в $E^{d}$ за исключением небольшого куба вокруг некоторой точки x ₀ , где x ₀ — уникальный корень $g$. Если $g$ является липшицевым непрерывным с постоянной $L$, то куб вокруг x ₀ может иметь длину стороны $\varepsilon /L$. Любой алгоритм, который находит ε -корень $g$ необходимо проверить набор кубиков, покрывающий всю $E^{d}$; число таких кубиков не менее $(L/\varepsilon )^{d}$.

Однако существуют классы функций, для которых нахождение приближенного корня эквивалентно нахождению приближенной неподвижной точки. Один пример это класс функций $g$ такой, что $g(x)+x$ карты $E^{d}$ самому себе (то есть: $g(x)+x$ находится в $E^{d}$ для всех x в $E^{d}$). Это связано с тем, что для каждой такой функции функция $f(x):=g(x)+x$ удовлетворяет условиям теоремы Брауэра о неподвижной точке. X — фиксированная точка $f$ тогда и только тогда, когда x является корнем $g$, а x — ε -невязкая неподвижная точка $f$ тогда и только тогда, когда x является ε -корнем $g$. Чен и Дэн показывают, что дискретные варианты этих задач вычислительно эквивалентны: обе задачи требуют $\Theta (n^{d-1})$ функциональные оценки.

Сложность связи

Рафгарден и Вайнштейн изучил коммуникационную сложность вычисления приближенной фиксированной точки. В их модели есть два агента: один из них знает функцию $f$ а другой знает функцию $g$. Обе функции липшицевы и удовлетворяют условиям Брауэра. Цель состоит в том, чтобы вычислить приблизительную фиксированную точку составной функции. $g\circ f$. Они показывают, что детерминированная сложность коммуникации заключается в $\Omega (2^{d})$.

Дальнейшее чтение

• Яннакакис, Михалис (май 2009 г.). «Равновесия, неподвижные точки и классы сложности» . Обзор компьютерных наук . 3 (2): 71–85. arXiv : 0802.2831 . дои : 10.1016/j.cosrev.2009.03.004 .