Benchmarking Optimization Algorithms with Quality Profiles and Test Set Profiles

Résumé Technique : Évaluation des algorithmes d'optimisation par les profils de qualité et les profils d'ensemble de tests

Énoncé du Problème
L'évaluation comparative des algorithmes d'optimisation présente un défi significatif, particulièrement lorsqu'il s'agit de comparer des solveurs qui peuvent converger vers différents points de solution sur un ensemble de tests. Les outils d'évaluation existants, tels que les profils de performance (Dolan et Moré) et les profils de données (Moré et Wild), se concentrent principalement sur l'efficacité (effort de calcul) et la fiabilité (taux de succès). Bien que les profils de performance soient la norme pour mesurer l'effort de convergence (ex. : temps CPU, itérations), ils excluent souvent les problèmes où les solveurs convergent vers des solutions différentes afin de garantir une comparaison équitable de la charge de calcul. Par conséquent, il existe un manque d'outils spécifiquement conçus pour évaluer et comparer la qualité (précision) des valeurs de la fonction objectif finales obtenues par différents solveurs, notamment dans les scénarios où des méthodes exactes et des heuristiques sont comparées, ou lorsque les solveurs convergent vers des minima locaux distincts. De plus, la littérature a accordé une attention limitée à l'évaluation quantitative de la pertinence et de la cohérence de l'ensemble de tests lui-même par rapport aux solveurs faisant l'objet de l'évaluation.

Méthodologie
Les auteurs proposent deux nouveaux outils graphiques : les Profils de Qualité et les Profils d'Ensemble de Tests.

1. Profils de Qualité :

   • Définition : Pour un ensemble de solveurs $S$ et de problèmes de test $P$, un profil de qualité $Q_s(\tau)$ représente la proportion de problèmes où un solveur $s$ atteint une solution dans un seuil de précision spécifique $\tau$. La précision est mesurée par rapport à une valeur de référence $f_L^{(p)}$ (typiquement la meilleure solution trouvée par n'importe quel solveur de l'ensemble) et un point initial $x_0^{(p)}$.
   • Inégalité Fondamentale : Le profil est construit sur la base de l'inégalité :
     $$f_s^{(p)}(x^*) - f_L^{(p)} \leq \tau [f^{(p)}(x_0^{(p)}) - f_L^{(p)}]$$
     où $\tau \in [0, 1]$.
   • Faible vs Fort : Les profils « faibles » utilisent le point initial $x_0^{(p)}$ pour la normalisation, tandis que les profils « forts » utilisent la pire solution trouvée par les solveurs.
   • Améliorations de la Visualisation : Pour remédier à la difficulté de distinguer des trajectoires étroitement regroupées, les auteurs introduisent des paramètres d'échelle $r_1$ et $r_2$. Ceux-ci permettent la compression ou l'expansion non linéaire de l'abscisse (précision) et de l'ordonnée (pourcentage de problèmes), respectivement. Cela facilite le zoom sur des plages de précision spécifiques (ex. : haute précision près de $\tau=0$) sans rejeter de données.
   • Propriétés : Les profils sont prouvés invariants sous des transformations affines cohérentes de la fonction objectif et sont non décroissants. Contrairement aux profils de performance, ils ne nécessitent pas d'identification de paramètres a priori qui pourrait introduire un biais, bien qu'ils reposent sur un budget de calcul fixe (critère d'arrêt) par solveur.

2. Profils d'Ensemble de Tests :

   • Objectif : Évaluer la robustesse des conclusions de l'évaluation et la cohérence de l'ensemble de tests $P$.
   • Méthodologie : Cet outil applique une technique de bootstrapping. Il rééchantillonne de manière répétée l'ensemble de tests $P$ (avec remplacement) pour générer plusieurs sous-ensembles $\hat{P}$. Des profils de qualité sont calculés pour chaque sous-ensemble.
   • Résultat : La variance $\sigma_s^2(\tau)$ des valeurs du profil de qualité à travers les cycles de bootstrap est tracée en fonction de $\tau$. Une faible variance indique que le classement du solveur et sa performance sont robustes aux changements de composition de l'ensemble de tests, tandis qu'une variance élevée suggère que les conclusions de l'évaluation sont sensibles au choix spécifique des problèmes.

Contributions Clés

• Nouvel Outil d'Évaluation : L'introduction des Profils de Qualité fournit une procédure déterministe pour comparer les solveurs basés sur la précision de la solution plutôt que sur l'effort de calcul. Cela permet d'inclure les problèmes où les solveurs convergent vers des solutions différentes, qui sont typiquement exclus des comparaisons de profils de performance.
• Nature Complémentaire : Les auteurs positionnent les Profils de Qualité non pas comme un remplacement des profils de performance ou de données, mais comme un outil complémentaire. Ils comblent une lacune dans la littérature en offrant une représentation graphique condensée de la qualité de la solution, particulièrement utile lors de la comparaison de méthodes exactes avec des heuristiques.
• Diagnostic de l'Ensemble de Tests : L'introduction des Profils d'Ensemble de Tests offre une méthode quantitative post-hoc pour évaluer la fiabilité et le pouvoir discriminatoire d'un ensemble de tests, abordant une dimension de l'évaluation souvent négligée.
• Flexibilité de Visualisation : L'utilisation de paramètres d'échelle ($r_1, r_2$) et d'échelles logarithmiques permet une analyse détaillée de la performance des solveurs à travers différents ordres de grandeur de précision, une caractéristique difficilement extensible aux profils de performance ou de données standards.

Résultats
L'article présente des expériences numériques étendues pour valider les outils :

• Optimisation Lisse :
  • Dans une comparaison de quatre solveurs à grande échelle non contraints (L-BFGS, CG+, TRON, CG DESCENT) sur 166 problèmes CUTEst, les Profils de Qualité ont révélé que TRON surpasse les autres dans les intervalles de précision faible à moyenne, tandis que CG+ a montré une robustesse légèrement supérieure (moins d'échecs). Les paramètres d'échelle ($r_1 > 1$) se sont avérés essentiels pour distinguer les solveurs dans les régions de haute précision où les trajectoires étaient autrement indiscernables.
  • Une seconde expérience a comparé des méthodes de Newton tronqué avec différentes stratégies de direction de courbure négative. Les Profils de Qualité ont efficacement mis en évidence que la stratégie TN-NC3 (sélectionnant la première valeur propre négative) était la plus efficace, confirmant les attentes théoriques et démontant la capacité de l'outil à évaluer des caractéristiques algorithmiques spécifiques.
• Optimisation Sans Dérivées :
  • Les auteurs ont appliqué les Profils de Qualité à sept solveurs sans dérivées (incluant NEWUOA, Nelder-Mead et des méthodes de recherche de motifs) sur 145 problèmes.
  • Les résultats ont démontré la complémentarité avec les Profils de Données : alors que les Profils de Données montrent la performance vs le budget de calcul pour une précision fixe, les Profils de Qualité montrent la performance vs la précision pour des budgets de calcul fixes.
  • Les expériences ont confirmé que les méthodes basées sur des modèles (NEWUA) produisent généralement une précision plus élevée que les méthodes de recherche de motifs, même avec des budgets modestes, et que les paramètres d'échelle sont cruciaux pour visualiser ces différences.
• Analyse de l'Ensemble de Tests :
  • En utilisant des données synthétiques et en faisant varier la cardinalité de l'ensemble de tests ($|P|$), les Profils d'Ensemble de Tests ont montré que les ensembles de tests plus petits entraînent une variance plus élevée dans le classement des solveurs, confirmant la sensibilité de l'évaluation à la composition de l'ensemble de tests.

Signification et Revendications
Les auteurs affirment que les Profils de Qualité et les Profils d'Ensemble de Tests améliorent le processus d'évaluation en fournissant une image plus complète du comportement des solveurs. Spécifiquement :

• Ils permettent la comparaison d'algorithmes qui convergent vers des solutions différentes, un scénario où les profils de performance traditionnels sont souvent inadéquats ou nécessitent l'exclusion de données.
• Ils offrent un moyen d'évaluer le « revers de la médaille » de la robustesse des solveurs : la pertinence de l'ensemble de tests lui-même.
• L'approche est constructive plutôt qu'axiomatique ; elle ne prétend pas résoudre tous les paradoxes de classement (tels que ceux discutés par Liu et al.) mais fournit un outil pratique et fondé sur les données pour mesurer une dimension spécifique de la performance (la qualité de la solution).
• Ces outils sont particulièrement précieux dans l'optimisation sans dérivées et l'optimisation boîte noire, où les budgets fixes d'évaluations de fonctions sont courants, et où la qualité de la solution est la métrique de performance principale.

L'article conclut que ces outils doivent être considérés comme faisant partie d'un écosystème d'évaluation plus large, complétant l'analyse de l'espace des instances, la conception expérimentale rigoureuse et les règles de comparaison sans paradoxe, plutôt que de remplacer les méthodologies existantes.