Restricción (matemáticas)

En matemáticas , una restricción es una condición de un problema de optimización que la solución debe satisfacer. Existen varios tipos de restricciones , principalmente restricciones de igualdad , de desigualdad y de enteros . El conjunto de soluciones candidatas que satisfacen todas las restricciones se denomina conjunto factible . ^{[ 1 ]}

El siguiente es un problema de optimización sencillo:

${\displaystyle \min f(\mathbf {x} )=x_{1}^{2}+x_{2}^{4}}$

sujeto a

${\displaystyle x_{1}\geq 1}$

y

${\displaystyle x_{2}=1,}$

dónde${\displaystyle \mathbf {x} }$denota el vector ( x ₁ , x ₂ ).

En este ejemplo, la primera línea define la función que se va a minimizar (denominada función objetivo , función de pérdida o función de coste). La segunda y la tercera línea definen dos restricciones: la primera es una restricción de desigualdad y la segunda, una restricción de igualdad. Estas dos restricciones son estrictas , lo que significa que deben cumplirse; definen el conjunto factible de soluciones candidatas.

Sin las restricciones, la solución sería (0,0), donde${\displaystyle f(\mathbf {x} )}$tiene el valor más bajo. Pero esta solución no satisface las restricciones. La solución del problema de optimización con restricciones mencionado anteriormente es${\displaystyle \mathbf {x} =(1,1)}$, que es el punto con el valor más pequeño de${\displaystyle f(\mathbf {x} )}$que satisface las dos restricciones.

• Si una restricción de desigualdad se cumple con igualdad en el punto óptimo, se dice que la restricción esvinculante , ya que el puntonose puede variar en la dirección de la restricción aunque hacerlo mejoraría el valor de la función objetivo.
• Si una restricción de desigualdad se cumple como una desigualdad estricta en el punto óptimo (es decir, no se cumple con la igualdad), se dice que la restricción esNo vinculante , ya que el puntopodríavariar en la dirección de la restricción, aunque no sería óptimo hacerlo. Bajo ciertas condiciones, como por ejemplo en la optimización convexa, si una restricción no es vinculante, el problema de optimización tendría la misma solución incluso en ausencia de dicha restricción.
• Si una restricción no se cumple en un punto dado, se dice que ese punto es infactible .

Si el problema exige que se cumplan las restricciones, como en el ejemplo anterior, a estas se las denomina restricciones estrictas . Sin embargo, en algunos problemas, conocidos como problemas de satisfacción de restricciones flexibles , se prefiere, pero no se exige, que se cumplan ciertas restricciones; estas restricciones no obligatorias se conocen como restricciones flexibles . Las restricciones flexibles surgen, por ejemplo, en la planificación basada en preferencias . En un problema MAX-CSP , se permite que se infrinjan varias restricciones, y la calidad de la solución se mide por el número de restricciones satisfechas.

Las restricciones globales ^{[ 2 ]} son ​​restricciones que representan una relación específica sobre varias variables, tomadas en conjunto. Algunas de ellas, como la alldifferentrestricción, pueden reescribirse como una conjunción de restricciones atómicas en un lenguaje más simple: la alldifferentrestricción se cumple sobre n variables.${\displaystyle x_{1}...x_{n}}$y se satisface si las variables toman valores que son diferentes entre sí. Es semánticamente equivalente a la conjunción de desigualdades.${\displaystyle x_{1}\neq x_{2},x_{1}\neq x_{3}...,x_{2}\neq x_{3},x_{2}\neq x_{4}...x_{n-1}\neq x_{n}}$Otras restricciones globales amplían la expresividad del marco de restricciones. En este caso, suelen capturar una estructura típica de problemas combinatorios. Por ejemplo, la regularrestricción expresa que una secuencia de variables es aceptada por un autómata finito determinista .

Las restricciones globales se utilizan ^{[ 3 ]} para simplificar el modelado de problemas de satisfacción de restricciones , ampliar la expresividad de los lenguajes de restricciones y mejorar la resolución de las mismas : de hecho, al considerar todas las variables, se pueden identificar situaciones inviables en una etapa más temprana del proceso de resolución. Muchas de las restricciones globales están referenciadas en un catálogo en línea.

• Beveridge, Gordon SG; Schechter, Robert S. (1970). «Características esenciales en la optimización» . Optimización: teoría y práctica . Nueva York: McGraw-Hill. págs. 5-8 . ISBN  0-07-005128-3.

• Preguntas frecuentes sobre programación no lineal. Archivado el 30/10/2019 en Wayback Machine.
• Glosario de programación matemática archivado el 28/03/2010 en Wayback Machine.