Computación de punto fijo

El cálculo de punto fijo se refiere al proceso de calcular un punto fijo exacto o aproximado de una función dada. ^{[ 1 ]} En su forma más común, la función dada${\displaystyle f}$satisface la condición del teorema del punto fijo de Brouwer : es decir,${\displaystyle f}$es continua y mapea el d -cubo unitario sobre sí mismo. El teorema del punto fijo de Brouwer garantiza que${\displaystyle f}$tiene un punto fijo, pero la prueba no es constructiva . Se han ideado varios algoritmos para calcular un punto fijo aproximado. Dichos algoritmos se utilizan en diversas tareas, como

• Cálculo del equilibrio de Nash ,
• Cálculo del equilibrio de mercado ,
• Análisis de sistemas dinámicos .

El intervalo unitario se denota por${\displaystyle E:=[0,1]}$y el cubo unitario d -dimensional se denota por${\displaystyle E^{d}}$Una función continua${\displaystyle f}$se define en${\displaystyle E^{d}}$(de${\displaystyle E^{d}}$a sí mismo) . A menudo, se asume que${\displaystyle f}$no solo es continua sino también Lipschitz continua , es decir, para alguna constante${\displaystyle L}$, ${\displaystyle |f(x)-f(y)|\leq L\cdot |xy|}$a pesar de${\displaystyle x,y}$en${\displaystyle E^{d}}$.

Un punto fijo de${\displaystyle f}$es un punto${\displaystyle x}$en${\displaystyle E^{d}}$de tal manera que${\displaystyle f(x)=x}$. Por el teorema del punto fijo de Brouwer , cualquier función continua de${\displaystyle E^{d}}$ para sí misma tiene un punto fijo. Pero para funciones generales, es imposible calcular un punto fijo con precisión, ya que puede ser un número real arbitrario . Los algoritmos de cálculo de punto fijo buscan puntos fijos aproximados . Existen varios criterios para un punto fijo aproximado. Algunos criterios comunes son: ^{[ 2 ]}

• El criterio residual : dado un parámetro de aproximación${\displaystyle \varepsilon >0}$, Un punto fijo residual ε de${\displaystyle f}$es un punto${\displaystyle x}$en${\displaystyle E^{d}}$' tal que${\displaystyle |f(x)-x|\leq \varepsilon }$, dónde aquí${\displaystyle |\cdot |}$denota la norma máxima . Es decir, todo${\displaystyle d}$coordenadas de la diferencia${\displaystyle f(x)-x}$debería ser como máximo ε . ^{[ 3 ] : 4}
• El criterio absoluto : dado un parámetro de aproximación${\displaystyle \delta >0}$, Un punto fijo absoluto δ de${\displaystyle f}$es un punto${\displaystyle x}$en${\displaystyle E^{d}}$de tal manera que${\displaystyle |x-x_{0}|\leq \delta }$, dónde${\displaystyle x_{0}}$es cualquier punto fijo de${\displaystyle f}$.
• El criterio relativo : dado un parámetro de aproximación${\displaystyle \delta >0}$, Un punto fijo relativo δ de${\displaystyle f}$es un punto x en${\displaystyle E^{d}}$de tal manera que${\displaystyle |x-x_{0}|/|x_{0}|\leq \delta }$, dónde${\displaystyle x_{0}}$es cualquier punto fijo de${\displaystyle f}$.

Para funciones Lipschitz-continuas, el criterio absoluto es más fuerte que el criterio residual: Si${\displaystyle f}$es Lipschitz continua con constante${\displaystyle L}$, entonces${\displaystyle |x-x_{0}|\leq \delta }$implica${\displaystyle |f(x)-f(x_{0})|\leq L\cdot \delta }$. Desde${\displaystyle x_{0}}$es un punto fijo de${\displaystyle f}$, esto implica${\displaystyle |f(x)-x_{0}|\leq L\cdot \delta }$, entonces${\displaystyle |f(x)-x|\leq (1+L)\cdot \delta }$Por lo tanto, un punto fijo δ-absoluto es también un punto fijo ε -residual con${\displaystyle \varepsilon =(1+L)\cdot \delta }$.

El paso más básico de un algoritmo de cálculo de punto fijo es una consulta de valor : dado cualquier${\displaystyle x}$en${\displaystyle E^{d}}$, el algoritmo se proporciona con un oráculo${\displaystyle {\tilde {f}}}$a${\displaystyle f}$que devuelve el valor${\displaystyle f(x)}$La precisión del punto fijo aproximado depende del error en el oráculo.${\displaystyle {\tilde {f}}(x)}$.

La función${\displaystyle f}$es accesible a través de consultas de evaluación : para cualquier${\displaystyle x}$, el algoritmo puede evaluar${\displaystyle f(x)}$La complejidad temporal de un algoritmo suele venir dada por el número de evaluaciones necesarias.

Una función Lipschitz-continua con constante${\displaystyle L}$se llama contractivo si${\displaystyle L<1}$; se denomina débilmente contractiva si${\displaystyle L\leq 1}$Toda función contractiva que satisface las condiciones de Brouwer tiene un único punto fijo. Además, el cálculo del punto fijo para funciones contractivas es más sencillo que para funciones generales.

El primer algoritmo para el cálculo de punto fijo fue el algoritmo de iteración de punto fijo de Banach. El teorema del punto fijo de Banach implica que, cuando se aplica la iteración de punto fijo a una aplicación de contracción, el error después de${\displaystyle t}$iteraciones está en${\displaystyle O(L^{t})}$. Por lo tanto, el número de evaluaciones requeridas para una${\displaystyle \delta }$-El punto fijo relativo es aproximadamente${\displaystyle \log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)}$. Sikorski y Wozniakowski ^{[ 4 ]} demostraron que el algoritmo de Banach es óptimo cuando la dimensión es grande. Específicamente, cuando${\displaystyle d\geq \log(1/\delta )/\log(1/L)}$, el número de evaluaciones requeridas de cualquier algoritmo para${\displaystyle \delta }$-El punto fijo relativo es mayor que el 50% del número de evaluaciones requeridas por el algoritmo de iteración. Tenga en cuenta que cuando${\displaystyle L}$Cuando se aproxima a 1, el número de evaluaciones tiende al infinito. Ningún algoritmo finito puede calcular un${\displaystyle \delta }$-punto fijo absoluto para todas las funciones con${\displaystyle L=1}$. ^{[ 5 ]}

Cuando${\displaystyle L}$< 1 y d = 1, el algoritmo óptimo es el algoritmo de Envolvente de Punto Fijo (FPE) de Sikorski y Wozniakowski. ^{[ 4 ]} Encuentra un punto fijo δ -relativo usando${\displaystyle O(\log(1/\delta )+\log \log(1/(1-L)))}$consultas y un punto fijo δ -absoluto usando${\displaystyle O(\log(1/\delta ))}$consultas. Esto es más rápido que el algoritmo de iteración de punto fijo. ^{[ 6 ]}

Cuando${\displaystyle d>1}$pero no demasiado grande, y${\displaystyle L\leq 1}$, el algoritmo óptimo es el algoritmo del elipsoide interior (basado en el método del elipsoide ). ^{[ 7 ]} Encuentra un punto fijo ε- residual usando${\displaystyle O(d\cdot \log(1/\varepsilon ))}$evaluaciones. Cuando${\displaystyle L<1}$, encuentra un${\displaystyle \delta }$-punto fijo absoluto usando${\displaystyle O(d\cdot [\log(1/\delta )+\log(1/(1-L))])}$evaluaciones.

Shellman y Sikorski ^{[ 8 ]} presentaron un algoritmo llamado BEFix (Bisection Envelope Fixed-point) para calcular un punto fijo ε -residual de una función bidimensional con '${\displaystyle L\leq 1}$, utilizando únicamente${\displaystyle 2\lceil \log _ {2}(1/\varepsilon )\rceil +1}$consultas. Posteriormente ^{[ 9 ]} presentaron una mejora llamada BEDFix (Bisection Envelope Deep-cut Fixed-point), con la misma garantía en el peor de los casos pero mejor rendimiento empírico. Cuando${\displaystyle L<1}$, BEDFix también puede calcular un${\displaystyle \delta }$-punto fijo absoluto usando${\displaystyle O(\log(1/\varepsilon )+\log(1/(1-L)))}$consultas.

Shellman y Sikorski ^{[ 2 ]} presentaron un algoritmo llamado PFix para calcular un punto fijo residual ε de una función d -dimensional con L ≤ 1, utilizando${\displaystyle O(\log ^{d}(1/\varepsilon ))}$consultas. Cuando${\displaystyle L}$< 1, PFix se puede ejecutar con${\displaystyle \varepsilon =(1-L)\cdot \delta }$y en ese caso, calcula un punto fijo δ-absoluto, utilizando${\displaystyle O(\log ^{d}(1/[(1-L)\delta ]))}$consultas. Es más eficiente que el algoritmo de iteración cuando${\displaystyle L}$está cerca de 1. El algoritmo es recursivo: maneja una función d -dimensional mediante llamadas recursivas a funciones ( d -1)-dimensionales.

Para funciones con constante de Lipschitz${\displaystyle L}$> 1, calcular un punto fijo es mucho más difícil.

Para una función unidimensional ( d = 1), una${\displaystyle \delta }$-El punto fijo absoluto se puede encontrar usando${\displaystyle O(\log(1/\delta ))}$Consultas que utilizan el método de bisección : comience con el intervalo${\displaystyle E:=[0,1]}$; en cada iteración, deje${\displaystyle x}$Sea el centro del intervalo actual y calcule${\displaystyle f(x)}$; si${\displaystyle f(x)>x}$luego recursión en el subintervalo a la derecha de${\displaystyle x}$; de lo contrario, recursión en el intervalo a la izquierda de${\displaystyle x}$. Tenga en cuenta que el intervalo actual siempre contiene un punto fijo, por lo que después${\displaystyle O(\log(1/\delta ))}$consultas, cualquier punto en el intervalo restante es un${\displaystyle \delta }$-punto fijo absoluto de${\displaystyle f}$Configuración${\displaystyle \delta$ :=\varepsilon /(L+1)} , donde${\displaystyle L}$es la constante de Lipschitz, da un punto fijo residual ε , usando${\displaystyle O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))}$consultas. ^{[ 3 ]}

Para funciones en dos o más dimensiones, el problema es mucho más desafiante. Shellman y Sikorski ^{[ 2 ]} demostraron que para cualquier entero d ≥ 2 y${\displaystyle L}$> 1, encontrar un punto fijo absoluto δ de dimensión d${\displaystyle L}$Las funciones Lipschitz podrían requerir un número infinito de evaluaciones. La idea de la demostración es la siguiente: para cualquier entero T > 1 y cualquier secuencia T de consultas de evaluación (posiblemente adaptativa), se pueden construir dos funciones que sean Lipschitz-continuas con constante${\displaystyle L}$y dan la misma respuesta a todas estas consultas, pero una de ellas tiene un único punto fijo en ( x , 0) y la otra tiene un único punto fijo en ( x , 1). Cualquier algoritmo que utilice T evaluaciones no puede diferenciar entre estas funciones, por lo que no puede encontrar un punto fijo δ-absoluto. Esto es cierto para cualquier entero finito T.

Se han desarrollado varios algoritmos basados ​​en evaluaciones de funciones para encontrar un punto fijo residual ε .

Una función discreta es una función definida en un subconjunto de${\displaystyle \mathbb {Z} ^{d}}$(la cuadrícula entera d -dimensional). Existen varios teoremas de punto fijo discretos que establecen las condiciones bajo las cuales una función discreta tiene un punto fijo. Por ejemplo, el teorema de Iimura-Murota-Tamura establece que (en particular) si${\displaystyle f}$es una función de un subconjunto rectangular de${\displaystyle \mathbb {Z} ^{d}}$a sí mismo, y${\displaystyle f}$es hipercúbica que conserva la dirección , entonces${\displaystyle f}$tiene un punto fijo.

Dejar${\displaystyle f}$sea ​​una función que preserve la dirección del cubo entero${\displaystyle \{1,\dots ,n\}^{d}}$a sí mismo. Chen y Deng ^{[ 20 ]} demuestran que, para cualquier d ≥ 2 y n > 48 d , el cálculo de dicho punto fijo requiere ${\displaystyle \Theta (n^{d-1})}$evaluaciones de funciones.

Chen y Deng ^{[ 21 ]} definen un problema de punto fijo discreto diferente, al que llaman 2D-BROUWER . Considera una función discreta${\displaystyle f}$en${\displaystyle \{0,\dots ,n\}^{2}}$de tal manera que, para cada x en la cuadrícula,${\displaystyle f}$( x ) - x es (0, 1) o (1, 0) o (-1, -1). El objetivo es encontrar un cuadrado en la cuadrícula en el que aparezcan las tres etiquetas. La función${\displaystyle f}$debe mapear el cuadrado${\displaystyle \{0,\dots ,n\}^{2}}$a sí mismo, por lo que debe mapear las líneas x = 0 e y = 0 a (0, 1) o (1, 0); la línea x = n a (-1, -1) o (0, 1); y la línea y = n a (-1, -1) o (1,0). El problema se puede reducir a 2D-SPERNER (calcular un triángulo completamente etiquetado en una triangulación que satisfaga las condiciones del lema de Sperner ), y por lo tanto es PPAD-completo . Esto implica que calcular un punto fijo aproximado es PPAD-completo incluso para funciones muy simples.

Dada una función${\displaystyle g}$de${\displaystyle E^{d}}$a R , una raíz de${\displaystyle g}$es un punto x en${\displaystyle E^{d}}$de tal manera que${\displaystyle g}$( x )=0. Una raíz ε de g es un punto x en${\displaystyle E^{d}}$de tal manera que${\displaystyle g(x)\leq \varepsilon }$.

El cálculo de punto fijo es un caso especial de búsqueda de raíces: dada una función${\displaystyle f}$en${\displaystyle E^{d}}$, definir${\displaystyle g(x):=|f(x)-x|}$. X es un punto fijo de${\displaystyle f}$si y solo si x es una raíz de${\displaystyle g}$y x es un punto fijo residual ε de${\displaystyle f}$si y solo si x es una raíz ε de${\displaystyle g}$Por lo tanto, cualquier algoritmo de búsqueda de raíces (un algoritmo que calcula una raíz aproximada de una función) puede utilizarse para encontrar un punto fijo aproximado.

Lo contrario no es cierto: encontrar una raíz aproximada de una función general puede ser más difícil que encontrar un punto fijo aproximado. En particular, Sikorski ^{[ 22 ]} demostró que encontrar una raíz ε requiere${\displaystyle \Omega (1/\varepsilon ^{d})}$evaluaciones de funciones. Esto proporciona una cota inferior exponencial incluso para una función unidimensional (en contraste, se puede encontrar un punto fijo residual ε de una función unidimensional usando${\displaystyle O(\log(1/\varepsilon ))}$consultas usando el método de bisección ). Aquí hay un esbozo de demostración. ^{[ 3 ] : 35} Construir una función${\displaystyle g}$que es ligeramente mayor que ε en todas partes${\displaystyle E^{d}}$excepto en algún pequeño cubo alrededor de algún punto x ₀ , donde x ₀ es la única raíz de${\displaystyle g}$. Si${\displaystyle g}$es Lipschitz continua con constante${\displaystyle L}$, entonces el cubo alrededor de x ₀ puede tener una longitud de lado de${\displaystyle \varepsilon /L}$. Cualquier algoritmo que encuentre una raíz ε de${\displaystyle g}$debe comprobar un conjunto de cubos que cubra todo${\displaystyle E^{d}}$; el número de tales cubos es al menos${\displaystyle (L/\varepsilon )^{d}}$.

Sin embargo, existen clases de funciones para las cuales encontrar una raíz aproximada es equivalente a encontrar un punto fijo aproximado. Un ejemplo ^{[ 20 ]} es la clase de funciones${\displaystyle g}$de tal manera que${\displaystyle g(x)+x}$mapas${\displaystyle E^{d}}$ a sí mismo (es decir:${\displaystyle g(x)+x}$está en${\displaystyle E^{d}}$para todo x en${\displaystyle E^{d}}$). Esto se debe a que, para cada una de esas funciones, la función${\displaystyle f(x):=g(x)+x}$satisface las condiciones del teorema del punto fijo de Brouwer. X es un punto fijo de${\displaystyle f}$si y solo si x es una raíz de${\displaystyle g}$y x es un punto fijo residual ε de${\displaystyle f}$si y solo si x es una raíz ε de${\displaystyle g}$Chen y Deng ^{[ 20 ]} muestran que las variantes discretas de estos problemas son computacionalmente equivalentes: ambos problemas requieren ${\displaystyle \Theta (n^{d-1})}$evaluaciones de funciones.

Roughgarden y Weinstein ^{[ 23 ]} estudiaron la complejidad de la comunicación al calcular un punto fijo aproximado. En su modelo, hay dos agentes: uno de ellos conoce una función${\displaystyle f}$y el otro conoce una función${\displaystyle g}$Ambas funciones son Lipschitz continuas y satisfacen las condiciones de Brouwer. El objetivo es calcular un punto fijo aproximado de la función compuesta.${\displaystyle g\circ f}$. Demuestran que la complejidad de la comunicación determinista está en${\displaystyle \Omega (2^{d})}$.

• Yannakakis, Mihalis (mayo de 2009). "Equilibrios, puntos fijos y clases de complejidad" . Computer Science Review . 3 (2): 71– 85. arXiv : 0802.2831 . doi : 10.1016/j.cosrev.2009.03.004 .