Méthodes de points intérieurs

On commence par introduire une nouvelle classe de fonction, dépendant d’un paramètre µ : ${\displaystyle f_{\mu }(x)=c^{T}x+\mu \times \sum _{i=1}^{m}\ln(b_{i}-a_{i}x)}$. On remarque que, quand ${\displaystyle \mu =0}$, on retrouve la fonction objectif de départ : ${\displaystyle f_{0}=f}$. La partie suivant de µ dans la formule est appelée fonction barrière. Son rôle est de réduire la valeur de ${\displaystyle f_{\mu }}$ près des frontières, pour éviter de trop s’en rapprocher[1].

L’idée générale de cette méthode est assez simple. On commence par choisir une valeur de µ suffisamment grande, un point de départ à l’intérieur des solutions possibles (en général intelligemment choisi, c’est-à-dire pas trop loin du maximum de ${\displaystyle f_{\mu }}$), et on va ensuite procéder par petits pas[10] :

• On réduit légèrement la valeur de µ
• On trouve une nouvelle approximation du max de ${\displaystyle f_{\mu }}$. Cette nouvelle approximation peut se faire efficacement en partant de principe que le nouveau maximum reste proche du point de départ
• On répète cette opération jusqu’à ce que µ soit suffisamment petit.