Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Méthode de l'ellipsoïde
Résumé
En optimisation mathématique, la méthode de l'ellipsoïde est une méthode itérative utilisée pour minimiser des fonctions convexes. En informatique théorique, cette méthode est connue comme étant le premier algorithme de complexité polynomiale découvert pour résoudre les problèmes d'optimisation linéaire.
L'algorithme construit une suite d'ellipsoïdes de plus en plus petits, qui enserrent à chaque étape le minimum de la fonction objectif.
Depuis son invention par George Dantzig en 1947, la méthode du simplexe avait relégué un certain nombre d'heuristiques antérieures pour résoudre les problèmes d'affectation sous contraintes linéaires, en particulier les itérations transposant le problème à une compétition entre deux joueurs. Tout au long des années 1950 et 1960, elle fut appliquée à des problèmes de taille de plus en plus grande jusqu'à ce qu'au début des années 1970, Victor Klee et mettent en évidence l'existence de programmes pour lesquels l'algorithme de Dantzig conduit à examiner un nombre de pivots croissant exponentiellement avec la taille du problème.
La méthode des ellipsoïdes est une technique itérative d'optimisation qui avait été imaginée par David Youdine, Arcadi Nemirovski et, indépendamment, Nahum Chor (1976–77) ; un mathématicien arménien, Khatchian, tenta de l'utiliser pour résoudre les programmes linéaires mais cela n'allait nullement de soi : l'algorithme exigeait le calcul d'une estimation de la distance à l'optimum ; pour cela, Khatchian établit un certain nombre de majorations sur les volumes de polyèdres, et analysa la précision de calcul requise pour que la méthode soit praticable. Il publia ces résultats sans les démonstrations dans une note de quatre pages des Soviet Mathematics Doklady (). L'algorithme vint à la connaissance des chercheurs occidentaux lors d'une conférence au Symposium de programmation mathématique de Montréal, au mois d', puis grâce à un article de Peter Gács et László Lovász, qui évitait les changements continuels de systèmes de coordonnées familiers aux mathématiciens russes.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.