Optimización graduada - Graduated optimization
La optimización graduada es una técnica de optimización global que intenta resolver un problema de optimización difícil resolviendo inicialmente un problema muy simplificado y transformando progresivamente ese problema (mientras se optimiza) hasta que sea equivalente al problema de optimización difícil.
Descripción técnica
La optimización gradual es una mejora de la escalada que permite al escalador evitar asentarse en los óptimos locales. Divide un problema de optimización difícil en una secuencia de problemas de optimización, de modo que el primer problema de la secuencia es convexo (o casi convexo), la solución de cada problema da un buen punto de partida para el siguiente problema de la secuencia y el último El problema de la secuencia es el difícil problema de optimización que, en última instancia, busca resolver. A menudo, la optimización graduada da mejores resultados que la simple escalada. Además, cuando existen ciertas condiciones, se puede demostrar que encuentra una solución óptima al problema final en la secuencia. Estas condiciones son:
- El primer problema de optimización de la secuencia puede resolverse dado el punto de partida inicial.
- La región localmente convexa alrededor del óptimo global de cada problema en la secuencia incluye el punto que corresponde al óptimo global del problema anterior en la secuencia.
Se puede demostrar inductivamente que si se cumplen estas condiciones, entonces un alpinista llegará al óptimo global para el problema difícil. Desafortunadamente, puede ser difícil encontrar una secuencia de problemas de optimización que cumpla con estas condiciones. A menudo, la optimización graduada produce buenos resultados incluso cuando no se puede probar que la secuencia de problemas cumpla estrictamente con todas estas condiciones.
Algunos ejemplos
La optimización graduada se usa comúnmente en el procesamiento de imágenes para ubicar objetos dentro de una imagen más grande. Se puede hacer que este problema sea más convexo desenfocando las imágenes. Por lo tanto, los objetos se pueden encontrar buscando primero la imagen más borrosa, luego comenzando en ese punto y buscando dentro de una imagen menos borrosa, y continuando de esta manera hasta que el objeto se ubique con precisión en la imagen nítida original. La elección adecuada del operador de desenfoque depende de la transformación geométrica que relaciona el objeto de una imagen con la otra.
La optimización graduada se puede utilizar en el aprendizaje múltiple. El algoritmo Manifold Sculpting, por ejemplo, utiliza optimización graduada para buscar una inserción múltiple para la reducción de dimensionalidad no lineal. Escala gradualmente la varianza de las dimensiones adicionales dentro de un conjunto de datos mientras optimiza las dimensiones restantes. También se ha utilizado para calcular las condiciones para el fraccionamiento con tumores, para el seguimiento de objetos en visión por computadora y otros fines.
Se puede encontrar una revisión completa del método y sus aplicaciones en.
Técnicas de optimización relacionadas
El recocido simulado está estrechamente relacionado con la optimización graduada. En lugar de suavizar la función sobre la que está optimizando, el recocido simulado perturba aleatoriamente la solución actual en una cantidad decreciente, lo que puede tener un efecto similar. Sin embargo, debido a que el recocido simulado se basa en el muestreo aleatorio para encontrar mejoras, su complejidad de cálculo es exponencial en el número de dimensiones que se optimizan. Por el contrario, la optimización graduada suaviza la función que se optimiza, por lo que las técnicas de optimización local que son eficientes en espacios de gran dimensión (como técnicas basadas en gradientes, escaladores de colinas, etc.) aún pueden usarse.