Intersección relajada

La intersección relajada de m conjuntos corresponde a la intersección clásica entre conjuntos, excepto que se permite relajar algunos conjuntos para evitar una intersección vacía. Esta noción se puede utilizar para resolver problemas de satisfacción de restricciones que son inconsistentes al relajar un pequeño número de restricciones . Cuando se considera un enfoque de error acotado para la estimación de parámetros , la intersección relajada permite ser robusto con respecto a algunos valores atípicos .

Definición

La intersección q -relajada de los m subconjuntos de , denotada por es el conjunto de todos los que pertenecen a todos los , excepto como máximo. Esta definición se ilustra en la Figura 1. ${\displaystyle X_{1},\dots ,X_{m}}$ ${\displaystyle R^{n}}$ ${\displaystyle X^{\{q\}}=\bigcap ^{\{q\}}X_{i}}$ ${\displaystyle x\in R^{n}}$ ${\displaystyle X_{i}}$ ${\displaystyle q}$

Figura 1. q -intersección de 6 conjuntos para q = 2 (rojo), q = 3 (verde), q = 4 (azul), q = 5 (amarillo).

Definir ${\displaystyle \lambda (x)={\text{card}}\left\{i\ |\ x\in X_{i}\right\}.}$

Tenemos ${\displaystyle X^{\{q\}}=\lambda ^{-1}([m-q,m]).}$

La caracterización de la intersección q-relajada es, por tanto, un problema de inversión de conjuntos . ^[1]

Ejemplo

Consideremos 8 intervalos: ${\displaystyle X_{1}=[1,4],}$ ${\displaystyle X_{2}=\ [2,4],}$ ${\displaystyle X_{3}=[2,7],}$ ${\displaystyle X_{4}=[6,9],}$ ${\displaystyle X_{5}=[3,4],}$ ${\displaystyle X_{6}=[3,7].}$

Tenemos

${\displaystyle X^{\{0\}}=\emptyset ,}$ ${\displaystyle X^{\{1\}}=[3,4],}$ ${\displaystyle X^{\{2\}}=[3,4],}$ ${\displaystyle X^{\{3\}}=[2,4]\cup [6,7],}$ ${\displaystyle X^{\{4\}}=[2,7],}$ ${\displaystyle X^{\{5\}}=[1,9],}$ ${\displaystyle X^{\{6\}}=]-\infty ,\infty [.}$

Intersección relajada de intervalos

La intersección relajada de intervalos no es necesariamente un intervalo. Por lo tanto, tomamos la envoltura de intervalos del resultado. Si son intervalos, la intersección relajada se puede calcular con una complejidad de m .log( m ) utilizando el algoritmo de Marzullo . Es suficiente ordenar todos los límites inferiores y superiores de los m intervalos para representar la función . Entonces, obtenemos fácilmente el conjunto ${\displaystyle X_{i}}$ ${\displaystyle \lambda }$

${\displaystyle X^{\{q\}}=\lambda ^{-1}([m-q,m])}$

que corresponde a una unión de intervalos. Luego devolvemos el intervalo más pequeño que contiene esta unión.

La figura 2 muestra la función asociada al ejemplo anterior. ${\displaystyle \lambda (x)}$

Figura 2. Función de pertenencia al conjunto asociada a los 6 intervalos.

Intersección relajada de cajas

Para calcular la intersección q -relajada de m cajas de , proyectamos todas las m cajas con respecto a los n ejes. Para cada uno de los n grupos de m intervalos, calculamos la intersección q -relajada. Devolvemos el producto cartesiano de los n intervalos resultantes. ^[2] La Figura 3 proporciona una ilustración de la intersección 4-relajada de 6 cajas. Cada punto de la caja roja pertenece a 4 de las 6 cajas. ${\displaystyle R^{n}}$

Figura 3. El cuadro rojo corresponde a la intersección relajada de los 6 cuadros.

Unión relajada

La unión q -relajada de se define por ${\displaystyle X_{1},\dots ,X_{m}}$

${\displaystyle {\overset {\{q\}}{\bigcup }}X_{i}=\bigcap ^{\{m-1-q\}}X_{i}}$

Nótese que cuando q = 0, la unión/intersección relajada corresponde a la unión/intersección clásica. Más precisamente, tenemos

${\displaystyle \bigcap ^{\{0\}}X_{i}=\bigcap X_{i}}$

y

${\displaystyle {\overset {\{0\}}{\bigcup }}X_{i}=\bigcup X_{i}}$

Ley de De Morgan

Si denota el conjunto complementario de , tenemos ${\displaystyle {\overline {X}}}$ ${\displaystyle X_{i}}$

${\displaystyle {\overline {\bigcap ^{\{q\}}X_{i}}}={\overset {\{q\}}{\bigcup }}{\overline {X_{i}}}}$

${\displaystyle {\overline {{\overset {\{q\}}{\bigcup }}X_{i}}}=\bigcap ^{\{q\}}{\overline {X_{i}}}.}$

Como consecuencia

${\displaystyle {\overline {\bigcap \limits ^{\{q\}}X_{i}}}={\overline {{\overset {\{m-q-1\}}{\bigcup }}X_{i}}}=\bigcap ^{\{m-q-1\}}{\overline {X_{i}}}}$

Relajación de los contratistas

Sean m contratistas para los conjuntos , entonces ${\displaystyle C_{1},\dots ,C_{m}}$ ${\displaystyle X_{1},\dots ,X_{m}}$

${\displaystyle C([x])=\bigcap ^{\{q\}}C_{i}([x]).}$

es un contratista para y ${\displaystyle X^{\{q\}}}$

${\displaystyle {\overline {C}}([x])=\bigcap ^{\{m-q-1\}}{\overline {C}}_{i}([x])}$

es un contratista para , donde ${\displaystyle {\overline {X}}^{\{q\}}}$

${\displaystyle {\overline {C}}_{1},\dots ,{\overline {C}}_{m}}$

son contratistas para

${\displaystyle {\overline {X}}_{1},\dots ,{\overline {X}}_{m}.}$

Combinado con un algoritmo de ramificación y acotación como SIVIA (Set Inversion Via Interval Analysis), se puede calcular la intersección q -relajada de m subconjuntos de . ${\displaystyle R^{n}}$

Aplicación a la estimación de error acotado

La intersección q -relajada se puede utilizar para localización robusta ^{[3] [4]} o para seguimiento. ^[5]

También se pueden implementar observadores robustos utilizando las intersecciones relajadas para que sean robustos con respecto a los valores atípicos. ^[6]

Proponemos aquí un ejemplo sencillo ^[7] para ilustrar el método. Consideremos un modelo cuya salida i -ésima viene dada por

${\displaystyle f_{i}(p)={\frac {1}{\sqrt {2\pi p_{2}}}}\exp(-{\frac {(t_{i}-p_{1})^{2}}{2p_{2}}})}$

donde . Supongamos que tenemos ${\displaystyle p\in R^{2}}$

${\displaystyle f_{i}(p)\in [y_{i}]}$

donde y están dados por la siguiente lista ${\displaystyle t_{i}}$ ${\displaystyle [y_{i}]}$

${\displaystyle \{(1,[0;0.2]),(2,[0.3;2]),(3,[0.3;2]),(4,[0.1;0.2]),(5,[0.4;2]),(6,[-1;0.1])\}}$

Los conjuntos para los diferentes se representan en la Figura 4. ${\displaystyle \lambda ^{-1}(q)}$ ${\displaystyle q}$

Figura 4. Conjunto de todos los vectores de parámetros consistentes con exactamente 6 barras de datos q (pintadas en rojo), para q=1,2,3,4,5.

Referencias

1. Jaulin, L.; Walter, E.; Didrit, O. (1996). Limitación robusta garantizada de parámetros no lineales (PDF) . En Actas de la multiconferencia IMACS de CESA'96 (Simposio sobre modelado, análisis y simulación).
2. Jaulin, L.; Walter, E. (2002). "Estimación minimax no lineal robusta garantizada" (PDF) . IEEE Transactions on Automatic Control . 47 (11): 1857–1864. doi :10.1109/TAC.2002.804479.
3. Kieffer, M.; Walter, E. (2013). Caracterización garantizada de regiones de confianza no asintóticas exactas en la estimación de parámetros no lineales (PDF) . En Actas del Simposio IFAC sobre sistemas de control no lineal, Toulouse: Francia (2013).
4. 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.
5. Langerwisch, M.; Wagner, B. (2012). "Seguimiento garantizado de robots móviles mediante propagación robusta de restricciones de intervalo". Robótica inteligente y aplicaciones ..
6. Jaulin, L. (2009). "Estimación robusta del estado de pertenencia a un conjunto; aplicación a la robótica submarina" (PDF) . Automatica . 45 : 202–206. doi :10.1016/j.automatica.2008.06.013.
7. Jaulin, L.; Kieffer, M.; Walter, E.; Meizel, D. (2002). "Estimación no lineal robusta garantizada con aplicación a la localización de robots" (PDF) . IEEE Transactions on Systems, Man, and Cybernetics - Part C: Applications and Reviews . 32 (4): 374–381. doi :10.1109/TSMCC.2002.806747. S2CID  17436801. Archivado desde el original (PDF) el 28 de abril de 2011.