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. [1] [2] [3]
La optimización graduada es una mejora de la escalada de colinas que permite a quien la practica evitar establecerse en óptimos locales. [4] 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 sea convexo (o casi convexo), la solución de cada problema proporcione un buen punto de partida para el siguiente problema de la secuencia y el último problema de la secuencia sea el problema de optimización difícil que finalmente se busca resolver. A menudo, la optimización graduada da mejores resultados que la simple escalada de colinas. Además, cuando se dan ciertas condiciones, se puede demostrar que encuentra una solución óptima para el problema final de la secuencia. Estas condiciones son:
Se puede demostrar de manera inductiva que, si se cumplen estas condiciones, el escalador de colinas llegará al óptimo global para el problema difícil. Desafortunadamente, puede resultar difícil encontrar una secuencia de problemas de optimización que cumpla con estas condiciones. A menudo, la optimización gradual produce buenos resultados incluso cuando no se puede demostrar que la secuencia de problemas cumpla estrictamente con todas estas condiciones.
La optimización graduada se utiliza habitualmente en el procesamiento de imágenes para localizar objetos dentro de una imagen más grande. Este problema se puede hacer más convexo difuminando las imágenes. De este modo, se pueden encontrar objetos buscando primero la imagen más borrosa, comenzando luego por ese punto y buscando dentro de una imagen menos borrosa, y continuando de esta manera hasta que el objeto se encuentre 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 en una imagen con la otra. [5]
La optimización graduada se puede utilizar en el aprendizaje de variedades. El algoritmo Manifold Sculpting, por ejemplo, utiliza la optimización graduada para buscar una incrustación de variedades para la reducción de dimensionalidad no lineal . [6] Escala gradualmente la varianza de las dimensiones adicionales dentro de un conjunto de datos mientras optimiza en las dimensiones restantes. También se ha utilizado para calcular las condiciones para el fraccionamiento con tumores, [7] para el seguimiento de objetos en visión artificial, [8] y otros fines.
Una revisión exhaustiva del método y sus aplicaciones se puede encontrar en [3] .
El recocido simulado está estrechamente relacionado con la optimización graduada. En lugar de suavizar la función sobre la que se está optimizando, el recocido simulado perturba aleatoriamente la solución actual en una cantidad decreciente, lo que puede tener un efecto similar. [ cita requerida ] Sin embargo, debido a que el recocido simulado se basa en un muestreo aleatorio para encontrar mejoras, su complejidad computacional es exponencial en el número de dimensiones que se están optimizando. [ cita requerida ] Por el contrario, la optimización graduada suaviza la función que se está optimizando, por lo que aún se pueden usar técnicas de optimización local que son eficientes en un espacio de alta dimensión (como técnicas basadas en gradientes, escaladores de colinas, etc.).