Descenso de coordenadas adaptativo

El descenso de coordenadas adaptativo ^{[ 1 ]} es una mejora del algoritmo de descenso de coordenadas para la optimización no separable mediante el uso de codificación adaptativa . ^{[ 2 ]} El enfoque de descenso de coordenadas adaptativo construye gradualmente una transformación del sistema de coordenadas de tal manera que las nuevas coordenadas estén lo más descorrelacionadas posible con respecto a la función objetivo. Se ha demostrado que el descenso de coordenadas adaptativo es competitivo con los algoritmos evolutivos de última generación y posee las siguientes propiedades de invariancia:

1. Invariancia con respecto a transformaciones monótonas de la función (escalamiento)
2. Invariancia con respecto a transformaciones ortogonales del espacio de búsqueda (rotación).

La actualización de codificación adaptativa tipo CMA (b), basada principalmente en el análisis de componentes principales (a), se utiliza para extender el método de descenso de coordenadas (c) a la optimización de problemas no separables (d).

La adaptación de un sistema de coordenadas apropiado permite que el descenso de coordenadas adaptativo supere al descenso de coordenadas en funciones no separables. La siguiente figura ilustra la convergencia de ambos algoritmos en la función de Rosenbrock bidimensional hasta un valor de función objetivo.${\displaystyle 10^{-10}}$, partiendo del punto inicial${\displaystyle x_{0}=(-3,-4)}$.

El método de descenso de coordenadas adaptativo alcanza el valor objetivo tras solo 325 evaluaciones de la función (aproximadamente 70 veces más rápido que el descenso de coordenadas convencional), lo que resulta comparable a los métodos basados ​​en gradientes . El algoritmo presenta una complejidad temporal lineal si se actualiza el sistema de coordenadas cada D iteraciones, y también es adecuado para la optimización no lineal a gran escala (D>>100).

Los primeros enfoques para la optimización utilizando un sistema de coordenadas adaptativo se propusieron ya en la década de 1960 (véase, por ejemplo, el método de Rosenbrock ). El algoritmo de Ejes Principales (PRAXIS), también conocido como algoritmo de Brent, es un algoritmo sin derivadas que asume una forma cuadrática de la función optimizada y actualiza repetidamente un conjunto de direcciones de búsqueda conjugadas. ^{[ 3 ]} Sin embargo, el algoritmo no es invariante a la escala de la función objetivo y puede fallar bajo ciertas transformaciones que preservan el rango (por ejemplo, conducirá a una forma no cuadrática de la función objetivo). Un análisis reciente de PRAXIS se puede encontrar en ^{[ 4 ]} . Para aplicaciones prácticas, véase ^{[ 5 ]} donde se propuso un enfoque de descenso de coordenadas adaptativo con adaptación del tamaño del paso y rotación del sistema de coordenadas local para la planificación de trayectorias de robots-manipuladores en el espacio 3D con obstáculos poligonales estáticos.

• Descenso de coordenadas
• CMA-ES
• Métodos de Rosenbrock
• Optimización matemática

• CÓDIGO FUENTE ACD ACD es un código fuente de MATLAB para el Descenso Adaptativo de Coordenadas.