Extended-Krylov-subspace methods for trust-region and norm-regularization subproblems

1. Problématique

L'article s'intéresse à la résolution efficace des sous-problèmes qui apparaissent dans de nombreuses applications d'optimisation non linéaire, notamment :

• Le sous-problème de la région de confiance (Trust-Region Subproblem - TRS) :
  $$\min_{x \in \mathbb{R}^n} \frac{1}{2}x^T A x - b^T x \quad \text{sous} \quad \|x\| \leq \Delta$$
  où $A$ est une matrice Hessienne symétrique (éventuellement indéfinie), $b$ un vecteur, et $\Delta$ le rayon de confiance.
• Le sous-problème de régularisation par norme (Norm-Regularization Subproblem) :
  $$\min_{x \in \mathbb{R}^n} \frac{1}{2}x^T A x - b^T x + \frac{\rho}{r} \|x\|^r$$
  où $\rho > 0$ est un poids de régularisation.

Les méthodes existantes se divisent généralement en deux catégories :

1. Méthodes basées sur la factorisation (ex: Moré-Sorensen) : Précises mais coûteuses en temps de calcul car elles nécessitent plusieurs factorisations de matrices décalées ($A + \sigma I$) pour trouver le paramètre de décalage optimal $\sigma$.
2. Méthodes sans factorisation basées sur les sous-espaces de Krylov standards (ex: GLTR) : Efficaces pour les grands problèmes mais peuvent converger lentement lorsque le paramètre $\sigma$ est proche de la valeur minimale $\sigma_{\min}$ (cas où la solution est proche de la frontière ou dans le cas "difficile").

2. Méthodologie et Contributions Clés

Les auteurs proposent une nouvelle approche hybride, nommée TREK (Trust-Region Extended Krylov) et NREK (Norm-Regularization Extended Krylov), qui combine les avantages des deux approches précédentes.

A. Observation Fondamentale : Dimensionalité Faible

Les auteurs démontrent théoriquement et numériquement que l'ensemble des solutions $x(\sigma)$ du système $(A + \sigma I)x = b$, lorsque $\sigma$ varie, réside dans un sous-espace de très faible dimension (approximativement de rang faible), indépendamment de la taille $n$ du problème.

• En analysant la matrice de Cauchy généralisée associée aux solutions pour différents $\sigma$, ils montrent que le rang numérique de cette matrice est très faible (souvent inférieur à 40 pour des problèmes de grande taille).
• Cela implique qu'il est possible de construire une base de petite taille pour approximer l'ensemble des solutions sans avoir besoin de factoriser la matrice à chaque itération.

B. L'Algorithme EKS (Extended Krylov Subspace)

Pour capturer cette structure de faible dimension, les auteurs utilisent un sous-espace de Krylov étendu (Extended Krylov Subspace - EKS). Contrairement au sous-espace de Krylov standard $\mathcal{K}_m(A, b) = \text{span}\{b, Ab, \dots, A^{m-1}b\}$, le sous-espace étendu inclut également les puissances inverses de la matrice :
$$\mathcal{K}_{2m}(A, b) = \text{span}\{b, A^{-1}b, Ab, A^{-2}b, \dots, A^{-m}b\}$$

• Justification : L'inclusion de $A^{-1}$ permet de mieux approximer le comportement de la solution lorsque $\sigma$ est petit (proche de $\lambda_1(A)$), tandis que les puissances de $A$ capturent le comportement pour $\sigma$ grand.
• Construction : Un algorithme itératif (Algorithme 4.1) construit une base orthonormée $V_{2m+1}$ de ce sous-espace en effectuant un seul produit matrice-vecteur ($Av$) et une seule résolution de système linéaire ($A^{-1}v$) par itération.
• Structure de la matrice projetée : La matrice projetée $P = V^T A V$ possède une structure creuse spécifique (pentadiagonale), ce qui permet de résoudre le sous-problème réduit de très faible coût.

C. Gestion des Cas Généraux et Indéfinis

• Matrices Indéfinies : Si $A$ n'est pas définie positive, l'inversion directe $A^{-1}$ est impossible. Les auteurs proposent de décaler la matrice par un scalaire $\sigma_S$ (calculé via le théorème de Gershgorin) pour rendre $A_{\sigma_S} = A + \sigma_S I$ définie positive, puis d'appliquer la méthode EKS sur cette matrice décalée.
• Normes Elliptiques : La méthode est généralisée pour des contraintes de la forme $\|Rx\| \leq \Delta$ ou $\|x\|_S \leq \Delta$ en transformant le problème via des matrices de préconditionnement.
• Cas "Difficile" (Hard Case) : Une petite perturbation pseudo-aléatoire est ajoutée au vecteur $b$ pour éviter les cas dégénérés où $b$ est orthogonal aux vecteurs propres associés à la plus petite valeur propre.

D. Résolution du Sous-Problème Réduit

Une fois la base $V_\ell$ construite, le problème original de grande dimension est projeté sur un problème de très petite dimension ($\ell \ll n$) :
$$\min_{y \in \mathbb{R}^\ell} \frac{1}{2}y^T P_\ell y - b_\ell^T y \quad \text{sous} \quad \|y\| \leq \Delta$$
Ce sous-problème est résolu efficacement en utilisant une factorisation spectrale de la petite matrice pentadiagonale $P_\ell$, suivie d'une méthode de recherche de racines d'ordre élevé (sans factorisation supplémentaire de matrices de grande taille).

3. Résultats Numériques

Les auteurs ont évalué leurs algorithmes (TREK et NREK) sur un ensemble de 93 problèmes tests de la bibliothèque CUTEst (avec $n \geq 1000$) et les ont comparés à :

• TRS : Une méthode de factorisation multiple (GALAHAD).
• GLTR : Une méthode de Krylov standard sans factorisation (GALAHAD).

Principales constatations :

• Performance Globale : TREK n'est pas toujours le gagnant absolu, mais il se positionne comme une alternative très compétitive.
• Avantage de la Factorisation Unique : Contrairement à TRS qui nécessite plusieurs factorisations (coûteuses), TREK n'en nécessite qu'une seule (pour l'inversion initiale ou le décalage).
• Efficacité pour les grands rayons : Les résultats montrent que l'approche EKS est particulièrement efficace lorsque le rayon de confiance $\Delta$ est grand (ce qui correspond à un $\sigma$ proche de $\sigma_{\min}$), un scénario où les méthodes de Krylov standard (GLTR) convergent souvent lentement.
• Coût de calcul : Dans de nombreux cas, TREK est plus rapide que TRS et plus robuste que GLTR, surtout lors de la résolution séquentielle de problèmes avec des rayons décroissants (réutilisation du sous-espace).
• Convergence Rapide : Le nombre d'itérations nécessaire pour construire un sous-espace de bonne qualité est très faible (souvent moins de 20 itérations, même pour des problèmes de grande taille).

4. Signification et Conclusion

Cet article apporte une contribution significative à l'optimisation numérique en :

1. Validant théoriquement que l'ensemble des solutions des sous-problèmes de région de confiance réside dans un sous-espace de très faible dimension.
2. Proposant une méthode pratique (EKS) qui exploite cette propriété en combinant les produits par $A$ et $A^{-1}$, offrant ainsi une convergence rapide sur tout le spectre des paramètres de décalage.
3. Offrant un compromis optimal entre les méthodes de factorisation (précises mais lourdes) et les méthodes itératives sans factorisation (légères mais parfois lentes).

Les algorithmes sont implémentés dans la bibliothèque logicielle GALAHAD (en Fortran) avec des interfaces pour C, Python, Julia et Matlab. Cette méthode élargit la boîte à outils des solveurs d'optimisation, permettant de traiter des sous-problèmes de confiance et de régularisation de manière plus efficace, en particulier pour les problèmes non convexes ou lorsque le rayon de confiance est grand.