Cube Klee–Menthe - Klee–Minty cube

Cube Klee Minty pour la méthode simplex du sommet de l'ombre.

Le cube Klee-Minty ou Klee-Minty polytope ( du nom de Victor Klee et George J. Minty ) est une unité hypercube de la variable dimension dont les coins ont été perturbés. Klee et Minty démontré que George Danzig d » algorithme simplex a de mauvaises performances pire des cas il est initialisé à un coin de leur « cube aplaties ». Sur la version tridimensionnelle, l' algorithme simplex et l' algorithme entrecroisé visitent les 8 coins dans le pire des cas.

En particulier, de nombreux algorithmes d' optimisation pour l'optimisation linéaire présentent des performances médiocres lorsqu'ils sont appliqués au cube Klee-Minty. En 1973, Klee et Minty ont montré que l' algorithme du simplexe de Dantzig n'était pas un algorithme en temps polynomial lorsqu'il était appliqué à leur cube. Par la suite, des modifications du cube Klee-Minty ont montré un mauvais comportement à la fois pour d' autres bases - échange des algorithmes de pivotement et aussi pour les algorithmes de points intérieurs.

Description du cube

Le cube Klee-Minty a été initialement spécifié avec un système paramétré d'inégalités linéaires, avec la dimension comme paramètre. Lorsque la dimension est de deux, le "cube" est un carré écrasé. Lorsque la dimension est de trois, le "cube" est un cube écrasé. Des illustrations du "cube" sont apparues à côté des descriptions algébriques.

Le polytope de Klee-Minty est donné par

${\displaystyle {\begin{aligned}x_{1}\leq 5\\4x_{1}+x_{2}\leq 25\\8x_{1}+4x_{2}+x_{3}\leq 125\ \\vdots \\2^{D}x_{1}+2^{D-1}x_{2}+\dots +4x_{D-1}+x_{D}\leq 5^{D}\\ x_{1}\geq 0,\,\,\dots ,\,\,x_{D}\geq 0.\end{aligned}}}$

Cela a D variables, D contraintes autres que les D contraintes de non-négativité, et 2 ^D sommets, tout comme un D -dimensionnelle hypercube fait. Si la fonction objectif à maximiser est

${\displaystyle 2^{D-1}x_{1}+2^{D-2}x_{2}+\dots +2x_{D-1}+x_{D},}$

et si le sommet initial de l'algorithme du simplexe est l'origine, alors l'algorithme tel que formulé par Dantzig visite tous les sommets ^2D , atteignant finalement le sommet optimal${\displaystyle (0,0,\dots ,5^{D}).}$

Complexité de calcul

Le cube Klee-Minty a été utilisé pour analyser les performances de nombreux algorithmes, à la fois dans le pire des cas et en moyenne. La complexité temporelle d'un algorithme compte le nombre d' opérations arithmétiques suffisant pour que l'algorithme résolve le problème. Par exemple, l'élimination gaussienne nécessite de l' ordre de  D ³ opérations, et on dit donc qu'elle a une complexité polynomiale en temps, car sa complexité est limitée par un polynôme cubique . Il existe des exemples d'algorithmes qui n'ont pas de complexité en temps polynomial. Par exemple, une généralisation de l'élimination de Gauss appelée algorithme de Buchberger a pour sa complexité une fonction exponentielle des données du problème (le degré des polynômes et le nombre de variables des polynômes multivariés ). Étant donné que les fonctions exponentielles finissent par croître beaucoup plus rapidement que les fonctions polynomiales, une complexité exponentielle implique qu'un algorithme a des performances lentes sur de gros problèmes.

Pire cas

Une illustration d'un polytope tridimensionnel qui est la région réalisable pour un problème de programmation linéaire. L'algorithme du simplexe traverse les arêtes entre les sommets jusqu'à ce qu'il atteigne un sommet optimal. Dans le cas illustré, l'algorithme du simplexe prend cinq étapes. Cependant, l'algorithme du simplexe visite chaque sommet dans le pire des cas d'un problème dont la région réalisable est le cube de Klee-Minty, de sorte que le nombre d'étapes augmente de façon exponentielle avec la dimension du problème.

En optimisation mathématique, le cube Klee-Minty est un exemple qui montre la complexité de calcul dans le pire des cas de nombreux algorithmes d' optimisation linéaire . C'est un cube déformé avec exactement 2  coins ^D de dimension D . Klee et Minty ont montré que l' algorithme du simplexe de Dantzig visite tous les coins d'un cube (perturbé) en dimension  D dans le pire des cas .  

Les modifications de la construction de Klee-Minty ont montré une complexité temporelle exponentielle similaire pour d'autres règles pivotantes de type simplexe, qui maintiennent la faisabilité primale, comme la règle de Bland . Une autre modification a montré que l' algorithme d'entrecroisement , qui ne maintient pas la faisabilité primale, visite également tous les coins d'un cube de Klee-Minty modifié. Comme l'algorithme simplex, l'algorithme entrecroisé visite les 8 coins du cube tridimensionnel dans le pire des cas.

Algorithmes de suivi de chemin

D'autres modifications du cube Klee-Minty ont montré de mauvaises performances des algorithmes de suivi du chemin central pour l'optimisation linéaire, en ce sens que le chemin central se rapproche arbitrairement de chacun des coins d'un cube. Cette performance de "vertex-stalking" est surprenante, car de tels algorithmes de suivi de chemin ont une complexité en temps polynomial pour l'optimisation linéaire.

Cas moyen

Le cube de Klee-Minty a également inspiré des recherches sur la complexité des cas moyens . Lorsque les pivots éligibles sont effectués au hasard (et non par la règle de la descente la plus raide), l'algorithme du simplexe de Dantzig nécessite en moyenne un nombre quadratique de pas ( de l'ordre de O( D ² ). Les variantes standard de l'algorithme du simplexe prennent en moyenne  D pas pour un cube. Lorsqu'il est initialisé à un coin aléatoire du cube, l'algorithme d'entrecroisement ne visite que  D coins supplémentaires, cependant, selon un article de Fukuda et Namiki de 1994. L'algorithme du simplexe et l'algorithme d'entrecroisement visitent exactement 3 coins supplémentaires du cube tridimensionnel en moyenne.

Voir également

• Algorithme projectif de Karmarkar
• Algorithme ellipsoïdal de Khachiyan

Remarques

Les références

• Deza, Antoine ; Nematollahi, Eissa ; Terlaky, Tamás (mai 2008). "Quelle est la qualité des méthodes de point intérieur? Les cubes Klee-Minty resserrent les limites de complexité d'itération" (PDF) . Programmation mathématique . 113 (1) : 1-14. CiteSeerX  10.1.1.214.111 . doi : 10.1007/s10107-006-0044-x . MR  2367063 .
• Fukuda, Komei ; Namiki, Makoto (mars 1994). « Sur les comportements extrêmes de la méthode du moindre indice de Murty ». Programmation mathématique . 64 (1) : 365-370. doi : 10.1007/BF01582581 . MR  1286455 .
• Fukuda, Komei ; Terlaky, Tamas (1997). Thomas M. Liebling ; Dominique de Werra (dir.). « Méthodes croisées : un regard neuf sur les algorithmes de pivot ». Programmation mathématique, série B . 79 (Articles du 16e Symposium international sur la programmation mathématique tenu à Lausanne, 1997) : 369-395. CiteSeerX  10.1.1.36.9373 . doi : 10.1007/BF02614325 . MR  1464775 . Préimpression post-scriptum .
• Gartner, B. ; Ziegler, GM (1994). Algorithmes du simplexe randomisés sur cubes Klee-Minty . Foundations of Computer Science, Symposium annuel de l'IEEE sur . IEEE. p. 502-510. CiteSeerX  10.1.1.24.1405 . doi : 10.1109/SFCS.1994.365741 . ISBN 978-0-8186-6580-6.
• Klee, Victor ; Minty, George J. (1972). "Quelle est la qualité de l'algorithme du simplexe ?". Dans Shisha, Oved (éd.). Inégalités III (Actes du troisième symposium sur les inégalités tenu à l'Université de Californie, Los Angeles, Californie, du 1er au 9 septembre 1969, dédié à la mémoire de Theodore S. Motzkin) . New York-Londres : Academic Press. p. 159–175. MR  0332165 .
• Megiddo, Nemrod ; Shub, Michael (février 1989). "Comportement aux limites des algorithmes de points intérieurs dans la programmation linéaire". Mathématiques de la recherche opérationnelle . 14 (1) : 97-146. CiteSeerX  10.1.1.80.184 . doi : 10.1287/moor.14.1.97 . JSTOR  3689840 . MR  0984561 .
• Murty, Katta G. (1983). Programmation linéaire . New York : John Wiley & Fils. p. XIX+482. ISBN 978-0-471-09725-9. MR  0720547 .
• Roos, C. (1990). « Un exemple exponentiel pour la règle de pivotement de Terlaky pour la méthode simplex entrecroisée ». Programmation mathématique . Série A. 46 (1) : 79-84. doi : 10.1007/BF01585729 . MR  1045573 .
• Terlaky, Tamas ; Zhang, Shu Zhong (1993). « Règles de pivot pour la programmation linéaire : Une enquête sur les développements théoriques récents ». Annales de recherche opérationnelle . 46 (Dégénérescence dans les problèmes d'optimisation, numéro 1) : 203-233. CiteSeerX  10.1.1.36.7658 . doi : 10.1007/BF02096264 . ISSN  0254-5330 . MR  1260019 .

Liens externes

Description algébrique avec illustration

Les deux premiers liens ont à la fois une construction algébrique et une image d'un cube de Klee-Minty en trois dimensions :

• Deza, Antoine ; Nematollahi, Eissa ; Terlaky, Tamás (mai 2008). "Quelle est la qualité des méthodes de point intérieur? Les cubes Klee-Minty resserrent les limites de complexité d'itération" (PDF) . Programmation mathématique . 113 (1) : 1-14. CiteSeerX  10.1.1.214.111 . doi : 10.1007/s10107-006-0044-x . MR  2367063 .
• Gartner, B. ; Ziegler, GM (1994). Algorithmes du simplexe randomisés sur cubes Klee-Minty . Foundations of Computer Science, Symposium annuel de l'IEEE sur . IEEE. p. 502-510. CiteSeerX  10.1.1.24.1405 . doi : 10.1109/SFCS.1994.365741 . ISBN 978-0-8186-6580-6. IEEE orthographie mal le nom "Gärnter" comme "Gartner" (sic.).

Images sans système linéaire

• Articles de E. Nematollahi, qui traitent du cube Klee-Minty avec des illustrations.
• Une image d'un cube de Klee-Minty montrant un chemin d'algorithme simplex (traduction automatique de l' allemand ) par Günter Ziegler . L'image dans la seconde moitié de la page.