Méthodes de points intérieurs

Méthodes de points intérieurs en optimisation convexe

16.1.1 Vue d’ensemble Soit E un espace vectoriel de dimension finie (> 1), muni d’un produit scalaire h·, ·i, dit de référence, et de sa norme associée k · k. Dans cette section, nous nous intéressons à la résolution numérique de problèmes d’optimisation convexes, que l’on supposera écrits sous la forme (P)  inf hc, xi x ∈ X. (16.1) Ici c ∈ E et X est un convexe de E. Le fait que le critère soit linéaire n’introduit pas de perte de généralité, car on peut toujours faire passer en contrainte un critère, qui serait ici convexe, comme à la proposition 1.13. La théorie que nous présentons ci-dessous, principalement développée par Nesterov et Nemirovskii [455 ; 1993], peut être vue comme une généralisation des méthodes de points intérieurs que nous verrons sous des formes un peu différentes dans les cas particuliers de l’optimisation linéaire (chapitre 18) et de l’optimisation semi-définie positive (chapitre 20). Chronologiquement, elle a été construite après la découverte de ces dernières, dans un but évident de généralisation et d’extension de son domaine d’application. C’est aussi pour cette raison que nous la présentons dans cette partie décrivant les méthodes générales de l’optimisation avec contraintes. Le lecteur pourra d’ailleurs étudier les chapitres 18 et 20, avant d’aborder cette section, mais rien n’impose un tel ordre de lecture. Cette théorie est remarquable, puisqu’elle conduit au résultat impressionnant selon lequel tout problème d’optimisation convexe, écrit sous la forme ci-dessus, peut être résolu avec une précision arbitraire donnée en un nombre polynomial d’itérations ne dépendant de la précision demandée que par son logarithme. La dépendance polynomiale ne se fait pas directement par rapport à la dimension de E, car la structure de l’ensemble admissible X intervient également, mais par l’intermédiaire d’un module de complexité ϑf , dont la dépendance par rapport à dim E pourra parfois être explicitée. Cela paraît très attrayant. Il faut toutefois que l’on dispose d’une barrière autoconcordante f dont le domaine est l’intérieur de l’ensemble admissible X pour que ce résultat ait lieu. Même si l’on peut montrer qu’une telle fonction existe toujours, on ne dispose pas nécessairement d’une forme analytique de celle-ci, si bien que le résultat peut ne pas avoir une utilité pratique immédiate. On connaît cependant de grandes classes de problèmes auxquelles sont associées des fonctions autoconcordantes : l’optimisation linéaire (chapitre 18) et l’optimisation SDP (chapitre 20). Mais on connait aussi des problèmes convexes qui sont NP-ardus, les problèmes d’optimisation copositive [69 ; 2012] ; donc pour lesquels l’évaluation d’une barrière auto-concoirdante ne pourra se faire en temps polynomial que si P = NP. Nous introduisons d’abord, à la section 16.1.2, la notion de fonction auto-concordante et en donnons les propriétés utiles à l’étude des algorithmes décrits. Nous présentons ensuite, à la section 16.1.3, les barrières autoconcordantes, qui sont des fonctions autoconcordantes pour lesquelles la direction de Newton est bornée (pour une métrique particulière). Ce sont ces fonctions qui permettent d’obtenir des résultats de complexité itérative polynomiale des méthodes de points intérieurs. Nous concluons la section par trois algorithmes typiques et en démontrons leur complexité polynomiale (section 16.1.4). On peut accéder à l’étude d’un algorithme polynomialement convergent avec un minimum d’effort préalable : il suffit de définir les notions de fonction autoconcordante (définition 16.1 et définitions équivalentes de la proposition 16.5) et de barrière autoconcordante (définition 16.18), d’étudier les propositions 16.8 et 16.11 et d’établir l’inégalité de droite dans (16.15) et celle de la proposition 16.28; on a alors toute l’information nécessaire à la compréhension et à l’analyse du premier algorithme présenté à la section 16.1.4. La seconde partie de ce chapitre s’intéresse au cas des problèmes non linéaires et non convexes. Il n’y a alors plus de résultat de complexité polynomiale. Après avoir présenté un schéma algorithmique parfois implémenté, nous en étudions le comportement asymptotique. 

Fonction autoconcordante

 On verra aux chapitres 18 et 20, que la fonction logarithmique joue un rôle important dans la conception des algorithmes de points intérieurs et dans l’étude de leur convergence polynomiale. Les fonctions autoconcordantes sont celles qui ont les propriétés du logarithme qui y jouent un rôle-clé, avec l’intérêt supplémentaire de pouvoir être définie sur des ouverts convexes plus généraux que l’intérieur de l’orthant positif (exemple 16.2) ou du cône des matrices semi-définies positives (exemple 16.3). Les fonctions autoconcordantes f : E → R ∪ {+∞}, dont l’adhérence du domaine définira l’ensemble admissible de (P), devront au moins vérifier les propriétés suivantes :    dom f est un ouvert convexe non vide, f est C 2 sur son domaine et ∇2f(x) ≻ 0 pour tout x ∈ dom f. Évidemment, de telles fonctions sont strictement convexes. On note g(x) := ∇f(x) et H(x) := ∇2 f(x) le gradient et hessienne de f en x ∈ dom f pour le produit scalaire de référence. 

Fonction autoconcordante 

Définition 16.1 On dit qu’une fonction f : E → R ∪ {+∞} est autoconcordante, si elle vérifie les conditions (16.2) et si les deux propriétés suivantes ont lieu : (AC1) ∀x ∈ dom f, Bx(x, 1) ⊆ dom f, (AC2) ∀x ∈ dom f, ∀y ∈ Bx(x, 1), ∀v ∈ E \ {0}, on a 1 − ky − xkx 6 kvky kvkx 6 1 1 − ky − xkx . (16.4) On note AC(E) l’ensemble des fonctions autoconcordantes sur E. ✷ Les inégalités (16.4) sont remarquables si on les compare à (16.3) : aucune constante indéterminée n’est utilisée et le voisinage Bx(x, 1) sur lequel elles ont lieu est bien précisé. Cette absence de constante inconnue est une caractéristique que l’on s’attachera à préserver dans toutes les propriétés des fonctions autoconcordantes et qui contribuera à l’obtention des résultats de polynomialité. La condition (AC1) donne à une fonction autoconcordante f une allure proche de la frontière de son domaine qui rappelle celle de l’opposé du logarithme au voisinage de 0 (proposition 16.4). En particulier, f(x) tend vers +∞ lorsque x tend vers un point de ∂(dom f). La condition (AC2) exprime à sa manière le caractère lipschitzien de la hessienne de f (proposition 16.5). Cette propriété permet en particulier de comparer deux directions de Newton successives (proposition 16.11), ce qui sera important dans le contrôle des itérés dans les méthodes de points intérieurs. Les fonctions autoconcordantes existent ! En voici deux exemples emblématiques, qui seront respectivement utilisées en optimisation linéaire (chapitre 18) et en optimisation semi-définie positive (chapitre 20). Le logarithme y joue un rôle important. On peut d’ailleurs voir l’autoconcordante comme un moyen d’introduire sur un ensemble convexe quelconque une fonction ayant les propriétés particulières de l’opposé du logarithme sur R++, qui sont décisives pour l’obtention des résultats de polynomialité.