Método de penalización

Tipo de algoritmo para optimización restringida

Los métodos de penalización son una determinada clase de algoritmos para resolver problemas de optimización restringida .

Un método de penalización reemplaza un problema de optimización restringido por una serie de problemas no restringidos cuyas soluciones idealmente convergen a la solución del problema restringido original. Los problemas sin restricciones se forman agregando a la función objetivo un término, llamado función de penalización , que consiste en un parámetro de penalización multiplicado por una medida de violación de las restricciones. La medida de violación es distinta de cero cuando se violan las restricciones y es cero en la región donde no se violan las restricciones.

Descripción

Digamos que estamos resolviendo el siguiente problema restringido:

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

sujeto a

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

Este problema se puede resolver 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, es la función de penalización exterior mientras que es el coeficiente de penalización . Cuando el coeficiente de penalización es 0, f _p = f . En cada iteración del método, aumentamos el coeficiente de penalización (por ejemplo, en un factor de 10), resolvemos el problema sin restricciones y utilizamos la solución como estimación inicial para la siguiente iteración. Las soluciones de los sucesivos problemas no restringidos convergerán asintóticamente a la solución del problema restringido original. ${\displaystyle g(c_{i}(\mathbf {x} ))}$ ${\displaystyle p}$ ${\displaystyle p}$

Convergencia

Primero consideramos el conjunto de optimizadores globales del problema original, X*. ^{[1] : Thm.9.2.1} Suponga que el objetivo f tiene conjuntos de niveles 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 está vacío.
• Para cada ε>0, existe un coeficiente de penalización p tal que el conjunto X _p * está contenido en una ε-vecindad del conjunto X*.

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

Un segundo teorema considera optimizadores locales. ^{[1] : 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 optimización suficiente de segundo orden). Entonces, existe una vecindad 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 acerca a x* cuando p →∞. Además, el valor objetivo f (x*( p )) aumenta débilmente con p .

Aplicaciones prácticas

Los algoritmos de optimización de la compresión de imágenes pueden utilizar funciones de penalización para seleccionar la mejor manera de comprimir zonas de color en valores representativos únicos. ^{[2] [3]}

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

Ver también

Los métodos de barrera constituyen una clase alternativa de algoritmos para la optimización restringida. Estos métodos también agregan un término similar a una penalización a la función objetivo, pero en este caso los iterados se ven obligados a permanecer dentro del dominio factible y la barrera está colocada para sesgar los iterados para que permanezcan alejados del límite de la región factible. Son prácticamente más eficaces que los métodos de penalización.

Los métodos lagrangianos aumentados son métodos de penalización alternativos que permiten obtener soluciones de alta precisión sin llevar el coeficiente de penalización al infinito. Esto hace que los problemas penalizados sin restricciones sean más fáciles de resolver.

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

Referencias

1. Nemirovsky y Ben-Tal (2023). "Optimización III: Optimización convexa" (PDF) .
2. Galar, M.; Jurio, A.; López-Molina, C.; Paternin, D.; Sanz, J.; Bustince, H. (2013). "Funciones de agregación para combinar canales de color RGB en coincidencia estéreo". Óptica Express . 21 (1): 1247–1257. doi :10.1364/oe.21.001247. hdl : 2454/21074 . PMID  23389018.
3. "Los investigadores restauran la imagen utilizando una versión que contiene entre el 1 y el 10 por ciento de la información". Phys.org (Omicron Technology Limited) . Consultado el 26 de octubre de 2013 .

Smith, Alice E .; Coit David W. Funciones de penalización Manual de Computación Evolutiva, Sección C 5.2. Oxford University Press e Instituto de Publicaciones de Física, 1996.

Coello, AC[1]: Técnicas teóricas y numéricas de manejo de restricciones utilizadas con algoritmos evolutivos: un estudio del estado del arte. Computadora. Métodos de aplicación. Mec. Ing. 191(11-12), 1245-1287

Courant, R. Métodos variacionales para la solución de problemas de equilibrio y vibraciones. Toro. América. Matemáticas. Soc., 49, 1-23, 1943.

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