ETUDE DES MÉTHODES DE POINT INTÉRIEUR APPLIQUÉES 
À LA PROGRAMMATION LINÉAIRE ET À LA PROGRAMMATION SEMIDÉFINIE

La programmation mathématique, branche de l’optimisation, s’occupe de la 
minimisation sous contraintes d’une fonction à plusieurs variables, schéma 
très général s’appliquant à de nombreuses situations pratiques dans 
beaucoup de domaines (minimisation de coûts, de durées, etc.).

Dans le cas d'une fonction et de contraintes linéaires (programmation 
linéaire), on dispose d'une méthode efficace de résolution : l'algorithme 
du simplexe, découvert par Dantzig en 1947. Cet algorithme a connu depuis 
de nombreuses améliorations, et est utilisé dans la majorité des logiciels 
commerciaux. Cependant, un nouveau type de méthodes de résolution a fait 
son apparition en 1984 : les méthodes de point intérieur. Depuis, un très
 important courant de recherches s'est orienté dans cette voie.

L’objectif de ce travail de fin d’études est de donner un aperçu de ce 
domaine relativement récent, en fournissant une description claire et 
compréhensible de ces méthodes, tant du point de vue théorique que de celui 
de leur implémentation sur ordinateur et de leurs performances pratiques. 
Nous nous attacherons dans un premier temps à l’examen du cas linéaire, le 
plus étudié et le plus utilisé, avant de nous concentrer sur un cas 
particulier important de la programmation non-linéaire, la programmation 
semidéfinie, possédant de nombreuses applications. Enfin, nous terminerons 
en décrivant une implémentation sur ordinateur, réalisée dans le cadre de 
ce travail de fin d’études, utilisant les méthodes de point intérieur 
appliquées à la programmation semidéfinie pour résoudre un problème de 
classification de données (analyse discriminante par ellipsoïdes).

Les conclusions que nous tirons de ce travail sont les suivantes :

- Les méthodes de point intérieur pour la programmation linéaire sont 
arrivées à une certaine maturité. Elles jouissent d’une supériorité 
théorique (complexité polynomiale) et pratique (pour les problèmes de 
grande taille) par rapport à l’algorithme du simplexe.

- Ces méthodes ont de plus l’avantage d’être relativement aisément 
adaptables à la programmation non-linéaire. En particulier, l’application 
de ces méthodes à la programmation semidéfinie nous semble très prometteuse 
de par le nombre important d’applications existantes.

- Enfin, notre implémentation d’un algorithme de classification par 
ellipsoïdes, qui fait partie de ces applications, s’est révélée très 
efficace puisqu’elle a correctement classé l’ensemble des "Iris de Fisher", 
problème standard servant de référence dans le domaine de l’analyse 
discriminante.