Adaptive Metrics for Norm-Minimization-Based Outer Approximation in Convex Vector Optimization

Résumé Technique : Métriques Adaptatives pour l'Approximation Extérieure Basée sur la Minimisation de Norme en Optimisation Vectorielle Convexe

Énoncé du Problème
L'article traite de l'approximation de l'image supérieure $P := \Gamma(X) + C$ dans des problèmes d'optimisation vectorielle convexe (CVOP) bornés, où $X$ est un ensemble convexe compact, $\Gamma$ une application $C$-convexe continue, et $C$ un cône polyédrique fermé, solide et pointé. L'objectif est de construire une approximation extérieure polyédrique de $P$ avec une borne d'erreur garantie dans la distance de Hausdorff. Bien que les algorithmes d'approximation extérieure pilotés par des scalarisations minimisant la norme aient été établis comme possédant une terminaison finie et des taux de convergence, un vide subsistait concernant la dépendance de ces taux vis-à-vis du choix de la norme de scalarisation. Plus précisément, des travaux antérieurs d'Ararat et al. [4] ont démontré un taux de convergence amélioré de $O(k^{2/(1-q)})$ pour la norme euclidienne standard ($\ell_2$), tandis que le taux générique pour des normes arbitraires était de $O(k^{1/(1-q)})$. Il restait incertain de savoir si cette amélioration était un artefact de la structure euclidienne ou une propriété de géométries hilbertiennes plus générales, et si l'adaptation dynamique de la métrique pouvait encore améliorer les performances.

Méthodologie
L'article développe un cadre théorique et un algorithme adaptatif pour répondre à ces questions à travers trois mécanismes principaux :

1. Isométrie Linéaire et Invariance : Les auteurs établissent que toute norme issue d'un produit scalaire $\|y\|_M = \sqrt{y^\top M y}$ (où $M \succ 0$) est isométrique à la norme euclidienne via la transformation linéaire $T = M^{1/2}$. Ils prouvent que l'algorithme d'approximation extérieure basé sur la minimisation de norme est invariant sous cette transformation. Par conséquent, le comportement de l'algorithme dans un espace de produit scalaire arbitraire est équivalent à son comportement dans l'espace euclidien sous un problème transformé. Cela permet de transférer l'analyse de convergence du cas euclidien à toute norme de produit scalaire.

2. Cadre à Métrique Adaptative : Les auteurs proposent un algorithme où la norme de scalarisation varie à chaque itération $k$ en fonction de l'historique des normales de coupes. Spécifiquement, la métrique $M_k$ est construite comme une moyenne régularisée des produits externes des normales de coupes normalisées : $M_k = \varepsilon_0 I + \frac{1}{k} \sum_{i=1}^k u_i u_i^\top$. Bien que la scalarisation utilise cette métrique adaptative $M_k$, l'erreur d'approximation est mesurée et le critère d'arrêt est appliqué en utilisant une norme euclidienne fixe.

3. Théorème de Dispersion : Pour garantir que les métriques adaptatives restent bien conditionnées (c'est-à-dire que le nombre de conditionnement n'explose pas), l'article introduit une condition de « dispersion ». Cette condition exige que la séquence des normales de coupes se répartisse suffisamment dans toutes les directions de l'espace des objectifs. Les auteurs prouvent que si la frontière efficiente de la tranche de l'image supérieure est une hypersurface strictement convexe à courbure bornée (Hypothèse 3), les normales de coupes se dispersent naturellement. Cette propriété géométrique garantit que la plus petite valeur propre de la matrice de covariance empirique des normales reste bornée loin de zéro, assurant ainsi que la métrique adaptative reste bien conditionnée tout au long de l'exécution.

Contributions Clés
L'article apporte cinq contributions distinctes :

• Extension des Taux de Convergence : Il prouve que le taux de convergence amélioré $O(k^{2/(1-q)})$, précédemment connu uniquement pour la norme euclidienne, s'étend à toutes les normes de produit scalaire. Cela est réalisé en exploitant l'isométrie linéaire entre l'espace de produit scalaire et l'espace euclidien, montrant que le taux dépend de la géométrie hilbertienne plutôt que de la structure euclidienne spécifique.
• Bornes de Convergence Explicites : Les auteurs dérivent des bornes de convergence explicites dans les coordonnées originales, quantifiant comment les propriétés spectrales de la matrice de produit scalaire $M$ influencent les constantes dans les estimations d'erreur.
• Convergence à Métrique Adaptative : Ils établissent la correction et la convergence euclidienne de la variante à métrique adaptative. Sous des bornes spectrales uniformes sur les métriques adaptatives, ils fournissent des bornes explicites montrant qu'un meilleur conditionnement de la métrique (meilleure dispersion) conduit à des constantes de convergence plus précises.
• Théorème de Dispersion : Un résultat théorique central (Théorème 15) fournit des conditions géométriques suffisantes (convexité stricte avec courbure bornée de la frontière efficiente) sous lesquelles les métriques adaptatives restent bien conditionnées. Cela comble le fossé entre la théorie à norme fixe et l'observation pratique que l'adaptation à la géométrie du problème accélère la convergence.
• Validation Numérique : L'article présente des expériences numériques sur trois problèmes tests (incluant des ensembles réalisables sphériques et ellipsoïdaux) validant les taux théoriques et démontrant l'efficacité pratique de l'approche adaptative.

Résultats

• Taux Théoriques : Les expériences confirment le taux théorique $O(k^{2/(1-q)})$ pour des normes de produit scalaire fixes. Pour la métrique adaptative, bien que la garantie théorique soit le taux générique $O(k^{1/(1-q)})$ (Théorème 18), les résultats empiriques montrent des améliorations de performance cohérentes.
• Économies d'Itérations : Sur des problèmes avec des fronts de Pareto courbes (Exemples 1 et 2), l'approche à métrique adaptative a réduit le nombre d'itérations nécessaires pour atteindre une tolérance spécifique de 31–33 % par rapport à la norme euclidienne fixe.
• Conditionnement de la Métrique : Les expériences ont vérifié empiriquement la condition de dispersion. La plus petite valeur propre de la matrice de covariance empirique $\Sigma_k$ est restée bornée loin de zéro (par exemple $\approx 0,15$), et le paramètre de qualité de la métrique $\theta_k$ s'est stabilisé dans la plage $[0,41, 0,54]$, confirmant que les métriques sont restées bien conditionnées.
• Stratégies en Haute Dimension : Pour des dimensions $q \ge 4$, où l'énumération complète des sommets est computationnellement prohibitive, l'article a évalué des stratégies de « sonde LP » et « hybrides ». La métrique adaptative combinée à une stratégie de sonde LP a atteint la convergence la plus rapide (nombre d'itérations le plus faible) dans le cas en haute dimension testé ($q=4$).
• Limites : Dans un problème avec un front de Pareto parabolique et un nombre d'itérations très faible (Exemple 3), la métrique adaptative n'a offert aucune accélération, attribué à une accumulation de données insuffisante pour que le mécanisme d'adaptation s'engage efficacement.

Signification et Revendications
L'article revendique fournir une fondation rigoureuse pour l'utilisation de métriques de produit scalaire adaptatives et conscientes de la géométrie dans l'optimisation vectorielle convexe basée sur la minimisation de norme. Sa signification principale réside dans :

1. Clarification des Origines Géométriques : Il démontre que l'exposant de convergence amélioré est une propriété de la géométrie hilbertienne (espaces de produit scalaire) plutôt que de la norme euclidienne spécifique, résolvant une ambiguïté théorique.
2. Justification de l'Adaptativité : Il offre la première justification rigoureuse pour la sélection de métriques adaptatives dans ce contexte, prouvant que sous des conditions géométriques naturelles (convexité stricte), l'algorithme se corrige lui-même pour maintenir des métriques bien conditionnées, évitant ainsi la dégradation des constantes de convergence.
3. Efficacité Pratique : Les résultats suggèrent que pour des problèmes avec des fronts de Pareto courbes, l'adaptation de la métrique de scalarisation à l'historique des coupes peut réduire considérablement l'effort computationnel (nombre d'itérations) sans augmenter significativement le coût par itération.

Les auteurs restent modestes concernant le taux de convergence de la métrique adaptative elle-même ; bien qu'ils observent des économies d'itérations, ils notent que prouver le taux amélioré $O(k^{2/(1-q)})$ pour le cas adaptatif reste une question ouverte, car l'argument d'isométrie standard échoue lorsque la métrique change à chaque itération. Ils notent également que la théorie actuelle repose sur la convexité stricte et l'énumération complète des sommets, limitant sa portée immédiate aux frontières non lisses et aux stratégies de recherche de sommets approximatives.