En la optimización restringida , un campo de las matemáticas , una función de barrera es una función continua cuyo valor en un punto aumenta hasta el infinito cuando el punto se acerca al límite de la región factible de un problema de optimización. [1] [2] Estas funciones se utilizan para reemplazar las restricciones de desigualdad por un término de penalización en la función objetivo que es más fácil de manejar.
Los dos tipos más comunes de funciones de barrera son las funciones de barrera inversas y las funciones de barrera logarítmicas. La reanudación del interés en las funciones de barrera logarítmica fue motivada por su conexión con los métodos de punto interior primal-dual .
Motivación
Considere el siguiente problema de optimización restringida:
- minimizar f ( x )
- sujeto ax ≥ b
donde b es una constante. Si se desea eliminar la restricción de desigualdad, el problema puede reformularse como
- minimizar f ( x ) + c ( x ) ,
- donde c ( x ) = ∞ si x < b , y cero en caso contrario.
Este problema es equivalente al primero. Elimina la desigualdad, pero introduce el problema de que la función de penalización c , y por lo tanto la función objetivo f ( x ) + c ( x ) , es discontinua , lo que impide el uso del cálculo para resolverla.
Una función de barrera, ahora, es una aproximación continua g a c que tiende a infinito cuando x se aproxima a b desde arriba. Usando tal función, se formula un nuevo problema de optimización, a saber.
- minimizar f ( x ) + μ g ( x )
donde μ > 0 es un parámetro libre. Este problema no es equivalente al original, pero a medida que μ se acerca a cero, se convierte en una aproximación cada vez mejor. [3]
Función de barrera logarítmica
Para funciones de barrera logarítmicas, Se define como Cuándo y de lo contrario (en 1 dimensión. Consulte a continuación una definición en dimensiones superiores). Esto se basa esencialmente en el hecho de que tiende al infinito negativo como tiende a 0.
Esto introduce un gradiente en la función que se está optimizando que favorece valores menos extremos de (en este caso valores inferiores a ), mientras que tiene un impacto relativamente bajo en la función lejos de estos extremos.
Las funciones de barrera logarítmica pueden verse favorecidas frente a las funciones de barrera inversa menos costosas desde el punto de vista computacional , dependiendo de la función que se esté optimizando.
Mayores dimensiones
La ampliación a dimensiones superiores es sencilla, siempre que cada dimensión sea independiente. Para cada variable que debería limitarse a ser estrictamente inferior a , agregar .
Definicion formal
Minimizar sujeto a
Suponga estrictamente factible:
Definir barrera logarítmica
Ver también
Referencias
- ↑ Nesterov, Yurii (2018). Conferencias sobre optimización convexa (2 ed.). Cham, Suiza: Springer. pag. 56. ISBN 978-3-319-91577-7.
- ^ Nocedal, Jorge; Wright, Stephen (2006). Optimización numérica (2 ed.). Nueva York, NY: Springer. pag. 566. ISBN 0-387-30303-0.
- ^ Vanderbei, Robert J. (2001). Programación lineal: fundamentos y ampliaciones . Kluwer. págs. 277–279.
enlaces externos
- Conferencia 14: Método de barrera del profesor Lieven Vandenberghe de UCLA