Contratista de intervalos

En matemáticas , un contratista de intervalo (o contratista para abreviar) ^{[ 1 ]} asociado a un conjunto${\displaystyle X}$es un operador${\displaystyle C}$que se asocia a un hiperrectángulo${\displaystyle [x]}$en${\displaystyle {\mathbf {R}}^{n}}$otra caja${\displaystyle C([x])}$de${\displaystyle {\mathbf {R}}^{n}}$ De tal manera que siempre se cumplan las dos propiedades siguientes:

• ${\displaystyle C([x])\subset [x]}$(propiedad contractual)
• ${\displaystyle C([x])\cap X=[x]\cap X}$(propiedad de completitud)

Un contratista asociado a una restricción (como una ecuación o una desigualdad ) es un contratista asociado al conjunto${\displaystyle X}$de todos${\displaystyle x}$que satisfacen la restricción. Los contratistas hacen posible mejorar la eficiencia de los algoritmos de ramificación y acotación utilizados clásicamente en el análisis de intervalos .

Un contratista C es monótono si tenemos ${\displaystyle [x]\subset [y]\Rightarrow C([x])\subset C([y])}$.

Es mínimo si para todas las cajas [ x ], tenemos ${\displaystyle C([x])=[[x]\cap X]}$, donde [ A ] es la envoltura del intervalo del conjunto A , es decir, la caja más pequeña que encierra a A .

El contratista C es delgado si para todos los puntos x , ${\displaystyle C(\{x\})=\{x\}\cap X}$ donde { x } denota la caja degenerada que encierra a x como un solo punto.

El contratista C es idempotente si para todas las cajas [ x ], tenemos ${\displaystyle C\circ C([x])=C([x]).}$

El contratista C es convergente si para todas las secuencias [ x ]( k ) de cajas que contienen x , tenemos ${\displaystyle [x](k)\rightarrow x\implies C([x](k))\rightarrow \{x\}\cap X.}$

La figura 1 representa el conjunto X pintado de gris y algunas cajas, algunas de ellas degeneradas (es decir, corresponden a elementos únicos). La figura 2 representa estas cajas después de la contracción . Nótese que el contractor no ha eliminado ningún punto de X. El contractor es mínimo para la caja cian, pero pesimista para la verde. Todas las cajas azules degeneradas se contraen a la caja vacía . La caja magenta y la roja no se pueden contraer.

Se pueden realizar algunas operaciones en contratistas para construir contratistas más complejos. ^{[ 2 ]} La intersección , la unión , la composición y la repetición se definen de la siguiente manera.

${\displaystyle (C_{1}\cap C_{2})([x])=C_{1}([x])\cap C_{2}([x])}$

${\displaystyle (C_{1}\cup C_{2})([x])=[C_{1}([x])\cup C_{2}([x])]}$

${\displaystyle (C_{1}\circ C_{2})([x])=C_{1}(C_{2}([x]))}$

${\displaystyle C^{\infty }([x])=C\circ C\circ C\circ \cdots ([x])}$

Existen diferentes maneras de construir contratistas asociados a ecuaciones e inecuaciones, por ejemplo, f ( x ) en [ y ]. La mayoría se basan en aritmética de intervalos. Uno de los más eficientes y sencillos es el contratista hacia adelante/hacia atrás (también llamado HC4-revisado). ^{[ 3 ] [ 4 ]}

El principio consiste en evaluar f ( x ) mediante aritmética de intervalos (este es el paso hacia adelante). El intervalo resultante se interseca con [ y ]. A continuación _, se realiza una evaluación hacia atrás de f ( x ) para reducir los intervalos para xᵢ (este es el paso hacia atrás). Ahora ilustramos el principio con un ejemplo sencillo.

Considere la restricción ${\displaystyle (x_{1}+x_{2})\cdot x_{3}\in [1,2].}$ Podemos evaluar la función f ( x ) introduciendo las dos variables intermedias a y b , de la siguiente manera:

${\displaystyle a=x_{1}+x_{2}}$

${\displaystyle b=a\cdot x_{3}}$

Las dos restricciones anteriores se denominan restricciones hacia adelante . Obtenemos las restricciones hacia atrás tomando cada restricción hacia adelante en orden inverso y aislando cada variable en el lado derecho. Obtenemos

${\displaystyle x_{3}={\frac {b}{a}}}$

${\displaystyle a={\frac {b}{x_{3}}}}$

${\displaystyle x_{1}=a-x_{2}}$

${\displaystyle x_{2}=a-x_{1}}$

El contratista resultante hacia adelante/atrás ${\displaystyle C([x_{1}],[x_{2}],[x_{3}])}$ se obtiene evaluando las restricciones hacia adelante y hacia atrás utilizando el análisis de intervalos .

${\displaystyle [a]=[x_{1}]+[x_{2}]}$

${\displaystyle [b]=[a]\cdot [x_{3}]}$

${\displaystyle [b]=[b]\cap [1,2]}$

${\displaystyle [x_{3}]=[x_{3}]\ \cap \ {\frac {[b]}{[a]}}}$

${\displaystyle [a]=[a]\cap {\frac {[b]}{[x_{3}]}}}$

${\displaystyle [x_{1}]=[x_{1}]\ \cap \ \ [a]-[x_{2}]}$

${\displaystyle [x_{2}]=[x_{2}]\ \cap \ \ [a]-[x_{1}]}$