Método de penalización

En optimización matemática , los métodos de penalización son una clase específica de algoritmos para resolver problemas de optimización con restricciones .

El método de penalización sustituye un problema de optimización con restricciones por una serie de problemas sin restricciones cuyas soluciones convergen idealmente a la solución del problema original con restricciones. Estos problemas sin restricciones se forman añadiendo un término, denominado función de penalización , a la función objetivo . Este término consiste en un parámetro de penalización multiplicado por una medida de la violación de las restricciones. La medida de la violación es distinta de cero cuando se violan las restricciones y es cero en la región donde no se violan.

Digamos que estamos resolviendo el siguiente problema con restricciones:

${\displaystyle \min _ {x}f(\mathbf {x} )}$

sujeto a

${\displaystyle c_{i}(\mathbf {x} )\leq 0~\forall i\in I.}$

Este problema puede resolverse como una serie de problemas de minimización sin restricciones.

${\displaystyle \min f_{p}(\mathbf {x} ):=f(\mathbf {x} )+p~\sum _{i\in I}~g(c_{i}(\mathbf {x} ))}$

dónde

${\displaystyle g(c_{i}(\mathbf {x} ))=\max(0,c_{i}(\mathbf {x} ))^{2}.}$

En las ecuaciones anteriores,${\displaystyle g(c_{i}(\mathbf {x} ))}$es la función de penalización exterior mientras${\displaystyle p}$es el coeficiente de penalización . Cuando el coeficiente de penalización${\displaystyle p}$es 0, f _p = f , lo que significa que no tomamos en cuenta las restricciones.

En cada iteración del método, aumentamos el coeficiente de penalización.${\displaystyle p}$(p. ej., por un factor de 10), resuelva el problema sin restricciones y utilice la solución como estimación inicial para la siguiente iteración. Las soluciones de los problemas sucesivos sin restricciones convergerán asintóticamente a la solución del problema original con restricciones.

Las funciones de penalización comunes en la optimización con restricciones son la función de penalización cuadrática y la función de penalización lineal de zona muerta . ^{[ 1 ]}

Primero consideramos el conjunto de optimizadores globales del problema original, X*. ^{[ 2 ] : Teorema 9.2.1} Supongamos que la función objetivo f tiene conjuntos de nivel acotados y que el problema original es factible. Entonces:

• Para cada coeficiente de penalización p , el conjunto de optimizadores globales del problema penalizado, X _p *, no es vacío.
• Para cada ε>0, existe un coeficiente de penalización p tal que el conjunto X _p * está contenido en un entorno ε del conjunto X*.

Este teorema es útil principalmente cuando f _p es convexa, ya que en este caso podemos encontrar los optimizadores globales de f _p .

Un segundo teorema considera optimizadores locales. ^{[ 2 ] : Thm.9.2.2} Sea x* un optimizador local no degenerado del problema original ("no degenerado" significa que los gradientes de las restricciones activas son linealmente independientes y se satisface la condición de optimalidad suficiente de segundo orden). Entonces, existe un entorno V* de x*, y algún p ₀ >0, tal que para todo p > p ₀ , el objetivo penalizado f _p tiene exactamente un punto crítico en V* (denotado por x*(p)), y x*( p ) se aproxima a x* cuando p →∞. Además, el valor del objetivo f (x*( p )) es débilmente creciente con p .

Los algoritmos de optimización de compresión de imágenes pueden utilizar funciones de penalización para seleccionar la mejor manera de comprimir zonas de color a valores representativos únicos. ^{[ 3 ] [ 4 ]} El método de penalización se utiliza a menudo en mecánica computacional, especialmente en el método de elementos finitos , para imponer condiciones como por ejemplo el contacto .

La ventaja del método de penalización es que, una vez que tenemos un objetivo penalizado sin restricciones, podemos usar cualquier método de optimización sin restricciones para resolverlo. La desventaja es que, a medida que el coeficiente de penalización p aumenta, el problema sin restricciones se vuelve mal condicionado : los coeficientes son muy grandes, lo que puede causar errores numéricos y una convergencia lenta de la minimización sin restricciones. ^{[ 2 ] : Sub.9.2}

Los métodos de barrera constituyen una clase alternativa de algoritmos para la optimización con restricciones. Estos métodos también añaden un término de penalización a la función objetivo, pero en este caso las iteraciones se ven obligadas a permanecer dentro del dominio factible y la barrera se utiliza para sesgar las iteraciones y alejarlas del límite de la región factible. En la práctica, son más eficientes que los métodos de penalización.

Los métodos de Lagrangiano aumentado son métodos de penalización alternativos que permiten obtener soluciones de alta precisión sin que el coeficiente de penalización tienda al infinito. Esto facilita la resolución de problemas penalizados sin restricciones.

Otros algoritmos de programación no lineal:

• Programación cuadrática secuencial
• Programación lineal sucesiva
• Programación lineal-cuadrática secuencial
• Método del punto interior

Smith, Alice E .; Coit, David W. Funciones de penalización. Manual de computación evolutiva, Sección C 5.2. Oxford University Press e Institute of Physics Publishing, 1996.

Coello, ACTécnicas teóricas y numéricas para el manejo de restricciones utilizadas con algoritmos evolutivos: una revisión del estado del arte. Comput. Methods Appl. Mech. Engrg. 191(11-12), 1245-1287

Courant, R. Métodos variacionales para la solución de problemas de equilibrio y vibraciones . Bull. Amer. Math. Soc., 49, 1 – 23, 1943.

Wotao, Y. Algoritmos de optimización para optimización con restricciones . Departamento de Matemáticas, UCLA, 2015.