Optimisation linéaire algorithmes de points
intérieurs

Éléments constitutifs des algorithmes Cheminement

Résoudre le problème d’optimisation (P) revient à résoudre ses conditions d’optimalité (18.1), lesquelles sont nécessaires et suffisantes. En apparence simple, ce système d’équations et d’inéquations présente plusieurs difficultés, toutes liées aux conditions de complémentarité 0 6 s ⊥ x > 0. D’une part, l’équation s Tx = 0 qui exprime la perpendicularité de s et x est non linéaire. D’autre part, elle présente une « combinatoire » importante. Elle s’écrit en effet, du fait de la positivité de s et x : xisi = 0, pour tout i ∈ [1 : n] ; il faut donc décider pour tout indice i si xi = 0 ou si = 0, et il y a 2 n possibilités. Si l’on a un premier itéré primal-dual z := (x, y, s) avec x > 0 et s > 0, on pourrait songer à résoudre le système d’optimalité (18.1) directement par des itérations de Newton amorties : à chaque itération, on détermine un pas α > 0 le long de la direction de Newton d := (dx, dy, ds) de telle sorte que l’itéré suivant z+ := (x+, y+, s+) = z + αd vérifie encore x+ > 0 et s+ > 0. On sait en effet que la stricte positivité des variables x et s assure que l’équation de Newton associée au système d’optimalité est bien définie (la matrice est inversible par la proposition 18.4). L’expérience à montré que cette stratégie, qui est suivie par l’algorithme affine (« affine scaling algorithm »), ne conduit pas à des algorithmes polynomiaux. La raison provient probablement du fait que, lorsque z est proche du bord de l’ensemble admissible primal-dual, le pas α > 0 le long de d, assurant l’admissibilité des itérés, peut devenir très petit, empêchant tout progrès significatif vers la solution. Une des techniques mises au point pour obtenir la polynomialité consiste à forcer les itérés de rester proche du chemin central, d’une part, et à être moins gourmand, d’autre part, en ne cherchant pas à résoudre le système non linéaire (18.1) directement. Il est difficile de renoncer à la direction de Newton, dont on connaît les qualités, si bien que le fait de faire des déplacements le long de telles directions est conservé dans les algorithmes de points intérieurs considérés dans ce chapitre. De manière à prévenir le phénomène des petits pas décrit ci-dessus, les algorithmes vont maintenir les itérés suffisamment proches du chemin central étudié à la section 18.1. Nous montrerons en effet dans chaque cas que, dans ces conditions, le pas α pris le long de la direction de Newton est borné inférieurement par une constante strictement positive en O(n −ω), où ω > 0 dépend de l’approche algorithmique, en particulier du type de voisinage du chemin central où sont maintenus les itérés. Même si l’on peut regretter que la borne inférieure sur le pas dépende de n (il ne semble pas possible d’éviter cela), on est au moins assuré que les pas ne deviendront pas arbitrairement petits. Cette dépendance en n aura une incidence directe sur la complexité itérative des algorithmes, c’est-à-dire sur le nombre d’itérations qu’ils requièrent pour s’approcher d’une solution à ε > 0 près. Pour des raisons évidentes, on dit que les algorithmes qui viennent d’être brièvement décrits sont des méthodes de suivi de chemin. La solution que l’on recherche par ces algorithmes, le centre analytique de la face optimale situé au bout de chemin central, est un point singulier parce que la jacobienne du système de Newton n’y est en général pas inversible. On ne peut donc pas appliquer directement les techniques de suivi de chemin que l’on utilise dans les méthodes d’homotopie par exemple. Celles mises en œuvre pour suivre le chemin central dans les méthodes de points intérieurs sont originales. Elles dépendent des algorithmes, mais elles relèvent presque toujours d’un principe que l’on peut voir comme la poursuite d’un objectif fuyant, ce que l’on a schématisé à la figure 18.1 : en l’itéré zk ∈ Fs de l’itération k, on se fixe pour objectif un point z(µk) sur le chemin central C, mais après avoir fait un pas de Newton dans sa direction (parfois plusieurs pas) conduisant à zk+1, on change d’objectif en visant un autre point z(µk+1) sur le chemin central, plus près de la solution (µk+1 < µk). On se rapproche ainsi petit à petit de la solution cherchée, laquelle est en quelque sorte inaccessible directement. Ce principe s’est avéré fécond. Certains algorithmes imposent aux itérés d’être strictement admissibles (section 18.3). Leur complexité itérative est en O(n ω log ε −1 ), avec ω = 1 2 ou 1, ce qui veut dire que le nombre d’itérations pour atteindre une solution à ε > 0 près est majoré par une constante (indépendante de n et de ε) fois n ω log ε −1 (une définition précise de cette complexité itérative sera donnée plus loin). La complexité itérative en O(n 1/2 log ε −1 ) est la meilleure que l’on ait obtenue ; mais les algorithmes qui la réalisent demandent que l’on dispose d’un premier itéré strictement admissible. D’autres algorithmes autorisent les itérés à ne pas satisfaire les équations linéaires de (18.1), ce qui peut être utile s’il n’y a pas de point primal-dual strictement admissible (c’est-à-dire si F s = ∅) ou si l’on ne dispose pas initialement d’un tel point. Leur complexité itérative est moins bonne ; elle est en O(n 2 log ε −1 ) pour l’algorithme étudié à la section 18.4. Voici à présent quelques concepts qui jouent un rôle-clé dans l’étude des algorithmes de points intérieurs.

Mesures du saut de dualité et du centrage

 Le contrôle des itérés dans les algorithmes de points intérieurs se fait par plusieurs « mesures » : mesure du saut de dualité, mesure du centrage et mesure de l’admissibilité. Si l’on veut se donner une cible sur le chemin central primal-dual C, il est nécessaire de savoir près de quel point central l’itéré courant z se trouve. Il n’y aurait en effet pas de sens à se donner une cible qui soit plus éloignée de la solution que ne l’est l’itéré courant. Trouver le point central le plus proche de z n’est cependant pas un problème simple, ni d’ailleurs bien posé car, le chemin central n’étant pas un convexe fermé, la projection de z sur C n’est en général pas bien définie (proposition 2.25). Par contre, l’image de C par l’application surjective (et bijective si A est surjective, voir l’exercice 18.2) p : z = (x, y, s) ∈ Fs 7→ (x1s1, . . . , xnsn) ∈ R n ++ (18.15) est la demi-droite {µe : µ > 0}, si bien que la projection dans l’espace d’arrivée de cette application se fait trivialement en résolvant le problème

Sur la complexité itérative des algorithmes

 Contrairement à l’algorithme du simplexe, les méthodes de points intérieurs ne sont pas des algorithmes à terminaison finie : ils ne trouvent pas la solution en un nombre fini d’étapes. En effet, à chaque itération, on a x > 0 et s > 0, ce qui n’est jamais le cas en une solution de (P) (voir la troisième condition dans (18.1)). On ne peut donc estimer que le nombre d’opérations pour trouver une solution à ε > 0 près. La proximité de la solution se mesurera ici par la petitesse du saut de dualité µ¯(z). En réalité, il existe des procédures, dites de purification (section ??), permettant de déterminer une solution exacte strictement complémentaire par quelques opérations d’algèbre linéaire à partir d’un itéré généré par un algorithme de points intérieurs, suffisamment proche de la face optimale. On ne s’intéressera ici qu’à la complexité itérative des algorithmes. On veut dire par là que l’on cherche à estimer le nombre d’itérations nécessaires pour obtenir une solution à ε > 0 près, dans le pire des cas. Les résultats que nous donnerons sur cette question feront usage du lemme suivant. On note {zk} la suite des itérés générés par l’algorithme considéré et µ¯k = ¯µ(zk).