Résumé Technique : Optimisation Riemannienne Sans Métrique

1. Énoncé du Problème

L'optimisation riemannienne est un cadre puissant pour l'optimisation sous contraintes, particulièrement sur les variétés de matrices rencontrées en vision par ordinateur, en traitement du signal et en calcul quantique. Elle traite les contraintes comme des propriétés géométriques intrinsèques, évitant ainsi le recours aux multiplicateurs de Lagrange ou aux projections explicites. Cependant, un goulot d'étranglement pratique important existe : l'évaluation ou l'application explicite de la métrique riemannienne peut être coûteuse en termes de calcul ou numériquement instable.

Dans certaines applications spécifiques, telles que les cadres adaptatifs à l'énergie pour les problèmes de valeurs propres non linéaires, l'application de la métrique équivaut à l'application d'un hamiltonien, ce qui est coûteux. De plus, les algorithmes standards comme le Gradient Conjugué Riemannien (RCG) nécessitent souvent plusieurs applications de la métrique pour calculer les tailles de pas et les paramètres de CG. Ce travail étudie dans quelle mesure les algorithmes classiques d'optimisation riemannienne peuvent être reformulés pour éviter l'application explicite de la métrique, améliorant ainsi l'efficacité sans sacrifier la rigueur mathématique.

2. Méthodologie

Le cœur de la méthodologie repose sur l'observation selon laquelle de nombreuses quantités de premier ordre en optimisation riemannienne dépendent uniquement de la différentielle de la fonction objectif ($Df(x)$) et de l'accès au gradient riemannien ($\text{grad}f(x)$), plutôt que de l'application explicite du tenseur métrique.

2.1. Le Principe Sans Métrique

L'article établit un principe général pour la reformulation des quantités d'optimisation. Bien que le gradient riemannien soit défini via le théorème de représentation de Riesz ($\langle \text{grad}f(x), v \rangle_x = Df(x)[v]$), les quantités exprimées classiquement comme des produits scalaires impliquant le gradient peuvent souvent être réécrites comme des dérivées directionnelles.

• Euclidien vs Riemannien : Dans l'espace euclidien, minimiser les applications de produits scalaires est une optimisation standard. Dans l'espace riemannien, la généralisation « naïve » nécessite souvent de transporter des vecteurs vers un espace tangent commun et d'appliquer la métrique dans cet espace.
• Formulation Sans Métrique : L'article propose d'exprimer ces quantités directement via la différentielle $Df(x)$. Par exemple, au lieu de calculer $\langle g, d \rangle$, on calcule $Df(x)[d]$. Cette approche minimise le nombre de transports de vecteurs requis et contourne complètement l'application explicite du tenseur métrique.

2.2. Analogie avec le Préconditionnement

L'article établit un parallèle avec la méthode du Gradient Conjugué Préconditionné (PCG) euclidien. Dans le PCG, résoudre un système avec une matrice $A$ en utilisant un préconditionneur $M$ est mathématiquement équivalent à effectuer des gradients conjugués par rapport au produit scalaire $\langle \cdot, \cdot \rangle_M$. L'article démontre que, tout comme le PCG peut être implémenté sans former explicitement le produit scalaire $M$ (en utilisant $M^{-1}$ sur les résidus), l'optimisation riemannienne peut être effectuée en utilisant une métrique « peu coûteuse » pour le calcul des tailles de pas, tout en s'appuyant sur une évaluation « peu coûteuse » de la différentielle pour les termes liés au gradient, évitant ainsi totalement l'application de la métrique « coûteuse ».

2.3. Reformulation des Composants Clés

L'auteur reformule systématiquement les composants standards de l'optimisation riemannienne en versions sans métrique :

• Conditions de Direction de Recherche : Les conditions de descente et de descente suffisante sont reformulées en utilisant $Df(x)[d] < 0$ plutôt que des produits scalaires.
• Conditions de Recherche de Pas :
  • Armijo & Goldstein : Reformulées en utilisant $Df(x)[d]$ au lieu de produits scalaires.
  • Conditions de Courbure : Les conditions de Wolfe faible et forte sont exprimées en utilisant le transport de la rétraction différenciée ($T_{td_k}(d_k)$) et la différentielle, évitant ainsi le besoin de calculer les gradients aux points d'essai si cela n'est pas strictement nécessaire pour la vérification de la condition.
• Stratégies de Taille de Pas :
  • Pas de Polyak : Reformulé en utilisant $Df(x)[\text{grad}f(x)]$.
  • Barzilai-Borwein (BB) : La formulation sans métrique sépare les expressions pour minimiser les transports de vecteurs, utilisant les différentielles plutôt que les gradients transportés et les produits scalaires.
• Paramètres de Gradient Conjugué : L'article fournit des formulations sans métrique pour les paramètres de Hestenes-Stiefel (HS), Fletcher-Reeves (FR), Polak-Ribière-Polyak (PRP) et Dai-Yuan (DY). Par exemple, le paramètre FR, typiquement $\|\text{grad}f(x_k)\|^2 / \|\text{grad}f(x_{k+1})\|^2$, est reformulé en $Df(x_k)[\text{grad}f(x_k)] / Df(x_{k+1})[\text{grad}f(x_{k+1})]$.

2.4. Extensions aux Variétés Non-Riemanniennes

L'article explore l'applicabilité de ces stratégies sans métrique aux variétés sans métrique riemannienne :

• Variétés de Banach : Bien que le Hessien riemannien soit indéfini, des méthodes de type Newton peuvent être construites en utilisant l'application dérivée $Df: M \to T^*M$ et les transports de vecteurs vers l'arrière. Les conditions de descente et les stratégies de recherche de pas restent valides.
• Variétés de Finsler : En utilisant la définition de Golomb-Tapia, un « gradient de Finsler » est défini comme le maximiseur de la différentielle sur la boule unité de l'espace tangent. L'article soutient que toutes les quantités sans métrique discutées précédemment (conditions de descente, recherches de pas, paramètres de CG) sont bien définies dans ce cadre, permettant des méthodes de descente de gradient et de gradient conjugué sur les variétés de Finsler.

3. Contributions Clés

1. Reformulations Sans Métrique : L'article fournit des reformulations explicites et mathématiquement équivalentes pour un large éventail de composants d'optimisation riemannienne (conditions de descente, recherches de pas, tailles de pas et paramètres de CG) qui éliminent l'application explicite de la métrique riemannienne.
2. Généralisation aux Cadres Finsler/Banach : Il démontre que ces reformulations s'étendent naturellement aux variétés de Finsler et de Banach, suggérant qu'une part substantielle de l'optimisation riemannienne est indépendante de la structure métrique spécifique.
3. Efficacité Algorithmique : La méthodologie réduit la surcharge de calcul en évitant les applications de métrique coûteuses et les inversions de matrices associées au calcul du gradient dans la métrique « coûteuse », en les remplaçant par des évaluations de différentielles plus légères.
4. Stabilité Numérique : En évitant l'application explicite de la métrique et les transports de vecteurs inutiles, l'approche réduit les sources potentielles d'erreur numérique.

4. Résultats Numériques

L'efficacité de la stratégie proposée a été démontrée par des expériences numériques sur un problème de valeur propre de Laplace 2D sur la sphère unité ($S^{n-1}$) avec une métrique non standard et coûteuse définie par un préconditionneur $M \approx A$.

• Configuration : Le problème consistait à minimiser $E(x) = \frac{1}{2}x^T Ax$ sur la sphère. La métrique « coûteuse » impliquait une décomposition $LDL^T$.
• Comparaison : L'étude a comparé trois méthodes :
  1. RCG avec métrique euclidienne standard (2-RCG).
  2. RCG avec métrique « coûteuse » standard (M-RCG).
  3. RCG sans métrique avec métrique « coûteuse » (M-RCG-mf).
• Performance :
  • Convergence : M-RCG et M-RCG-mf étaient mathématiquement équivalents, convergeant en le même nombre d'itérations (230).
  • Efficacité : La variante sans métrique (M-RCG-mf) a obtenu une réduction d'environ 82 % du temps CPU et une réduction d'environ 78 % du nombre total de multiplications matrice-vecteur par rapport au M-RCG standard.
  • Mécanisme : L'accélération était principalement due à l'élimination de l'application explicite de la métrique $M$ et du calcul du gradient $\text{grad}_M f(x)$ coûteux lors des vérifications de la recherche de pas, en s'appuyant plutôt sur la différentielle $Df(x)$ plus légère et sur la métrique euclidienne pour les calculs de taille de pas.

5. Signification et Revendications

L'article affirme qu'une partie substantielle de l'optimisation riemannienne peut être réalisée indépendamment de l'application explicite de la métrique. La signification réside dans :

• Élargissement de l'Applicabilité : L'approche rend l'optimisation riemannienne viable pour des problèmes où la métrique est implicitement définie, coûteuse à évaluer ou numériquement instable (ex: problèmes de valeurs propres non linéaires).
• Efficacité de Calcul : Elle offre une voie directe vers des gains de performance significatifs sans modifier les propriétés de convergence des algorithmes sous-jacents.
• Aperçu Théorique : Elle souligne que de nombreuses quantités « riemanniennes » sont en réalité des propriétés de premier ordre indépendantes de la métrique, suggérant que le cadre est plus robuste et généralisable (aux espaces de Finsler/Banach) qu'utilisé précédemment en pratique.

L'auteur note que, bien que les méthodes de second ordre (comme Newton riemannien) ne puissent généralement pas être rendues sans métrique en raison de leur dépendance à la courbure, les méthodes de premier ordre discutées ici représentent un sous-ensemble important et pratiquement crucial des algorithmes d'optimisation.