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 gradual es una mejora en la escalada que permite al escalador 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 es convexo (o casi convexo), la solución a cada problema proporciona un buen punto de partida para el siguiente problema de la secuencia. y el último problema de la secuencia es el difícil problema de optimización que finalmente busca resolver. A menudo, la optimización gradual da mejores resultados que la simple subida de pendientes. Además, cuando existen ciertas condiciones, se puede demostrar que se encuentra una solución óptima al problema final de la secuencia. Estas condiciones son:
Se puede demostrar inductivamente que si se cumplen estas condiciones, un escalador llegará al óptimo global para el difícil problema. Desafortunadamente, puede resultar difícil encontrar una secuencia de problemas de optimización que cumplan estas condiciones. A menudo, la optimización gradual produce buenos resultados incluso cuando no se puede demostrar que la secuencia de problemas cumpla estrictamente 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 desenfocando las imágenes. Por lo tanto, los objetos se pueden encontrar buscando primero en 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 localice 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. [5]
La optimización graduada se puede utilizar en múltiples aprendizajes. El algoritmo Manifold Sculpting, por ejemplo, utiliza optimización graduada para buscar una incrustación múltiple para una reducción de dimensionalidad no lineal . [6] Reduce gradualmente la variación de 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 de tumores, [7] para el seguimiento de objetos en visión por computadora, [8] y otros fines.
Se puede encontrar una revisión exhaustiva del método y sus aplicaciones en [3] .
El recocido simulado está estrechamente relacionado con la optimización gradual. En lugar de suavizar la función 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 necesaria ] Sin embargo, debido a que el recocido simulado se basa en un muestreo aleatorio para encontrar mejoras, su complejidad de cálculo es exponencial en la cantidad de dimensiones que se optimizan. [ cita necesaria ] Por el contrario, la optimización graduada suaviza la función que se optimiza, por lo que aún se pueden utilizar técnicas de optimización local que son eficientes en espacios de alta dimensión (como técnicas basadas en gradientes, escaladores de colinas, etc.).