Función de barrera

En optimización restringida , un campo de las matemáticas , una función de barrera es una función continua cuyo valor aumenta hasta el infinito a medida que su argumento 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 penalizador en la función objetivo que sea más fácil de manejar. Una función de barrera también se llama función de penalización interior , ya que es una función de penalización que obliga a la solución a permanecer dentro de la región factible.

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 por las funciones de barrera logarítmicas fue motivada por su conexión con los métodos de puntos interiores duales primarios .

Motivación

Considere el siguiente problema de optimización restringida:

minimizar f ( x )

sujeto a x ≤ b

donde b es alguna constante. Si se desea eliminar la restricción de desigualdad, el problema se puede reformular 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 de g a c que tiende al infinito cuando x se aproxima a b desde arriba. Utilizando dicha 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 aproxima 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 otra manera (en una dimensión; consulte a continuación una definición en dimensiones superiores). Esto esencialmente se basa en el hecho de que tiende a infinito negativo cuando tiende a 0. ${\displaystyle g(x,b)}$ ${\displaystyle -\log(b-x)}$ ${\displaystyle x<b}$ ${\displaystyle \infty }$ ${\displaystyle \log t}$ ${\displaystyle t}$

Esto introduce un gradiente en la función que se está optimizando que favorece valores menos extremos de (en este caso, valores inferiores a ), al tiempo que tiene un impacto relativamente bajo en la función alejada de estos extremos. ${\displaystyle x}$ ${\displaystyle b}$

Las funciones de barrera logarítmicas pueden preferirse a las funciones de barrera inversas menos costosas desde el punto de vista computacional, dependiendo de la función que se optimice.

Dimensiones superiores

Extenderlo a dimensiones superiores es sencillo, siempre que cada dimensión sea independiente. Para cada variable que deba limitarse a ser estrictamente inferior a , agregue . ${\displaystyle x_{i}}$ ${\displaystyle b_{i}}$ ${\displaystyle -\log(b_{i}-x_{i})}$

Definicion formal

Minimizar sujeto a ${\displaystyle \mathbf {c} ^{T}x}$ ${\displaystyle \mathbf {a} _{i}^{T}x\leq b_{i},i=1,\ldots ,m}$

Supongamos estrictamente factible: ${\displaystyle \{\mathbf {x} |Ax<b\}\neq \emptyset }$

Definir barrera logarítmica ${\displaystyle g(x)={\begin{cases}\sum _{i=1}^{m}-\log(b_{i}-a_{i}^{T}x)&{\text{for }}Ax<b\\+\infty &{\text{otherwise}}\end{cases}}}$

Ver también

• Método de penalización
• Método lagrangiano aumentado

Referencias

1. Nesterov, Yurii (2018). Conferencias sobre optimización convexa (2 ed.). Cham, Suiza: Springer. pag. 56.ISBN​ 978-3-319-91577-7.
2. Nocedal, Jorge; Wright, Stephen (2006). Optimización numérica (2 ed.). Nueva York, Nueva York: Springer. pag. 566.ISBN​ 0-387-30303-0.
3. Vanderbei, Robert J. (2001). Programación lineal: fundamentos y extensiones . Kluwer. págs. 277-279.

enlaces externos

• Conferencia 14: Método de barrera del profesor Lieven Vandenberghe de UCLA