Inversión de conjuntos

Problema matemático de encontrar el conjunto mapeado por una función especificada a un rango determinado

En matemáticas , la inversión de conjuntos es el problema de caracterizar la preimagen X de un conjunto Y por una función f , es decir, X = f ⁻¹ ( Y  ) = { x ∈ R ⁿ | f ( x ) ∈ Y  }. También puede verse como el problema de describir el conjunto solución de la restricción cuantificada " Y ( f  ( x ))", donde Y (  y ) es una restricción, por ejemplo una desigualdad , que describe el conjunto Y .

En la mayoría de las aplicaciones, f es una función de R ⁿ a R ^p y el conjunto Y es una caja de R ^p (es decir, un producto cartesiano de p intervalos de R ).

Cuando f no es lineal, el problema de inversión de conjuntos se puede resolver ^[1] utilizando análisis de intervalos combinado con un algoritmo de ramificación y acotación . ^[2]

La idea principal consiste en construir un pavimento de R ^p formado por cajas no superpuestas. Para cada caja [ x ], realizamos las siguientes pruebas:

1. si f  ([ x ]) ⊂ Y concluimos que [ x ] ⊂ X ;
2. si f  ([ x ]) ∩ Y = ∅ concluimos que [ x ] ∩ X = ∅;
3. De lo contrario, el cuadro [ x ] se divide en dos, excepto si su ancho es menor que una precisión dada.

Para comprobar las dos primeras pruebas, necesitamos una extensión de intervalo (o una función de inclusión) [ f  ] para f . Las cajas clasificadas se almacenan en subpavings , es decir, unión de cajas que no se superponen. El algoritmo se puede hacer más eficiente reemplazando las pruebas de inclusión por contractors .

Ejemplo

El conjunto X = f ⁻¹ ([4,9]) donde f  ( x ₁ , x ₂ ) = x²
₁+ x²
₂está representado en la figura.

Por ejemplo, como [−2,1] ² + [4,5] ² = [0,4] + [16,25] = [16,29] no interseca el intervalo [4,9], concluimos que la caja [−2,1] × [4,5] está fuera de X . Como [−1,1] ² + [2, √ 5 ] ² = [0,1] + [4,5] = [4,6] está dentro de [4,9], concluimos que toda la caja [−1,1] × [2, √ 5 ] está dentro de X .

Un anillo definido como un problema de inversión de conjuntos

Solicitud

La inversión de conjuntos se utiliza principalmente para la planificación de rutas , para la estimación de conjuntos de parámetros no lineales , ^{[3] [4]} para la localización ^{[5] [6]} o para la caracterización de dominios de estabilidad de sistemas dinámicos lineales . ^[7]

Referencias

1. Jaulin, L.; Walter, E. (1993). "Inversión de conjuntos mediante análisis de intervalos para estimación no lineal de error acotado" (PDF) . Automatica . 29 (4): 1053–1064. doi :10.1016/0005-1098(93)90106-4.
2. Jaulín, L.; Kieffer, M.; Didrit, O.; Walter, E. (2001). Análisis de intervalos aplicado . Berlín: Springer. ISBN 1-85233-219-0.
3. Jaulin, L.; Godet, JL; Walter, E.; Elliasmine, A.; Leduff, Y. (1997). "Análisis de datos de dispersión de luz mediante inversión de conjuntos" (PDF) . Journal of Physics A: Mathematical and General . 30 (22): 7733–7738. Bibcode :1997JPhA...30.7733J. doi :10.1088/0305-4470/30/22/012.
4. Braems, I.; Berthier, F.; Jaulin, L.; Kieffer, M.; Walter, E. (2001). "Estimación garantizada de parámetros electroquímicos mediante inversión de conjuntos utilizando análisis de intervalos" (PDF) . Revista de química electroanalítica . 495 (1).
5. Colle, E.; Galerne, S. (2013). "Localización de robots móviles mediante multiangulación utilizando inversión de conjuntos". Robótica y sistemas autónomos . 66 (1): 39–48. doi :10.1016/j.robot.2012.09.006.
6. Drevelle, V.; Bonnifait, Ph. (2011). "Un enfoque de pertenencia a conjuntos para posicionamiento satelital de alta integridad asistido por altura". Soluciones GPS . 15 (4): 357–368. doi :10.1007/s10291-010-0195-3. S2CID  121728552.
7. Walter, E.; Jaulin, L. (1994). "Caracterización garantizada de dominios de estabilidad mediante inversión de conjuntos" (PDF) . IEEE Trans. Autom. Control . 39 (4): 886–889. doi :10.1109/9.286277.