Ê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
Algorithme de Karmarkar
Résumé
L’algorithme de Karmarkar est un algorithme introduit par Narendra Karmarkar en 1984 pour résoudre les problèmes d'optimisation linéaire. C'est le premier algorithme réellement efficace qui résout ces problèmes en un temps polynomial. La méthode de l'ellipsoïde fonctionne aussi en temps polynomial mais est inefficace en pratique.
En posant le nombre de variables et le nombre de bits d'entrée de l'algorithme, l'algorithme de Karmarkar réalise opérations sur bits à comparer aux opérations pour la méthode des ellipsoïdes. Le temps d'exécution de l'algorithme de Karmarkar est ainsi en utilisant l'algorithme de Schönhage-Strassen (voir Comparaison asymptotique).
L'algorithme de Karmarkar est une méthode du point intérieur : la solution candidate courante ne suit pas les bornes de l'espace faisable comme dans l'algorithme du simplexe, mais approche par l'intérieur de l'espace faisable et atteint la solution optimale de manière asymptotique.
Soit le problème d'optimisation linéaire sous forme matricielle suivant :
L'algorithme de Karmarkar est complexe. Une version simplifiée, appelée "affine scaling method", est succinctement décrite ci-dessous. Il faut noter que cet algorithme, bien qu'efficace en pratique, ne tourne pas en temps polynomial.
Entrées : A, b, c, , critère d'arrêt, .
do while critère d'arrêt non satisfait
if then
return non bornée
end if
end do
Considérons le problème d'optimisation linéaire suivant :
Il y a deux variables et onze contraintes associées à différentes valeurs de . La figure montre chaque itération de l'algorithme avec des points rouge. Les contraintes sont représentées par des lignes bleues.
Au moment où il a découvert l'algorithme, Narenda Karmarkar était employé par AT&T. Comme la découverte pouvait avoir d'importantes applications, AT&T dépose un brevet pour l'algorithme de Karmarkar en , ce qui a alimenté la controverse au sujet de la brevetabilité du logiciel.
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.