An inexact infeasible arc-search interior-point method for linear optimization problems

Résumé Technique : Une méthode de point intérieur par recherche d'arc inexacte et infaisable pour les problèmes d'optimisation linéaire

Énoncé du Problème
L'article traite de la résolution des problèmes d'optimisation linéaire (LOP) à l'aide de méthodes de point intérieur (IPM). Plus précisément, il se concentre sur les méthodes de point intérieur infaisables inexactes (II-IPM), qui sont des variantes conçues pour résoudre les LOP en partant d'un point initial infaisable et en résolvant les systèmes de Newton de manière inexacte (par exemple, via des solveurs itératifs comme le gradient conjugué). Bien que les solveurs inexacts réduisent le coût computationnel par itération pour les problèmes à grande échelle, les méthodes existantes de recherche de ligne infaisables inexactes souffrent d'un inconvénage majeur : l'accumulation des erreurs de linéarisation (provenant de l'approximation du chemin central) et des erreurs d'inexactitude (du solveur) le long d'une direction de recherche droite. Cette accumulation force l'algorithme à prendre des tailles de pas très petites, ce qui entraîne une borne de complexité d'itération dans le pire des cas relativement lâche de $O(n^2 L)$, où $n$ est le nombre de variables et $L$ la longueur binaire des données d'entrée.

Méthodologie
Les auteurs proposent une nouvelle méthode appelée II-arc (Méthode de point intérieur par recherche d'arc infaisable inexacte). L'innovation centrale consiste à remplacer la recherche standard par une ligne droite par une stratégie de recherche d'arc ellipsoïdal.

1. Cadre de recherche d'arc : Au lieu de se déplacer le long d'une ligne droite, la méthode approxime le chemin central par un arc ellipsoïdal défini par un développement de Taylor du second ordre. Le prochain itéré $(x_{k+1}, y_{k+1}, s_{k+1})$ est calculé comme suit :
   $$x(\alpha) = x_k - \dot{x} \sin(\alpha) + \ddot{x}(1 - \cos(\alpha))$$
   (et de même pour $y$ et $s$), où $\dot{x}, \ddot{x}$ sont les première et seconde dérivées du chemin central.
2. Résolution inexacte : La méthode résout les systèmes de Newton pour la première dérivée ($\dot{x}, \dot{y}, \dot{s}$) et la seconde dérivée ($\ddot{x}, \ddot{y}, \ddot{s}$) de manière inexacte. Les auteurs utilisent la formulation du Système d'Équations Normales Modifié (MNES) pour l'analyse théorique afin d'assouplir les exigences de résidu, bien que les expériences numériques utilisent le Système d'Équations Normales (NES) standard avec un préconditionneur de Jacobi en raison de l'instabilité numérique observée dans les implémentations MNES pour les problèmes à grande échelle.
3. Sélection de la taille du pas : La taille du pas $\alpha$ est choisie pour satisfaire des conditions de voisinage spécifiques (garantissant que l'itéré reste dans une région spécifique du chemin central) et une condition de type Armijo pour assurer une réduction suffisante du gap de dualité.
4. Analyse Théorique : Les auteurs prouvent que la trajectoire courbe de la recherche d'arc supprime l'erreur de linéarisation plus efficacement qu'une ligne droite. Cela permet à la taille du pas de rester plus grande même lorsque les systèmes de Newton sont résolus avec une inexactitude significative.

Contributions Clés

• Premier IPM d'arc inexact : À la connaissance des auteurs, il s'agit du premier article traitant d'un IPM inexact dans le cadre de la recherche d'arc.
• Amélioration de la Borne de Complexité : L'article établit une borne de complexité d'itération polynomiale de $O(n^{1.5} L)$ pour la méthode II-arc proposée. Cela représente une amélioration théorique par rapport à la meilleure borne connue pour les méthodes existantes de recherche de ligne infaisables inexactes ($O(n^2 L)$) par un facteur de $n^{0.5}$.
• Atténuation de l'Accumulation d'Erreur : Les auteurs démontrent que la stratégie de recherche d'arc atténue l'accumulation des erreurs de linéarisation et d'inexactitude, ce qui est le principal goulot d'étranglement des méthodes infaisables inexactes existantes.

Résultats Numériques
Les auteurs ont mené des expériences numériques sur des problèmes à grande échelle issus de la collection de benchmarks NETLIB (incluant DFL001, QAP15, STOCFOR3 et les problèmes de Kennington) en utilisant une implémentation Python avec le Gradient Conjugué Préconditionné (CG) comme solveur linéaire.

• Comparaison : La méthode II-arc proposée (spécifiquement la variante utilisant le point initial heuristique de Yang, "II-arc-Yang") a été comparée à une méthode existante de recherche de ligne infaisable inexacte ("II-line-Yang").
• Performance :
  • Itérations : II-arc-Yang a systématiquement nécessité moins d'itérations que II-line-Yang. Pour près de 25 % des problèmes de test, la méthode de recherche de ligne a nécessité deux fois ou plus d'itérations que la méthode de recherche d'arc.
  • Temps de Calcul : II-arc-Yang a réduit le temps de calcul total pour 75 % des problèmes. La réduction des itérations a compensé le coût supplémentaire de la résolution du système de la seconde dérivée.
  • Robustesse : La méthode a résolu avec succès 17 des 18 problèmes de test, démontrant une stabilité numérique.
• Points Initiaux : L'étude a également comparé un point initial constant à l'approche heuristique de Yang, trouvant que l'approche heuristique (II-arc-Yang) offrait généralement de meilleures performances en termes d'itérations et de temps.

Signification et Revendications
L'article affirme que la méthode II-arc proposée offre une borne de complexité d'itération dans le pire des cas prouvablement plus serrée que les méthodes de recherche de ligne infaisables inexactes existantes. La signification de ce travail réside dans le fait de combler l'écart entre les avantages théoriques de la recherche d'arc (meilleure approximation du chemin central) et la nécessité pratique des solveurs inexacts pour les problèmes à grande échelle.

Les auteurs notent modestement que, bien que la complexité théorique soit améliorée, l'objectif principal était de proposer le cadre et de discuter de sa convergence. Ils reconnaissent que les performances numériques pourraient être davantage améliorées par :

• L'implémentation de la méthode dans des langages plus rapides (par exemple, C++, Julia).
• L'étude de solveurs de systèmes linéaires inexacts et de préconditionneurs plus avancés.
• L'exploration de combinaisons avec la stratégie de redémarrage de Nesterov ou des IPM faisables.

L'article conclut que l'approximation par arc ellipsoïdal permet des tailles de pas plus grandes en présence d'inexactitude, conduisant à la fois à une réduction théorique de la complexité d'itération et à des améliorations pratiques pour la résolution de problèmes d'optimisation linéaire à grande échelle.