Immunity to Increasing Condition Numbers of Linear Superiorization versus Linear Programming

Résumé Technique : Immunité face à l'augmentation des nombres de condition des problèmes de programmation linéaire par supériorisation linéaire versus la programmation linéaire

Énoncé du problème
L'article traite de la performance comparative des algorithmes de programmation linéaire (LP) et de la méthodologie de supériorisation linéaire (LinSup) lorsqu'ils sont appliqués à des problèmes de programmation linéaire caractérisés par des nombres de condition croissants. Alors que la programmation linéaire classique vise à trouver un point optimal (minimisant la fonction objectif sous contraintes), la méthode LinSup vise à trouver un point réalisable possédant une valeur de fonction objectif « supérieure » (réduite, bien que non nécessairement minimale). Le problème central étudié est la sensibilité de ces deux approches à l'imprécision (ill-posedness), spécifiquement comment l'augmentation des nombres de condition de la matrice de contrainte affecte le temps d'exécution, l'atteinte de la réalisabilité et la réduction de la fonction objectif de ces algorithmes.

Méthodologie
Les auteurs ont mené une étude expérimentale contrôlée comparant LinSup aux solveurs de LP établis.

• Génération de problèmes : Les chercheurs ont construit des problèmes de programmation linéaire de la forme $\min \langle c, x \rangle$ sous les contraintes $Ax \le b$ et $\ell \le x \le u$. Pour garantir une similitude structurelle entre les différents nombres de condition, ils ont utilisé la décomposition en valeurs singulières (SVD). Ils ont généré des matrices semi-orthogonales aléatoires $U$ et $V$ et construit des matrices diagonales $\Sigma_\kappa$ avec des valeurs singulières distribuées pour atteindre des nombres de condition $\kappa$ spécifiques (allant de bien conditionnés à hautement mal conditionnés). La taille des matrices variait de $80 \times 100$ à $4000 \times 5000$.
• Algorithmes testés :
  • LinSup : Implémentée en utilisant la méthode de projection d'Agmon-Motzkin-Schönberg (AMS) comme algorithme de base de recherche de réalisabilité. Des perturbations ont été introduites en utilisant le gradient négatif normalisé de la fonction objectif. L'algorithme employait des perturbations bornées et des projections cycliques avec des programmes de tailles de pas spécifiques et des mécanismes de redémarrage.
  • Solveurs LP : L'étude a comparé LinSup à scipy.simplex, scipy.revised simplex, scipy.interior-point et gurobi.primal simplex.
• Protocole expérimental : Pour assurer une comparaison équitable, les auteurs ont imposé un critère d'arrêt unifié basé sur un seuil d'inréalisabilité fixe ($\varepsilon = 10^{-8}$).
  • LinSup a été exécutée jusqu'à ce qu'elle atteigne ce seuil.
  • Les solveurs LP ont été exécutés sous le même seuil. Si un solveur LP ne parvenait pas à atteindre le seuil dans le temps $T_{sup}$ (le temps mis par LinSup pour se terminer), il était arrêté à $T_{sup}$, et son itéré actuel était enregistré.
  • Les métriques enregistrées comprenaient le temps d'exécution, les valeurs de la fonction objectif et les violations maximales des contraintes (inréalisabilité) à la terminaison et tout au long des itérations.

Contributions clés et résultats
L'étude fournit des preuves empiriques concernant la robustesse de LinSup par rapport aux solveurs LP classiques sous des conditions de difficulté variables :

1. Performance sur l'augmentation des dimensions ( $\kappa$ fixe) :

   • Pour les petites dimensions, les solveurs basés sur le simplex étaient plus rapides.
   • À mesure que les dimensions des problèmes augmentaient (jusqu'à $4000 \times 5000$), le temps d'exécution des implémentations du simplex (y compris Gurobi) augmentait de manière significative. Dans les hautes dimensions, LinSup s'est terminée plus rapidement que les solveurs simplex.
   • Notamment, dans les plus grandes dimensions testées, LinSup a atteint le seuil de réalisabilité avant même que les algorithmes simplex n'atteignent la réalisabilité.

2. Immunité face à l'augmentation des nombres de condition (Dimensions fixes) :

   • Méthodes Simplex : À mesure que le nombre de condition augmentait, les implémentations simplex de scipy présentaient une dégradation sévère. Elles se terminaient souvent prématurément avec des valeurs d'objectif sous-optimales, « renonçant » de fait face à la difficulté du problème.
   • Méthode du point intérieur : Bien que cette méthode ait semblé trouver rapidement des valeurs d'objectif basses, elle peinait à atteindre le niveau de réalisabilité requis pour des nombres de condition élevés, résultant en des valeurs d'inréalisabilité élevées (jusqu'à $10^1$).
   • LinSup : La méthode de supériorisation a démontré une stabilité remarquable. Son temps d'exécution est resté relativement constant quel que soit le nombre de condition, et elle a systématiquement atteint le niveau de réalisabilité cible ($\varepsilon = 10^{-8}$) à travers tous les nombres de condition testés.
   • Fonction objectif : LinSup a systématiquement produit de meilleures (plus basses) valeurs de fonction objectif au point de terminaison par rapport aux méthodes simplex dans les scénarios mal conditionnés.

3. Analyse Proximité-Cible :

   • Les graphiques d'inréalisabilité par rapport à la valeur de la fonction objectif (courbes de proximité-cible) ont confirmé que LinSup maintenait un chemin constant vers la réalisabilité tout en réduisant l'objectif. En revanche, la méthode du point intérieur présentait un décalage entre la recherche d'un objectif bas et la satisfaction des contraintes dans les contextes mal conditionnés.

Signification et affirmations
L'article affirme que la programmation linéaire par supériorisation offre un avantage distinct par rapport aux solveurs LP classiques lorsqu'on traite des systèmes linéaires mal conditionnés, particulièrement dans les scénarios à grande échelle.

• Robustesse : Les auteurs concluent que LinSup est moins affectée par les nombres de condition élevés que les solveurs LP testés. Ils attribuent cela à la nature de l'algorithme : LinSup effectue des projections individuelles sur des demi-espaces plutôt que de résoudre le système complet simultanément, et la « résilience aux perturbations bornées » de l'algorithme de base peut aider à absorber les erreurs de calcul qui seraient autrement amplifiées par le mauvais conditionnement.
• Utilité pratique : L'étude suggère que pour les applications où trouver un point réalisable avec une valeur d'objectif réduite est suffisant (une approche de « satisfaction » plutôt que d'optimalité stricte), LinSup est un outil plus fiable et efficace pour les problèmes mal posés.
• Portée modeste : Les auteurs déclarent explicitement que leurs résultats sont basés sur des configurations expérimentales et des tailles de problèmes spécifiques. Ils expriment leur confiance dans le fait que les tendances observées se tiendront pour des instances plus grandes, mais ne prétendent pas que LinSup remplace les solveurs LP pour toutes les tâches d'optimisation. Ils notent que LinSup n'est pas un solveur LP et ne vise pas l'optimalité sous contraintes, mais plutôt un point réalisable « supérieur ».
• Travaux futurs : L'article suggère que la robustesse observée de LinSup dans les contextes linéaires justifie une investigation dans les contextes non linéaires, particulièrement là où les méthodes de point intérieur sont connues pour éprouver des difficultés avec le mauvais conditionnement (par exemple, la radiothérapie modulée en intensité).