Función de barrera

Función continua cuyo valor aumenta hasta el infinito

En la optimización restringida , un campo de las matemáticas , una función 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 es más fácil de manejar. Una función barrera también se denomina función de penalización interior , ya que es una función de penalización que obliga a la solución a permanecer dentro del interior 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. El interés por las funciones de barrera logarítmicas se reavivó a raíz de su conexión con los métodos de punto interior primal-dual .

Motivación

Consideremos el siguiente problema de optimización restringida:

minimizar f ( x )

sujeto a x ≤ b

donde b es una 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 es, ahora, una aproximación continua de g a c que tiende al infinito a medida que x se acerca a b desde arriba. Utilizando una función de este tipo, 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 las funciones de barrera logarítmicas, se define como cuando y en caso contrario (en una dimensión; consulte a continuación una definición en dimensiones superiores). Esto se basa esencialmente 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 los 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. ${\displaystyle x}$ ${\displaystyle b}$

Las funciones de barrera logarítmicas pueden preferirse a las funciones de barrera inversas, que son computacionalmente menos costosas, dependiendo de la función que se esté optimizando.

Dimensiones superiores

La ampliación a dimensiones superiores es sencilla, siempre que cada dimensión sea independiente. Para cada variable que deba limitarse a un valor estrictamente inferior a , se añade . ${\displaystyle x_{i}}$ ${\displaystyle b_{i}}$ ${\displaystyle -\log(b_{i}-x_{i})}$

Definición 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}}}$

Véase también

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

Referencias

1. Nesterov, Yurii (2018). Lecciones sobre optimización convexa (2.ª ed.). Cham, Suiza: Springer. p. 56. ISBN 978-3-319-91577-7.
2. Nocedal, Jorge; Wright, Stephen (2006). Optimización numérica (2.ª ed.). Nueva York, NY: Springer. p. 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