En optimización matemática , la optimización restringida (en algunos contextos llamada optimización de 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 costos o una función de energía , que debe minimizarse , o una función de recompensa o de utilidad , que debe maximizarse . Las restricciones pueden ser restricciones estrictas , que establecen condiciones para las variables que deben cumplirse, o restricciones suaves , que tienen algunos valores de variables que se penalizan en la función objetivo si, y en función de la medida, se cumplen las condiciones de las variables. no están satisfechos.
El problema de optimización restringida (COP) es una generalización significativa del modelo clásico de problema de satisfacción de restricciones (CSP). [1] COP es un CSP que incluye una función objetivo a optimizar. Se utilizan muchos algoritmos para manejar la parte de optimización.
Un problema general de minimización restringida se puede escribir de la siguiente manera: [2]
donde y son restricciones que deben cumplirse (se denominan restricciones estrictas ), y es la función objetivo que debe 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 costos, cada una de las cuales penaliza el grado (si lo hay) en el que se cumple una restricción suave (una restricción que se prefiere pero que no se requiere satisfacer). violado.
Muchos algoritmos de optimización restringidos se pueden adaptar 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 restringido, lo que lleva a una falta de convergencia. Esto se conoce como efecto Maratos. [3]
Para problemas muy simples, digamos una función de dos variables sujetas a una única restricción de igualdad, lo más práctico es 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 a 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 los 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 de igualdad y 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 optimización geométrica, las condiciones de Fritz John y las condiciones de Karush-Kuhn-Tucker , bajo las cuales problemas simples pueden tener solución.
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 normalmente funciona en tiempo polinómico en el tamaño del problema pero no está garantizado, o mediante métodos de punto interior que se garantiza que funcionan en tiempo polinómico.
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 polinómico mediante el método del elipsoide si la función objetivo es convexa ; de lo contrario, el problema puede ser NP difícil .
Al permitir restricciones de desigualdad, el enfoque KKT para la programación no lineal generaliza el método de los multiplicadores de Lagrange. Se puede aplicar bajo diferenciabilidad y convexidad.
La optimización de restricciones se puede resolver mediante algoritmos de ramificación y limitació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 puede extenderse para formar una solución de mejor costo que el mejor costo almacenado, el algoritmo retrocede, en lugar de intentar extender esta solución.
Suponiendo que se debe minimizar el costo, la eficiencia de estos algoritmos depende de cómo se evalúa el costo que se puede obtener al extender una solución parcial. De hecho, si el algoritmo puede retroceder desde 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 solución encontrado hasta el momento.
Por otro lado, 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 retroceder mientras exista una solución mejor que la mejor encontrada hasta el momento. Como resultado, el algoritmo requiere un límite superior en el costo que se puede obtener al extender una solución parcial, y este límite superior debe ser lo más pequeño posible.
Una variación de este enfoque llamada 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 suave, 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 suaves no pueden asumir un valor más alto. Es exacta porque los valores máximos de las restricciones suaves pueden derivar de diferentes evaluaciones: una restricción suave 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 vinculación en problemas, donde está 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 de variables , su costo óptimo se puede utilizar como límite superior mientras se resuelven los otros problemas.
En particular, la estimación del costo de una solución que tiene como variables no asignadas se suma al costo que se deriva de las variables evaluadas. Prácticamente esto corresponde a ignorar las variables evaluadas y resolver el problema sobre las no asignadas, excepto que este último problema ya ha sido 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); En cambio, el costo de las restricciones suaves que contienen solo variables no asignadas se estima utilizando la solución óptima del problema correspondiente, que ya se conoce en este momento.
Existe 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, Russian Doll Search resuelve subproblemas para resolver el problema completo. Pero, mientras que la Programación Dinámica combina directamente los resultados obtenidos en subproblemas para obtener el resultado del problema completo, Russian Doll Search sólo los utiliza como límites durante su búsqueda.
El algoritmo de eliminación de depósitos se puede adaptar para la optimización de restricciones. De hecho, una variable dada puede eliminarse 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 va a eliminar, las restricciones suaves la contienen y sus variables excepto , la nueva restricción suave se define por:
La eliminación de depósitos funciona con un ordenamiento (arbitrario) de las variables. Cada variable está asociada a un grupo de restricciones; el depósito de una variable contiene todas las restricciones que tienen la variable más alta en el orden. La eliminación del depósito procede de la última variable a la primera. Para cada variable, todas las restricciones del depósito se reemplazan como se indicó anteriormente para eliminar la variable. Luego, la restricción resultante se coloca en el depósito apropiado.
