Méthode du point intérieur

Les méthodes de points intérieurs (également appelées méthodes barrières ou IPM ) sont des algorithmes permettant de résoudre des problèmes d'optimisation convexe linéaires et non linéaires . Les IPM combinent deux avantages des algorithmes déjà connus :

• Théoriquement, leur temps d’exécution est polynomial , contrairement à la méthode du simplexe , qui a un temps d’exécution exponentiel dans le pire des cas.
• En pratique, elles fonctionnent aussi rapidement que la méthode du simplexe, contrairement à la méthode de l'ellipsoïde , qui a un temps d'exécution polynomial en théorie, mais est très lente en pratique.

Contrairement à la méthode du simplexe qui traverse la frontière de la région faisable, et à la méthode de l'ellipsoïde qui délimite la région faisable de l'extérieur , une méthode IPM atteint une meilleure solution en traversant l' intérieur de la région faisable — d'où son nom.

Une méthode de point intérieur a été découverte par le mathématicien soviétique II Dikin en 1967. La méthode a été réinventée aux États-Unis au milieu des années 1980. En 1984, Narendra Karmarkar a développé une méthode de programmation linéaire appelée algorithme de Karmarkar , qui s'exécute en temps polynomial démontrable ( opérations sur des nombres à L bits, où n est le nombre de variables et de constantes), et est également très efficace en pratique. L'article de Karmarkar a suscité un regain d'intérêt pour les méthodes de point intérieur. Deux ans plus tard, James Renegar a inventé la première méthode de point intérieur de suivi de chemin , avec un temps d'exécution . La méthode a ensuite été étendue des problèmes d'optimisation linéaire aux problèmes d'optimisation convexe, sur la base d'une fonction barrière auto-concordante utilisée pour coder l' ensemble convexe .

Tout problème d'optimisation convexe peut être transformé en minimisation (ou maximisation) d'une fonction linéaire sur un ensemble convexe en passant à la forme épigraphique . L'idée d'encoder l' ensemble faisable à l'aide d'une barrière et de concevoir des méthodes de barrière a été étudiée par Anthony V. Fiacco, Garth P. McCormick et d'autres au début des années 1960. Ces idées ont été principalement développées pour la programmation non linéaire générale , mais elles ont été abandonnées plus tard en raison de la présence de méthodes plus compétitives pour cette classe de problèmes (par exemple la programmation quadratique séquentielle ).

Yurii Nesterov et Arkadi Nemirovski ont mis au point une classe spéciale de telles barrières qui peuvent être utilisées pour coder n'importe quel ensemble convexe. Ils garantissent que le nombre d' itérations de l'algorithme est limité par un polynôme dans la dimension et la précision de la solution.

La classe des méthodes de suivi de chemin primal-dual à point intérieur est considérée comme la plus réussie. L'algorithme de prédiction-correction de Mehrotra fournit la base de la plupart des implémentations de cette classe de méthodes.

On nous donne un programme convexe de la forme : où f est une fonction convexe et G est un ensemble convexe . Sans perte de généralité, on peut supposer que l'objectif f est une fonction linéaire . Habituellement, l'ensemble convexe G est représenté par un ensemble d'inéquations convexes et d'égalités linéaires ; les égalités linéaires peuvent être éliminées en utilisant l'algèbre linéaire, donc pour simplifier nous supposons qu'il n'y a que des inégalités convexes, et le programme peut être décrit comme suit, où les g _i sont des fonctions convexes : On suppose que les fonctions de contrainte appartiennent à une famille (par exemple les fonctions quadratiques), de sorte que le programme peut être représenté par un vecteur fini de coefficients (par exemple les coefficients des fonctions quadratiques). La dimension de ce vecteur de coefficients est appelée la taille du programme. Un solveur numérique pour une famille donnée de programmes est un algorithme qui, étant donné le vecteur de coefficients, génère une séquence de solutions approchées x _t pour t =1,2,..., en utilisant un nombre fini d'opérations arithmétiques. Un solveur numérique est dit convergent si, pour tout programme de la famille et tout ε >0 positif, il existe un T (qui peut dépendre du programme et de ε ) tel que, pour tout t > T , la solution approchée x _t soit ε-approchée, c'est-à-dire : où est la solution optimale. Un solveur est dit polynomial si le nombre total d'opérations arithmétiques dans les T premières étapes est au plus

poly(taille du problème) * log( V / ε ),

où V est une constante dépendante des données, par exemple la différence entre la plus grande et la plus petite valeur de l'ensemble réalisable. En d'autres termes, V / ε est la « précision relative » de la solution, c'est-à-dire la précision par rapport au plus grand coefficient. log( V / ε ) représente le nombre de « chiffres de précision ». Par conséquent, un solveur est « polynomial » si chaque chiffre de précision supplémentaire nécessite un nombre d'opérations qui est polynomial dans la taille du problème.

Les types de méthodes de points intérieurs incluent :

• Méthodes de réduction de potentiel : l'algorithme de Karmarkar fut le premier.
• Méthodes de suivi de chemin : les algorithmes de James Renegar et Clovis Gonzaga furent les premiers.
• Méthodes prima-duales .

Étant donné un programme d'optimisation convexe (P) avec contraintes, nous pouvons le convertir en programme sans contraintes en ajoutant une fonction barrière . Plus précisément, soit b une fonction convexe lisse, définie à l'intérieur de la région réalisable G , telle que pour toute suite { x _j in interior(G)} dont la limite est sur la frontière de G : . Nous supposons également que b est non dégénéré, c'est-à-dire : est défini positif pour tout x in interior(G). Considérons maintenant la famille de programmes :

( P _t ) minimiser t * f(x) + b(x)

Techniquement, le programme est restreint, car b est défini uniquement à l'intérieur de G . Mais en pratique, il est possible de le résoudre comme un programme sans contrainte, car tout solveur essayant de minimiser la fonction n'approchera pas la frontière, où b tend vers l'infini. Par conséquent, ( P _t ) a une solution unique - notons-la x *( t ). La fonction x * est une fonction continue de t , qui est appelée le chemin central . Tous les points limites de x *, lorsque t tend vers l'infini, sont des solutions optimales du programme original (P).

Une méthode de suivi de chemin est une méthode de suivi de la fonction x * le long d'une certaine séquence croissante t ₁ ,t ₂ ,..., c'est-à-dire : calculer une approximation suffisamment bonne de x _i au point x *( t _i ), de telle sorte que la différence x _i - x *( t _i ) tende vers 0 lorsque i tend vers l'infini ; alors la séquence x _i tend vers la solution optimale de (P). Cela nécessite de spécifier trois choses :

• La fonction barrière b(x).
• Une politique permettant de déterminer les paramètres de pénalité t _i .
• Le solveur d'optimisation sans contrainte est utilisé pour résoudre ( P _i ) et trouver x _i , comme la méthode de Newton . Notez que nous pouvons utiliser chaque x _i comme point de départ pour résoudre le problème suivant ( P _i+1 ).

Le principal défi pour prouver que la méthode est polynomiale est que, à mesure que le paramètre de pénalité augmente, la solution se rapproche de la limite et la fonction devient plus raide. Le temps d'exécution des solveurs tels que la méthode de Newton devient plus long et il est difficile de prouver que le temps d'exécution total est polynomial.

Renegar et Gonzaga ont prouvé qu'une instance spécifique d'une méthode de suivi de chemin est le polytemps :

• Les contraintes (et l’objectif) sont des fonctions linéaires ;
• La fonction barrière est logarithmique : b(x) := - somme _j log( -g _j ( x )).
• Le paramètre de pénalité t est mis à jour géométriquement, c'est-à-dire , où μ est une constante (ils ont pris , où m est le nombre de contraintes d'inégalité) ;
• Le solveur est la méthode de Newton, et une seule étape de Newton est effectuée pour chaque étape unique de t .

Français Ils ont prouvé que, dans ce cas, la différence x _i - x *( t _i ) reste au plus égale à 0,01, et f( x _i ) - f* est au plus égale à 2* m / t _i . Ainsi, la précision de la solution est proportionnelle à 1/ t _i , donc pour ajouter un seul chiffre de précision, il suffit de multiplier t _i par 2 (ou tout autre facteur constant), ce qui nécessite O(sqrt( m )) pas de Newton. Comme chaque pas de Newton nécessite O( mn ² ) opérations, la complexité totale est de O( m ^3/2 n ² ) opérations pour le chiffre de précision.

Yuri Nesterov a étendu l'idée des programmes linéaires aux programmes non linéaires. Il a noté que la principale propriété de la barrière logarithmique, utilisée dans les preuves ci-dessus, est qu'elle est auto-concordante avec un paramètre de barrière fini. Par conséquent, de nombreuses autres classes de programmes convexes peuvent être résolues en temps polymérique en utilisant une méthode de suivi de chemin, si nous pouvons trouver une fonction de barrière auto-concordante appropriée pour leur région réalisable.

On nous donne un problème d'optimisation convexe (P) sous « forme standard » :

minimiser c ^T x st x dans G ,

où G est convexe et fermé. On peut aussi supposer que G est borné (on peut facilement le rendre borné en ajoutant une contrainte | x |≤ R pour un R suffisamment grand ).

Pour utiliser la méthode du point intérieur, nous avons besoin d'une barrière auto-concordante pour G . Soit b une barrière M -auto-concordante pour G , où M ≥1 est le paramètre d'auto-concordance. Nous supposons que nous pouvons calculer efficacement la valeur de b , son gradient et son Hessian , pour chaque point x à l'intérieur de G .

Pour tout t >0, on définit l' objectif pénalisé f _t (x) := t c ^T x + b( x ) . On définit le chemin des minimiseurs par : x*(t) := arg min f _t (x) . On approxime ce chemin le long d'une séquence croissante t _i . La séquence est initialisée par une certaine procédure d'initialisation non triviale en deux phases. Puis, elle est mise à jour selon la règle suivante : .

Pour chaque t _i , nous trouvons un minimum approximatif de f _ti , noté x _i . Le minimum approximatif est choisi pour satisfaire la « condition de proximité » suivante (où L est la tolérance de chemin ) :

Pour trouver x _{i +1} , nous commençons par x _i et appliquons la méthode de Newton amortie . Nous appliquons plusieurs étapes de cette méthode, jusqu'à ce que la « relation de proximité » ci-dessus soit satisfaite. Le premier point qui satisfait cette relation est noté x _{i +1} .

Le taux de convergence de la méthode est donné par la formule suivante, pour tout i :

En prenant , le nombre d'étapes de Newton nécessaires pour passer de x _i à x _{i +1} est au plus un nombre fixe, qui ne dépend que de r et L . En particulier, le nombre total d'étapes de Newton nécessaires pour trouver une solution ε -approchée (c'est-à-dire trouver x dans G tel que c ^T x - c* ≤ ε ) est au plus :

où le facteur constant O(1) ne dépend que de r et L. Le nombre d'étapes de Newton nécessaires pour la procédure d'initialisation en deux étapes est au plus :

où le facteur constant O(1) ne dépend que de r et L , et , et est un point à l'intérieur de G . Globalement, la complexité globale de Newton pour trouver une solution ε -approchée est au plus

Chaque étape de Newton nécessite O( n ³ ) opérations arithmétiques.

Pour initialiser les méthodes de suivi de chemin, nous avons besoin d'un point à l'intérieur relatif de la région faisable G . En d'autres termes : si G est défini par les inégalités g _i ( x ) ≤ 0, alors nous avons besoin d'un x pour lequel g _i ( x ) < 0 pour tout i dans 1,..., m . Si nous n'avons pas un tel point, nous devons en trouver un en utilisant une méthode dite de phase I . Une méthode de phase I simple consiste à résoudre le programme convexe suivant : On note la solution optimale par x*, s *.

• Si s *<0, alors nous savons que x* est un point intérieur du problème original et pouvons passer à la « phase II », qui consiste à résoudre le problème original.
• Si s *>0, alors nous savons que le programme original est irréalisable - la région réalisable est vide.
• Si s *=0 et qu'il est atteint par une solution x*, alors le problème est réalisable mais n'a pas de point intérieur ; s'il n'est pas atteint, alors le problème est infaisable.

Pour ce programme, il est facile d'obtenir un point intérieur : nous pouvons prendre arbitrairement x = 0, et prendre s comme un nombre supérieur à max( f ₁ (0),..., f _m (0)). Par conséquent, il peut être résolu en utilisant des méthodes de point intérieur. Cependant, le temps d'exécution est proportionnel à log(1/ s *). Lorsque s* se rapproche de 0, il devient de plus en plus difficile de trouver une solution exacte au problème de la phase I, et donc de décider si le problème initial est réalisable.

Les garanties théoriques supposent que le paramètre de pénalité augmente à la vitesse , de sorte que le nombre de pas de Newton requis dans le pire des cas est . En théorie, si μ est plus grand (par exemple 2 ou plus), alors le nombre de pas de Newton requis dans le pire des cas est . Cependant, en pratique, un μ plus grand conduit à une convergence beaucoup plus rapide. Ces méthodes sont appelées méthodes à pas longs . En pratique, si μ est compris entre 3 et 100, alors le programme converge en 20 à 40 pas de Newton, quel que soit le nombre de contraintes (bien que le temps d'exécution de chaque pas de Newton augmente bien sûr avec le nombre de contraintes). La valeur exacte de μ dans cette plage a peu d'effet sur les performances.

Pour les méthodes de réduction de potentiel, le problème est présenté sous la forme conique :

minimiser c ^T x st x dans {b+L} ∩ K ,

où b est un vecteur dans R ⁿ , L est un sous-espace linéaire dans R ⁿ (donc b + L est un plan affine ), et K est un cône convexe fermé et pointu avec un intérieur non vide. Tout programme convexe peut être converti en forme conique. Pour utiliser la méthode de réduction de potentiel (plus précisément, l'extension de l'algorithme de Karmarkar à la programmation convexe), nous avons besoin des hypothèses suivantes :

• A. L'ensemble des possibles {b+L} ∩ K est borné et coupe l'intérieur du cône K .
• B. On nous donne à l'avance une solution strictement réalisable x ^, c'est-à-dire une solution réalisable à l'intérieur de K .
• C. Nous connaissons à l’avance la valeur objective optimale, c*, du problème.
• D. On nous donne une barrière auto-concordante F M -logarithmiquement homogène pour le cône K.

Les hypothèses A, B et D sont nécessaires dans la plupart des méthodes de points intérieurs. L'hypothèse C est spécifique à l'approche de Karmarkar ; elle peut être atténuée en utilisant une « valeur objective glissante ». Il est possible de réduire encore le programme au format Karmarkar :

minimiser s ^T x st x dans M ∩ K et e ^T x = 1

où M est un sous-espace linéaire de dans R ⁿ , et la valeur objective optimale est 0. La méthode est basée sur la fonction potentielle scalaire suivante :

v ( x ) = F ( x ) + M ln ( s ^T x )

où F est la barrière auto-concordante M pour le cône réalisable. Il est possible de prouver que, lorsque x est strictement réalisable et v ( x ) est très petit (- très négatif), x est approximativement optimal. L'idée de la méthode de réduction de potentiel est de modifier x de telle sorte que le potentiel à chaque itération chute d'au moins une constante fixe X (plus précisément, X =1/3-ln(4/3)). Cela implique qu'après i itérations, la différence entre la valeur objective et la valeur objective optimale est au plus V * exp(- i X / M ), où V est une constante dépendante des données. Par conséquent, le nombre d'étapes de Newton nécessaires pour une solution ε -approximative est au plus .

Notez que dans les méthodes de suivi de chemin, l'expression est plutôt que M , ce qui est mieux en théorie. Mais en pratique, la méthode de Karmarkar permet de faire des pas beaucoup plus grands vers le but, elle peut donc converger beaucoup plus rapidement que les garanties théoriques.

L'idée de la méthode primale-duale est facile à démontrer pour l'optimisation non linéaire contrainte . Pour simplifier, considérons le problème d'optimisation non linéaire suivant avec des contraintes d'inégalité :

Ce problème d'optimisation sous contrainte d'inégalité est résolu en le convertissant en une fonction objective non contrainte dont on espère trouver efficacement le minimum. Plus précisément, la fonction barrière logarithmique associée à (1) est

Voici un petit scalaire positif, parfois appelé « paramètre barrière ». Comme converge vers zéro, le minimum de devrait converger vers une solution de (1).

Le gradient d'une fonction différentiable est noté . Le gradient de la fonction barrière est

En plus de la variable originale (« primaire »), nous introduisons une variable duale inspirée du multiplicateur de Lagrange

L'équation (4) est parfois appelée condition de « complémentarité perturbée », en raison de sa ressemblance avec le « relâchement complémentaire » dans les conditions KKT .

Nous essayons de trouver ceux pour lesquels le gradient de la fonction barrière est nul.

En substituant de (4) à (3), nous obtenons une équation pour le gradient : où la matrice est la Jacobienne des contraintes .

L'intuition derrière (5) est que le gradient de doit se situer dans le sous-espace engendré par les gradients des contraintes. La « complémentarité perturbée » avec un petit (4) peut être comprise comme la condition que la solution soit située près de la frontière , ou que la projection du gradient sur la composante normale de la contrainte soit presque nulle.

Soit la direction de recherche pour la mise à jour itérative de . En appliquant la méthode de Newton à (4) et (5), on obtient une équation pour :

où est la matrice hessienne de , est une matrice diagonale de , et est la matrice diagonale de .

En raison de (1), (4) la condition

doit être appliquée à chaque étape. Cela peut être fait en choisissant les éléments appropriés :

Voici quelques cas particuliers de programmes convexes qui peuvent être résolus efficacement par des méthodes de points intérieurs.

Considérons un programme linéaire de la forme : Nous pouvons appliquer des méthodes de suivi de chemin avec la barrière La fonction est auto-concordante avec le paramètre M = m (le nombre de contraintes). Par conséquent, le nombre d'étapes de Newton requises pour la méthode de suivi de chemin est O( mn ² ), et la complexité totale d'exécution est O( m ^3/2 n ² ).

Étant donné un programme quadratique contraint quadratiquement de la forme : où toutes les matrices A _j sont des matrices semi-définies positives . Nous pouvons appliquer des méthodes de suivi de chemin avec la barrière La fonction est une barrière auto-concordante avec un paramètre M = m . La complexité de Newton est O( (m+n)n ² ), et la complexité d'exécution totale est O( m ^1/2 (m+n) n ² ).

Considérons un problème de la forme où chacun est un vecteur, chacun est un scalaire et est une norme L _p avec Après conversion à la forme standard, nous pouvons appliquer des méthodes de suivi de chemin avec une barrière auto-concordante avec un paramètre M = 4 m . La complexité de Newton est O( (m+n)n ² ), et la complexité d'exécution totale est O( m ^1/2 (m+n) n ² ).

Considérez le problème

Il existe une barrière auto-concordante de paramètre 2 k + m . La méthode de suivi de chemin a une complexité de Newton O( mk ² + k ³ + n ³ ) et une complexité totale O(( k+m ) ^1/2 [ mk ² + k ³ + n ³ ]).

Les méthodes de points intérieurs peuvent être utilisées pour résoudre des programmes semi-définis.