Benchmarking Optimization Algorithms with Quality Profiles and Test Set Profiles

Resumen Técnico: Evaluación de Algoritmos de Optimización mediante Perfiles de Calidad y Perfiles de Conjunto de Prueba

Planteamiento del Problema
La evaluación comparativa (benchmarking) de algoritmos de optimización presenta un desafío significativo, particularmente cuando se comparan solucionadores que pueden converger a diferentes puntos de solución en un conjunto de prueba. Las herramientas de evaluación existentes, como los perfiles de rendimiento (Dolan y Moré) y los perfiles de datos (Moré y Wild), se centran principalmente en la eficiencia (esfuerzo computacional) y la fiabilidad (tasas de éxito). Si bien los perfiles de rendimiento son el estándar para medir el esfuerzo de convergencia (por ejemplo, tiempo de CPU, iteraciones), a menudo excluyen problemas donde los solucionadores convergen a soluciones distintas para asegurar una comparación justa de la carga computacional. En consecuencia, existe una falta de herramientas diseñadas específicamente para evaluar y comparar la calidad (exactitud) de los valores de la función objetivo finales obtenidos por diferentes solucionadores, especialmente en escenarios donde se comparan métodos exactos con heurísticos, o donde los solucionadores convergen a mínimos locales distintos. Además, la literatura ha prestado poca atención a la evaluación cuantitativa de la idoneidad y consistencia del propio conjunto de prueba con respecto a los solucionadores que se evalúan.

Metodología
Los autores proponen dos herramientas gráficas novedosas: Perfiles de Calidad y Perfiles de Conjunto de Prueba.

1. Perfiles de Calidad:

   • Definición: Para un conjunto de solucionadores $S$ y problemas de prueba $P$, un perfil de calidad $Q_s(\tau)$ representa la proporción de problemas donde un solucionador $s$ logra una solución dentro de un umbral de exactitud específico $\tau$. La exactitud se mide con respecto a un valor de referencia $f_L^{(p)}$ (típicamente la mejor solución encontrada por cualquier solucionador en el conjunto) y un punto inicial $x_0^{(p)}$.
   • Inecuación Central: El perfil se construye basado en la inecuación:
     $$f_s^{(p)}(x^*) - f_L^{(p)} \leq \tau [f^{(p)}(x_0^{(p)}) - f_L^{(p)}]$$
     donde $\tau \in [0, 1]$.
   • Débil vs. Fuerte: Los perfiles "débiles" utilizan el punto inicial $x_0^{(p)}$ en la normalización, mientras que los "fuertes" utilizan la peor solución encontrada por los solucionadores.
   • Mejoras de Visualización: Para abordar la dificultad de distinguir trayectorias densamente agrupadas, los autores introducen parámetros de escala $r_1$ y $r_2$. Estos permiten la compresión o expansión no lineal de los ejes de la abscisa (precisión) y la ordenada (porcentaje de problemas), respectivamente. Esto facilita el acercamiento (zooming) a rangos de exactitud específicos (por ejemplo, alta precisión cerca de $\tau=0$) sin descartar datos.
   • Propiedades: Se demuestra que los perfiles son invariantes ante transformaciones afines consistentes de la función objetivo y son no decrecientes. A diferencia de los perfiles de rendimiento, no requieren la identificación a priori de parámetros que pudiera introducir sesgos, aunque dependen de un presupuesto computacional fijo (criterio de parada) por cada solucionador.

2. Perfiles de Conjunto de Prueba:

   • Propósito: Evaluar la robustez de las conclusiones de la evaluación comparativa y la consistencia del conjunto de prueba $P$.
   • Metodología: Esta herramienta aplica una técnica de bootstrapping. Se vuelven a muestrear repetidamente los subconjuntos del conjunto de prueba $P$ (con reemplazo) para generar múltiples subconjuntos $\hat{P}$. Se calculan perfiles de calidad para cada subconjunto.
   • Resultado: La varianza $\sigma_s^2(\tau)$ de los valores del perfil de calidad a través de los ciclos de bootstrap se grafica contra $\tau$. Una varianza baja indica que el ranking y el rendimiento del solucionador son robustos ante cambios en la composición del conjunto de prueba, mientras que una varianza alta sugiere que las conclusiones de la evaluación son sensibles a la elección específica de los problemas.

Contribuciones Clave

• Herramienta de Evaluación Novedosa: La introducción de los Perfiles de Calidad proporciona un procedimiento determinista para comparar solucionadores basados en la exactitud de la solución en lugar del esfuerzo computacional. Esto permite la inclusión de problemas donde los solucionadores convergen a soluciones diferentes, los cuales suelen excluirse en las comparaciones de perfiles de rendimiento.
• Naturaleza Complementaria: Los autores posicionan a los Perfiles de Calidad no como un reemplazo de los perfiles de rendimiento o de datos, sino como una herramienta complementaria. Llenan un vacío en la literatura al ofrecer una representación gráfica condensada de la calidad de la solución, la cual es particularmente útil al comparar métodos exactos con heurísticos.
• Diagnóstico del Conjunto de Prueba: La introducción de los Perfiles de Conjunto de Prueba ofrece un método cuantitativo post-hoc para evaluar la fiabilidad y el poder discriminatorio de un conjunto de prueba, abordando una dimensión de la evaluación frecuentemente pasada por alto.
• Flexibilidad en la Visualización: El uso de parámetros de escala ($r_1, r_2$) y escalas semilogarítmicas permite un análisis detallado del rendimiento del solucionador a través de diferentes órdenes de magnitud en la exactitud, una característica que no es fácilmente extensible a los perfiles de rendimiento o de datos estándar.

Resultados
El artículo presenta extensos experimentos numéricos para validar las herramientas:

• Optimización Suave:
  • En una comparación de cuatro solucionadores de gran escala sin restricciones (L-BFGS, CG+, TRON, CG DESCENT) sobre 166 problemas de CUTEst, los Perfiles de Calidad revelaron que TRON superó a los demás en intervalos de baja a media exactitud, mientras que CG+ mostró una robustez ligeramente superior (menos fallos). Se demostró que los parámetros de escala ($r_1 > 1$) son esenciales para distinguir los solucionadores en regiones de alta exactitud donde las trayectorias serían de otro modo indistinguibles.
  • Un segundo experimento comparó métodos de Newton Truncado con diferentes estrategias de dirección de curvatura negativa. Los Perfiles de Calidad resaltaron eficazmente que la estrategia TN-NC3 (selección de la primera autovalor negativa) era la más efectiva, confirmando las expectativas teóricas y demostrando la capacidad de la herramienta para medir características algorítmicas específicas.
• Optimización Libre de Derivadas:
  • Los autores aplicaron Perfiles de Calidad a siete solucionadores libres de derivadas (incluyendo NEWUOA, Nelder-Mead y métodos de búsqueda de patrones) sobre 145 problemas.
  • Los resultados demostraron la complementariedad con los Perfiles de Datos: mientras que los Perfiles de Datos muestran el rendimiento frente al presupuesto computacional para una exactitud fija, los Perfiles de Calidad muestran el rendimiento frente a la exactitud para presupuestos computacionales fijos.
  • Los experimentos confirmaron que los métodos basados en modelos (NEWUA) generalmente producen una mayor exactitud que los métodos de búsqueda de patrones, incluso con presupuestos modestos, y que los parámetros de escala son cruciales para visualizar estas diferencias.
• Análisis del Conjunto de Prueba:
  • Utilizando datos sintéticos y variando la cardinalidad del conjunto de prueba ($|P|$), los Perfiles de Conjunto de Prueba mostraron que los conjuntos de prueba más pequeños conducen a una mayor varianza en los rankings de los solucionadores, confirmando la sensibilidad de la evaluación a la composición del conjunto de prueba.

Significancia y Reivindicaciones
Los autores sostienen que los Perfiles de Calidad y los Perfiles de Conjunto de Prueba mejoran el proceso de evaluación comparativa al proporcionar una imagen más completa del comportamiento de los solucionadores. Específicamente:

• Permiten la comparación de algoritmos que convergen a soluciones distintas, un escenario donde los perfiles de rendimiento tradicionales suelen ser inadecuados o requieren la exclusión de datos.
• Ofrecen una forma de evaluar la "otra cara" de la robustez del solucionador: la idoneidad del propio conjunto de prueba.
• El enfoque es constructivo en lugar de axiomático; no pretende resolver todas las paradojas de clasificación (como las discutidas por Liu et al.), sino que proporciona una herramienta práctica basada en datos para medir una dimensión específica del rendimiento (calidad de la solución).
• Las herramientas son particularmente valiosas en la optimización libre de derivadas y de caja negra, donde los presupuestos fijos de evaluaciones de función son comunes y la calidad de la solución es la métrica de interés principal.

El artículo concluye que estas herramientas deben verse como parte de un ecosistema de evaluación más amplio, que complementa el análisis de espacio de instancias, el diseño experimental sólido y las reglas de comparación libres de paradojas, en lugar de reemplazar las metodologías existentes.