Programmation Linaire, Complexit

Le but de cet ouvrage est de faire une prsentation complte et auto contenue de l'quivalence entre les Oracles Sparer, Optimiser et Appartenir en Optimisation Polydrale. Dans ce but le livre commence par une prsentation dtaille des problmes de Complexit des Algorithmes suivi d'une prsentation de la mthode du Simplexe. On dcrit ensuite l'algorithme de Khachiyan sans luder les problmes numriques. Viennent alors une suite d'algorithmes polynomiaux pour Optimiser partir de l'oracle Sparer. Aprs quelques transformations, on montre que, par polarit, on peut Sparer partir de l'oracle Optimiser. La premire quivalence est revue aprs avoir dcrit l'algorithme LLL. L'ouvrage se termine par la rduction de Sparer Appartenir.