Klee–Minty cube
The Klee–Minty cube or Klee–Minty polytope (named after
In particular, many optimization
Description
The Klee–Minty cube was originally specified with a parameterized system of linear inequalities, with the dimension as the parameter. The cube in two-dimensional space is a squashed square, and the "cube" in three-dimensional space is a squashed cube. Illustrations of the "cube" have appeared besides algebraic descriptions.[3] The Klee–Minty polytope is given by:[4]
This has variables, constraints other than the non-negativity constraints, and vertices, just as a -dimensional hypercube does. If the objective function to be maximized is
Computational complexity
The Klee–Minty cube has been used to analyze the performance of many algorithms, both in the worst case and on average. The
Worst case
In mathematical optimization, the Klee–Minty cube is an example that shows the
. Klee and Minty showed that Dantzig's simplex algorithm visits all corners of a (perturbed) cube in dimension in the worst case.[5]Modifications of the Klee–Minty construction showed similar exponential time complexity for other pivoting rules of simplex type, which maintain primal feasibility, such as Bland's rule.[6] Another modification showed that the criss-cross algorithm, which does not maintain primal feasibility, also visits all the corners of a modified Klee–Minty cube.[7] Like the simplex algorithm, the criss-cross algorithm visits all 8 corners of the three-dimensional cube in the worst case.
Path-following algorithms
Further modifications of the Klee–Minty cube have shown the poor performance of central-path–following algorithms for linear optimization, in that the central path comes arbitrarily close to each of the corners of a cube. This "vertex-stalking" performance is surprising because such path-following algorithms have polynomial-time complexity for linear optimization.[8]
Average case
The Klee–Minty cube has also inspired research on
See also
- Projective algorithm of Karmarkar
- Ellipsoidal algorithm of Khachiyan
References
Notes
- ^ More generally, for the simplex algorithm, the expected number of steps is proportional to for linear-programming problems that are randomly drawn from the
Citations
- ^ Klee & Minty (1972).
- ^ Deza, Nematollahi & Terlaky (2008).
- ^
- ^ Greenberg (1997).
- ^
- Klee & Minty (1972)
- Murty (1983), 14.2 Worst-case computational complexity, pp. 434–437
- Terlaky & Zhang (1993)
- ^
- Bland (1977) Murty (1983), Chapter 10.5, pp. 331–333; problem 14.8, p. 439 describes Bland's rule.
- Murty (1983), Problem 14.3, p. 438; problem 14.8, p. 439 describes the worst-case complexity of Bland's rule.
- ^
- ^
- ^ Gartner & Ziegler (1994).
- ^ Borgwardt (1987).
- ^
- Fukuda & Namiki (1994), p. 367
- Fukuda & Terlaky (1997), p. 385
Bibliography
- Bland, Robert G. (May 1977). "New finite pivoting rules for the simplex method". MR 0459599.
- Borgwardt, Karl-Heinz (1987). The simplex method: A probabilistic analysis. Algorithms and Combinatorics (Study and Research Texts). Vol. 1. Berlin: Springer-Verlag. MR 0868467.
- Deza, Antoine; Nematollahi, Eissa; Terlaky, Tamás (May 2008). "How good are interior point methods? Klee–Minty cubes tighten iteration-complexity bounds" (PDF). Mathematical Programming. 113 (1): 1–14. S2CID 156325.
- S2CID 21476636.
- Greenberg, Harvey J. (1997). "Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method" (PDF). University of Colorado at Denver.
- S2CID 2794181. Postscript preprint.
- Gartner, B.; S2CID 8090478.
- MR 0332165.
- MR 0984561.
- MR 0720547.
- Roos, C. (1990). "An exponential example for Terlaky's pivoting rule for the criss-cross simplex method". Mathematical Programming. Series A. 46 (1): 79–84. S2CID 33463483.
- Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot rules for linear programming: A Survey on recent theoretical developments". Annals of Operations Research. 46 (Degeneracy in optimization problems, number 1): 203–233. S2CID 6058077.
External links
Algebraic description with illustration
The first two links have both an algebraic construction and a picture of a three-dimensional Klee–Minty cube:
- Deza, Antoine; Nematollahi, Eissa; Terlaky, Tamás (May 2008). "How good are interior point methods? Klee–Minty cubes tighten iteration-complexity bounds" (PDF). Mathematical Programming. 113 (1): 1–14. S2CID 156325.
- Gartner, B.; S2CID 8090478. IEEE mis-spells the name "Gärnter" as "Gartner" (sic.).
Pictures with no linear system
- Articles of E. Nematollahi, which discuss the Klee-Minty cube with illustrations.
- A picture of a Klee-Minty cube showing a simplex-algorithm path (automatic translation of German) by Günter Ziegler. The picture in the second half of the page.