Función de preservación de dirección

En matemáticas discretas , una función que preserva la dirección (o aplicación) es una función en un espacio discreto, como la cuadrícula de números enteros, que (informalmente) no cambia demasiado drásticamente entre dos puntos adyacentes. Puede considerarse un análogo discreto de una función continua .

El concepto fue definido por primera vez por Iimura. ^{[1] [2]} Algunas variantes del mismo fueron definidas posteriormente por Yang, ^[3] Chen y Deng, ^[4] Herings, van-der-Laan, Talman y Yang, ^[5] y otros.

Conceptos básicos

Nos centramos en funciones donde el dominio X es un subconjunto finito del espacio euclidiano . ch( X ) denota la envoltura convexa de X . ${\displaystyle f:X\to \mathbb {R} ^{n}}$ ${\displaystyle \mathbb {R} ^{n}}$

Existen muchas variantes de las propiedades de conservación de la dirección, dependiendo de cómo se defina exactamente el "cambio drástico" y los "puntos adyacentes". En cuanto al "cambio drástico", existen dos variantes principales:

• La preservación de la dirección (PD) significa que, si x e y son adyacentes, entonces para todos los : . En palabras: cada componente de la función f no debe cambiar de signo entre puntos adyacentes. ${\displaystyle i\in [n]}$ ${\displaystyle f_{i}(x)\cdot f_{i}(y)\geq 0}$
• La preservación de la dirección bruta (PDB) significa que, si x e y son adyacentes, entonces . En palabras: la dirección de la función f (como vector) no cambia más de 90 grados entre puntos adyacentes. Nótese que la PD implica PD, pero no al revés. ${\displaystyle f(x)\cdot f(y)\geq 0}$

Respecto a los "puntos adyacentes" existen varias variantes:

• Hipercúbico significa que x e y son adyacentes siempre y cuando estén contenidos en algún hipercubo de ejes paralelos con una longitud de lado de 1.
• Simplicial significa que x e y son adyacentes si son vértices del mismo símplex, en alguna triangulación del dominio. Por lo general, la adyacencia simplicial es mucho más fuerte que la adyacencia hipercúbica; en consecuencia, la DP hipercúbica es mucho más fuerte que la DP simplicial.

A continuación se presentan definiciones específicas. Todos los ejemplos que aparecen a continuación son para dimensiones y para X = { (2,6), (2,7), (3, 6), (3, 7) }. ${\displaystyle n=2}$

Propiedades y ejemplos

Preservación de la dirección hipercúbica

Una celda es un subconjunto de que puede expresarse mediante para algún . Por ejemplo, el cuadrado es una celda. ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle k+[0,1]^{n}}$ ${\displaystyle k\in \mathbb {Z} ^{n}}$ ${\displaystyle [2,3]\times [6,7]}$

Dos puntos en una celda se llaman conexos si existe una celda que los contiene a ambos. ${\displaystyle \mathbb {R} ^{n}}$

Las propiedades de preservación de la dirección hipercúbica requieren que la función no cambie demasiado drásticamente en los puntos conectados a la celda (puntos en la misma celda hipercúbica).

Se dice que f conserva la dirección hipercúbica (HDP) si, para cualquier par de puntos x , y conectados por celdas en X, para todos los : . En su lugar, se suele utilizar el término preservación de la dirección local (LDP) . ^[1] La función f ^a de la derecha es DP. ${\displaystyle i\in [n]}$ ${\displaystyle f_{i}(x)\cdot f_{i}(y)\geq 0}$

• Algunos autores ^{[4] : Def.1} utilizan una variante que requiere que, para cualquier par de puntos x , y conectados por celdas en X, para todos : . Una función f ( x ) es HDP por la segunda variante, si y solo si la función g ( x ):= f ( x )- x es HDP por la primera variante. ${\displaystyle i\in [n]}$ ${\displaystyle (f_{i}(x)-x_{i})\cdot (f_{i}(y)-y_{i})\geq 0}$

f se llama preservadora de dirección bruta hipercúbica (HGDP) o preservadora de dirección bruta local (LGDP) si para cualquier par de puntos x , y conectados por celdas en X, . ^{[3] : Def.2.2} Toda función HDP es HGDP, pero la recíproca no es verdadera. La función f ^b es HGDP, ya que el producto escalar de cada dos vectores en la tabla no es negativo. Pero no es HDP, ya que el segundo componente cambia de signo entre (2,6) y (3,6): . ${\displaystyle f(x)\cdot f(y)\geq 0}$ ${\displaystyle f_{2}^{b}(2,6)\cdot f_{2}^{b}(3,6)=-1<0}$

• Algunos autores ^{[5] utilizan una variante que requiere que, para cualquier par de puntos} x , y conectados por celdas en X, . Una función f ( x ) es HGDP por la segunda variante, si y solo si la función g ( x ):= f ( x )- x es HGDP por la primera variante. ${\displaystyle (f(x)-x)\cdot (f(y)-y)\geq 0}$

Preservación de dirección simple

Un símplex se llama integral si todos sus vértices tienen coordenadas enteras y todos están en la misma celda (por lo que la diferencia entre las coordenadas de los diferentes vértices es como máximo 1).

Una triangulación de algún subconjunto de se llama integral si todos sus símplices son integrales. ${\displaystyle \mathbb {R} ^{n}}$

Dada una triangulación, dos puntos se denominan simplemente conexos si existe un símplex de la triangulación que los contiene a ambos.

Nótese que, en una triangulación integral, todos los puntos conexos de manera simple también están conexos por celda, pero lo inverso no es cierto. Por ejemplo, considere la celda . Considere la triangulación integral que la divide en dos triángulos: {(2,6),(2,7),(3,7)} y {(2,6),(3,6),(3,7)}. Los puntos (2,7) y (3,6) están conexos por celda pero no están conexos de manera simple. ${\displaystyle [2,3]\times [6,7]}$

Las propiedades de preservación de la dirección simpliciales suponen una triangulación integral fija del dominio de entrada. Requieren que la función no cambie demasiado drásticamente en puntos conexos simpliciales (puntos en el mismo símplex de la triangulación). Este es, en general, un requisito mucho más débil que la preservación de la dirección hipercúbica.

f se llama preservadora de dirección simple (SDP) si, para alguna triangulación integral de X , para cualquier par de puntos simplemente conectados x , y en X, para todos : . ^{[4] : Def.4} ${\displaystyle i\in [n]}$ ${\displaystyle (f_{i}(x)-x_{i})\cdot (f_{i}(y)-y_{i})\geq 0}$

f se llama preservación de dirección bruta simple (SGDP) o preservación de dirección bruta simple-local (SLGDP) si existe una triangulación integral de ch( X ) tal que, para cualquier par de puntos simplemente conectados x , y en X, . ^{[6] [7] [8]} ${\displaystyle f(x)\cdot f(y)\geq 0}$

Toda función HGDP es SGDP, pero HGDP es mucho más fuerte: es equivalente a SGDP con respecto a todas las triangulaciones integrales posibles de ch( X ), mientras que SGDP se relaciona con una única triangulación. ^{[3] : Def.2.3} Como ejemplo, la función f ^c de la derecha es SGDP por la triangulación que divide la celda en los dos triángulos {(2,6),(2,7),(3,7)} y {(2,6),(3,6),(3,7)}, ya que en cada triángulo, el producto escalar de cada dos vectores no es negativo. Pero no es HGDP, ya que . ${\displaystyle f^{c}(3,6)\cdot f^{c}(2,7)=-1<0}$

Referencias

1. Iimura, Takuya (1 de septiembre de 2003). "Un teorema de punto fijo discreto y sus aplicaciones". Revista de Economía Matemática . 39 (7): 725–742. doi :10.1016/S0304-4068(03)00007-7. ISSN  0304-4068.
2. Iimura, Takuya; Murota, Kazuo; Tamura, Akihisa (1 de diciembre de 2005). "Reconsideración del teorema del punto fijo discreto". Revista de Economía Matemática . 41 (8): 1030–1036. doi :10.1016/j.jmateco.2005.03.001. ISSN  0304-4068.
3. Yang, Zaifu (2009-12-01) [2004 (documento de trabajo de la FBA n.º 210, Universidad Nacional de Yokohama)]. "Análisis de punto fijo discreto y sus aplicaciones". Revista de teoría y aplicaciones de punto fijo . 6 (2): 351–371. doi :10.1007/s11784-009-0130-9. ISSN  1661-7746. S2CID  122640338.
4. Chen, Xi; Deng, Xiaotie (2006). "Un enfoque simplista para teoremas de punto fijo discreto". En Chen, Danny Z.; Lee, DT (eds.). Computación y combinatoria . Apuntes de clase en informática. Vol. 4112. Berlín, Heidelberg: Springer. págs. 3–12. doi :10.1007/11809678_3. ISBN 978-3-540-36926-4.
5. Jean-Jacques Herings, P.; van der Laan, Gerard; Talman, Dolf; Yang, Zaifu (1 de enero de 2008). "Un teorema del punto fijo para funciones discontinuas". Cartas de investigación operativa . 36 (1): 89–93. doi :10.1016/j.orl.2007.03.008. hdl : 10419/86189 . ISSN  0167-6377. S2CID  14117444.
6. Iimura, Takuya; Yang, Zaifu (1 de diciembre de 2009). "Un estudio sobre las correspondencias de demanda y respuesta en presencia de indivisibilidades". Revista de teoría y aplicaciones del punto fijo . 6 (2): 333–349. doi :10.1007/s11784-009-0131-8. ISSN  1661-7746. S2CID  121519442.
7. van der Laan, Gerard; Talman, Dolf; Yang, Zaifu (1 de enero de 2007). "Un método de etiquetado vectorial para resolver problemas discretos de punto cero y complementariedad" (PDF) . Revista SIAM sobre optimización . 18 (1): 290–308. doi :10.1137/050646378. ISSN  1052-6234.
8. Yang, Zaifu (1 de noviembre de 2008). "Sobre las soluciones de complementariedad no lineal discreta y problemas relacionados". Matemáticas de la investigación de operaciones . 33 (4): 976–990. doi :10.1287/moor.1080.0343. ISSN  0364-765X.