Optimización con restricciones
En la optimización matemática, la optimización con restricciones es el proceso de optimización de una función objetivo con respecto a algunas variables con restricciones en las mismas. La función objetivo es, o bien una función de coste o función de energía que debe ser minimizada, o una función de recompensa o función de utilidad, que ha de ser maximizado. Las restricciones pueden ser tanto restricciones duras que establecen condiciones para las variables que se requieren para estar satisfecha, o restricciones blandas que tienen algunos valores de las variables que están penalizados en la función objetivo si, y basados en la medida en que, las condiciones en las variables no son satisfecho.
Un problema general de minimización restringida se puede escribir como sigue:
donde para y para son las restricciones que se requieren para ser satisfacer el resultado; éstas se llaman restricciones duras.
En algunos problemas, a menudo llamados problemas de optimización con restricciones, la función objetivo es en realidad la suma de funciones de coste, cada una penaliza la medida (si la hay) en la que una restricción blanda (una restricción que se prefiere pero no se requiere para ser satisfecho) es violada.
Muchos algoritmos de optimización con restricciones se pueden adaptar al caso sin restricciones, a menudo a través del uso de un método de penalizaciones. Sin embargo, los pasos de búsqueda obtenidas por el método sin restricciones pueden ser inaceptables para el problema restringida, lo que lleva a una falta de convergencia. Esto se conoce como el efecto Maratos.
Si el problema restringido sólo tiene restricciones de igualdad, el método de los multiplicadores de Lagrange puede ser utilizado para convertirlo en un problema sin restricciones cuyo número de variables es el número original de las variables más el número original de restricciones de igualdad. Alternativamente, si las restricciones son todas las restricciones de igualdad y son lineales, que se pueden resolver para algunas de las variables en términos de los otros, y la antigua pueden ser sustituidos de la función objetivo, dejando un problema sin restricciones en un número menor de variables.
Con restricciones de desigualdad, el problema puede ser caracterizado en términos de las condiciones de Karush-Kuhn-Tucker, en la que los problemas pueden ser resueltos.
Si la función objetivo y todas las restricciones son lineales, entonces el problema es problema de programación lineal. Esto se puede resolver por el método simplex. Generalmente funciona en tiempo polinomial en el tamaño del problema, pero no se garantiza, o mediante métodos de puntos interiores que se garantiza que funcionan en tiempo polinomial.
Si todas las restricciones duras son lineales, pero la función objetivo es cuadrática, el problema es un problema de programación cuadrático . Todavía se puede resolver en tiempo polinomial por el método del elipsoide si la función objetivo es convexa ; de lo contrario, el problema es NP completo .
La optimización de restricciones puede resolverse mediante algoritmos de Ramificación y poda. Estos son algoritmos de back-tracking que almacenan el costo de la mejor solución encontrada durante la ejecución y la usan para evitar parte de la búsqueda. Más precisamente, cada vez que el algoritmo encuentra una solución parcial que no se puede extender 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 el costo se minimice, 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 dar marcha atrás desde una solución parcial, parte de la búsqueda se omite. Cuanto menor sea el costo estimado, mejor será el algoritmo, ya que es más probable que un menor costo estimado sea menor que el mejor costo de solución encontrado hasta ahora.
Por otro lado, este costo estimado no puede ser menor que el costo efectivo que se puede obtener extendiendo la solución, ya que de lo contrario el algoritmo podría retroceder mientras existe una solución mejor que la mejor hasta ahora. 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, llamado método de Hansen, usa métodos de intervalo. Implementa intrínsecamente 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 blandas no pueden asumir un valor más alto. Es exacto porque los valores máximos de restricciones suaves pueden derivar de evaluaciones diferentes: una restricción suave puede ser máxima para . mientras que otra restricción es máxima para .
