Muchos algoritmos de optimización sin restricciones pueden adaptarse al caso restringido, a menudo mediante el uso de un método de penalización. Sin embargo, los pasos de búsqueda realizados por el método no restringido pueden ser inaceptables para el problema restringido, lo que lleva a una falta de convergencia. Esto se conoce como el efecto Maratos.
Restricciones de igualdadEditar
Método de sustituciónEditar
Para problemas muy simples, digamos una función de dos variables sujeta a una única restricción de igualdad, lo más práctico es aplicar el método de sustitución. 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 f ( x , y ) = x ⋅ y {\displaystyle f(x,y)=x\cdot y}
sujeto a x + y = 10 {\displaystyle x+y=10}
. La restricción implica y = 10 – x {\displaystyle y=10-x}
, que puede sustituirse en la función objetivo para crear p ( x ) = x ( 10 – x ) = 10 x – x 2 {\displaystyle p(x)=x(10-x)=10x-x^{2}
. La condición necesaria de primer orden da ∂ p ∂ x = 10 – 2 x = 0 {\displaystyle {\frac {\partial p}{\partial x}}=10-2x=0}
, que se puede resolver para x = 5 {\displaystyle x=5}
y, en consecuencia, y = 10 – 5 = 5 {\displaystyle y=10-5=5}
.
Multiplicador de LagrangeEditar
Si el problema restringido sólo tiene 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 son todas lineales, pueden resolverse para algunas de las variables en términos de las otras, y las primeras pueden sustituirse fuera de la función objetivo, dejando un problema sin restricciones en un número menor de variables.
Restricciones de desigualdadEditar
Con las restricciones de desigualdad, el problema se puede caracterizar en términos de las condiciones de optimalidad geométrica, las condiciones de Fritz John y las condiciones de Karush-Kuhn-Tucker, bajo las cuales los problemas simples pueden ser resolubles.
Programación linealEditar
Si la función objetivo y todas las restricciones duras son lineales y algunas restricciones duras son desigualdades, entonces el problema es un problema de programación lineal. Se puede resolver por el método simplex, que suele funcionar en tiempo polinómico en el tamaño del problema pero no está garantizado que lo haga, o por métodos de punto interior que están garantizados para trabajar en tiempo polinómico.
Programación no linealEditar
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.
Programación cuadráticaEditar
Si todas las restricciones duras 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 por el método del elipsoide si la función objetivo es convexa; de lo contrario, el problema puede ser NP duro.
Condiciones KKTEditar
Permitiendo restricciones de desigualdad, el enfoque KKT a la programación no lineal generaliza el método de los multiplicadores de Lagrange. Puede aplicarse en condiciones de diferenciabilidad y convexidad.
Branch and boundEdit
La optimización de restricciones puede resolverse mediante algoritmos branch-and-bound. Se trata de algoritmos de backtracking 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 concretamente, cada vez que el algoritmo encuentra una solución parcial que no puede extenderse para formar una solución de mejor coste que el mejor coste almacenado, el algoritmo retrocede, en lugar de intentar extender esta solución.
Suponiendo que el coste debe minimizarse, la eficiencia de estos algoritmos depende de cómo se evalúe el coste que puede obtenerse al extender una solución parcial. En efecto, si el algoritmo puede retroceder desde una solución parcial, se salta parte de la búsqueda. Cuanto menor sea el coste estimado, mejor será el algoritmo, ya que es más probable que un coste estimado menor sea el mejor coste de la solución encontrada hasta el momento.
Por otro lado, este coste estimado no puede ser menor que el coste efectivo que se puede obtener al extender la solución, ya que de lo contrario el algoritmo podría retroceder mientras existe una solución mejor que la mejor encontrada hasta el momento. Como resultado, el algoritmo requiere un límite superior en el coste que se puede obtener de la ampliación de 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 utiliza métodos de intervalo. Implementa intrínsecamente las restricciones rectangulares.
Funciones de limitación de primera elecciónEditar
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 asume el valor máximo posible para cualquier asignación a las variables no asignadas. La suma de estos valores es una cota superior porque las restricciones blandas no pueden asumir un valor superior. Es exacta porque los valores máximos de las restricciones blandas pueden derivar de diferentes evaluaciones: una restricción blanda puede ser máxima para x = a {\displaystyle x=a}
mientras que otra restricción es máxima para x = b {\displaystyle x=b}
.
Muñeca rusa searchEdit
Este método ejecuta un algoritmo branch-and-bound sobre n {\displaystyle n}
problemas, donde n {\displaystyle n}
es el número de variables. Cada uno de estos problemas es el subproblema que se obtiene al eliminar una secuencia de variables x 1 , … , x i {\displaystyle x_{1},\ldots ,x_{i}}.
del problema original, junto con las restricciones que las contienen. Después del problema sobre las variables x i + 1 , … , x n {\displaystyle x_{i+1},\ldots ,x_{n}}
se resuelve, su coste óptimo puede usarse como cota superior mientras se resuelven los otros problemas,
En particular, la estimación del coste de una solución que tenga x i + 1 , … , x n {displaystyle x_{i+1},\ldots ,x_{n}}
como variables no asignadas se añade al coste que se deriva de las variables evaluadas. Prácticamente, esto corresponde a ignorar las variables evaluadas y resolver el problema sobre las no asignadas, con la salvedad de que este último problema ya ha sido resuelto. Más precisamente, el coste de las restricciones blandas que contienen tanto variables asignadas como no asignadas se estima como arriba (o usando otro método arbitrario); el coste de las restricciones blandas que contienen sólo variables no asignadas se estima en cambio usando la solución óptima del problema correspondiente, que ya se conoce en este punto.
Hay una similitud entre el método de Búsqueda de la Muñeca Rusa y la Programación Dinámica. Al igual que la Programación Dinámica, la Búsqueda de la Muñeca Rusa 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 la Muñeca Rusa sólo los utiliza como límites durante su búsqueda.
Eliminación de cubosEditar
El algoritmo de eliminación de cubos puede adaptarse para la optimización de restricciones. Una variable dada puede ser efectivamente eliminada del problema sustituyendo todas las restricciones blandas que la contienen por una nueva restricción blanda. El coste de esta nueva restricción se calcula asumiendo un valor máximo para cada valor de la variable eliminada. Formalmente, si x {\displaystyle x}
es la variable a eliminar, C 1 , … , C n {\displaystyle C_{1},\ldots ,C_{n}}
son las restricciones blandas que la contienen, e y 1 , … , y m {\displaystyle y_{1},\ldots ,y_{m}}
son sus variables excepto x {\displaystyle x}
, la nueva restricción blanda se define por: C ( y 1 = a 1 , … , y n = a n ) = max a ∑ i C i ( x = a , y 1 = a 1 , … , y n = a n ) . {\displaystyle C(y_{1}=a_{1},\ldots ,y_{n}=a_{n})={max _{a}{suma _{i}C_{i}(x=a,y_{1}=a_{1},\ldots ,y_{n}=a_{n}).}
La eliminación de cubos funciona con un ordenamiento (arbitrario) de las variables. A cada variable se le asocia un cubo de restricciones; el cubo de una variable contiene todas las restricciones que tiene la variable más alta en el orden. La eliminación de cubos procede desde la última variable hasta la primera. Para cada variable, se sustituyen todas las restricciones del cubo como se ha indicado anteriormente para eliminar la variable. La restricción resultante se coloca en el cubo apropiado.