En optimización matemática , la optimización restringida (en algunos contextos llamada optimización por restricciones ) es el proceso de optimizar una función objetivo con respecto a algunas variables en presencia de restricciones sobre esas variables. La función objetivo es una función de costo o una función de energía , que se debe minimizar , o una función de recompensa o una función de utilidad , que se debe maximizar . Las restricciones pueden ser restricciones duras , que establecen condiciones para las variables que se requieren satisfacer, o restricciones blandas , que tienen algunos valores de variables que se penalizan en la función objetivo si, y en función del grado en que, las condiciones de las variables no se satisfacen.
El problema de optimización con restricciones (COP) es una generalización significativa del modelo clásico de problema de satisfacción de restricciones (CSP). [1] El COP es un CSP que incluye una función objetivo que se optimizará. Se utilizan muchos algoritmos para manejar la parte de optimización.
Un problema general de minimización restringida puede escribirse de la siguiente manera: [2]
donde y son restricciones que se requieren satisfacer (estas se denominan restricciones duras ), y es la función objetivo que necesita optimizarse sujeta a las restricciones.
En algunos problemas, a menudo llamados problemas de optimización de restricciones , la función objetivo es en realidad la suma de funciones de costo, cada una de las cuales penaliza el grado (si lo hay) en el que se viola una restricción blanda (una restricción que se prefiere pero no se exige satisfacer).
Muchos algoritmos de optimización con restricciones pueden adaptarse al caso sin restricciones, a menudo mediante el uso de un método de penalización . Sin embargo, los pasos de búsqueda realizados por el método sin restricciones pueden ser inaceptables para el problema con restricciones, lo que conduce a una falta de convergencia. Esto se conoce como el efecto Maratos. [3]
Para problemas muy simples, digamos una función de dos variables sujeta a una única restricción de igualdad, es más práctico aplicar el método de sustitución. [4] La idea es sustituir la restricción en la función objetivo para crear una función compuesta que incorpore el efecto de la restricción. Por ejemplo, supongamos que el objetivo es maximizar sujeto a . La restricción implica , que puede sustituirse en la función objetivo para crear . La condición necesaria de primer orden da , que puede resolverse para y, en consecuencia, .
Si el problema restringido tiene solo restricciones de igualdad, se puede utilizar el método de multiplicadores de Lagrange para convertirlo en un problema sin restricciones cuyo número de variables es el número original de variables más el número original de restricciones de igualdad. Alternativamente, si las restricciones son todas restricciones de igualdad y son todas lineales, se pueden resolver para algunas de las variables en términos de las otras, y las primeras se pueden sustituir fuera de la función objetivo, dejando un problema sin restricciones en un número menor de variables.
Con restricciones de desigualdad, el problema se puede caracterizar en términos de las condiciones de optimalidad geométrica, condiciones de Fritz John y condiciones de Karush–Kuhn–Tucker , bajo las cuales se pueden resolver problemas simples.
Si la función objetivo y todas las restricciones estrictas son lineales y algunas restricciones estrictas son desigualdades, entonces el problema es un problema de programación lineal . Esto se puede resolver mediante el método simplex , que generalmente funciona en tiempo polinomial en el tamaño del problema, pero no se garantiza que lo haga, o mediante métodos de punto interior, que se garantiza que funcionan en tiempo polinomial.
Si la función objetivo o algunas de las restricciones son no lineales y algunas restricciones son desigualdades, entonces el problema es un problema de programación no lineal .
Si todas las restricciones estrictas son lineales y algunas son desigualdades, pero la función objetivo es cuadrática, el problema es un problema de programación cuadrática . Es un tipo de programación no lineal. Todavía se puede resolver en tiempo polinomial mediante el método del elipsoide si la función objetivo es convexa ; de lo contrario, el problema puede ser NP estricto .
Al permitir restricciones de desigualdad, el enfoque KKT para la programación no lineal generaliza el método de los multiplicadores de Lagrange. Puede aplicarse en condiciones de diferenciabilidad y convexidad.
La optimización de restricciones se puede resolver mediante algoritmos de ramificación y acotación . Se trata de algoritmos de retroceso que almacenan el coste de la mejor solución encontrada durante la ejecución y lo utilizan para evitar parte de la búsqueda. Más precisamente, siempre que el algoritmo encuentra una solución parcial que no se puede ampliar para formar una solución de mejor coste que el mejor coste almacenado, el algoritmo retrocede, en lugar de intentar ampliar esta solución.
Suponiendo que se pretende minimizar el costo, la eficiencia de estos algoritmos depende de cómo se evalúe el costo que se puede obtener al extender una solución parcial. De hecho, si el algoritmo puede retroceder a partir de una solución parcial, se omite parte de la búsqueda. Cuanto menor sea el costo estimado, mejor será el algoritmo, ya que es más probable que un costo estimado más bajo sea menor que el mejor costo de la solución encontrada hasta el momento.
Por otra parte, este coste estimado no puede ser inferior al coste efectivo que se puede obtener ampliando la solución, ya que de lo contrario el algoritmo podría dar marcha atrás aunque exista una solución mejor que la mejor encontrada hasta el momento. Como resultado, el algoritmo requiere un límite superior al coste que se puede obtener ampliando una solución parcial, y este límite superior debe ser lo más pequeño posible.
Una variación de este enfoque, denominada método de Hansen, utiliza métodos de intervalo . [5] Implementa inherentemente restricciones rectangulares.
Una forma de evaluar este límite superior para una solución parcial es considerar cada restricción blanda por separado. Para cada restricción blanda, se supone el valor máximo posible para cualquier asignación a las variables no asignadas. La suma de estos valores es un límite superior porque las restricciones blandas no pueden asumir un valor mayor. Es exacto porque los valores máximos de las restricciones blandas pueden derivar de diferentes evaluaciones: una restricción blanda puede ser máxima para mientras que otra restricción es máxima para .
Este método [6] ejecuta un algoritmo de ramificación y acotación en problemas, donde es el número de variables. Cada uno de estos problemas es el subproblema obtenido al eliminar una secuencia de variables del problema original, junto con las restricciones que las contienen. Una vez resuelto el problema sobre las variables, su costo óptimo se puede utilizar como límite superior al resolver los otros problemas.
En particular, el costo estimado de una solución que tiene variables no asignadas se suma al costo que se deriva de las variables evaluadas. Virtualmente, esto corresponde a ignorar las variables evaluadas y resolver el problema con las variables no asignadas, excepto que el último problema ya se ha resuelto. Más precisamente, el costo de las restricciones blandas que contienen variables asignadas y no asignadas se estima como se indicó anteriormente (o utilizando otro método arbitrario); el costo de las restricciones blandas que contienen solo variables no asignadas se estima en cambio utilizando la solución óptima del problema correspondiente, que ya se conoce en este punto.
Existe una similitud entre el método de búsqueda de muñecas rusas y la programación dinámica . Al igual que la programación dinámica, la búsqueda de muñecas rusas resuelve subproblemas para resolver el problema completo. Pero, mientras que la programación dinámica combina directamente los resultados obtenidos en los subproblemas para obtener el resultado del problema completo, la búsqueda de muñecas rusas solo los usa como límites durante su búsqueda.
El algoritmo de eliminación de cubos se puede adaptar para la optimización de restricciones. Una variable dada se puede eliminar del problema reemplazando todas las restricciones suaves que la contienen con una nueva restricción suave. El costo de esta nueva restricción se calcula suponiendo un valor máximo para cada valor de la variable eliminada. Formalmente, si es la variable que se eliminará, son las restricciones suaves que la contienen y son sus variables excepto , la nueva restricción suave se define por:
La eliminación de cubos funciona con un ordenamiento (arbitrario) de las variables. Cada variable está asociada a un cubo de restricciones; el cubo de una variable contiene todas las restricciones que tienen la variable en el orden más alto. La eliminación de cubos procede de la última variable a la primera. Para cada variable, todas las restricciones del cubo se reemplazan como se indicó anteriormente para eliminar la variable. La restricción resultante se coloca luego en el cubo apropiado.
