Klee–Minty cube explained

The Klee–Minty cube or Klee–Minty polytope (named after Victor Klee and George J. Minty) is a unit hypercube of variable dimension whose corners have been perturbed. Klee and Minty demonstrated that George Dantzig's simplex algorithm has poor worst-case performance when initialized at one corner of their "squashed cube". On the three-dimensional version, the simplex algorithm and the criss-cross algorithm visit all 8 corners in the worst case.

In particular, many optimization algorithms for linear optimization exhibit poor performance when applied to the Klee–Minty cube. In 1973 Klee and Minty showed that Dantzig's simplex algorithm was not a polynomial-time algorithm when applied to their cube. Later, modifications of the Klee–Minty cube have shown poor behavior both for other basis-exchange pivoting algorithms and also for interior-point algorithms.

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. The Klee–Minty polytope is given by:\begin x_1 &\le 5 \\4x_1 + x_2 &\le 25 \\8x_1 + 4x_2 + x_3 &\le 125 \\ &\vdots \\2^Dx_1 + 2^x_2 + \dots + 4x_ + x_D &\le 5^D \\x_1 \ge 0, \, \, \dots, \, \, x_D &\ge 0.\end

This has

D

variables,

D

constraints other than the

D

non-negativity constraints, and

2D

vertices, just as a dimensional hypercube does. If the objective function to be maximized is 2^x_1+2^x_2+ \dots + 2x_+x_D, and if the initial vertex for the simplex algorithm is the origin, then the algorithm as formulated by Dantzig visits all

2D

vertices, finally reaching the optimal vertex

(0,0,...,5D)

.

Computational complexity

D3

operations, and so it is said to have polynomial time-complexity because its complexity is bounded by a cubic polynomial. There are examples of algorithms that do not have polynomial-time complexity. For example, a generalization of Gaussian elimination called Buchberger's algorithm has for its complexity an exponential function of the problem data (the degree of the polynomials and the number of variables of the multivariate polynomials). Because exponential functions eventually grow much faster than polynomial functions, an exponential complexity implies that an algorithm has slow performance on large problems.

Worst case

D

. Klee and Minty showed that Dantzig's simplex algorithm visits all corners of a (perturbed) cube in dimension

D

in the worst case.

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. 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. 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.

Average case

O(D2)

. Standard variants of the simplex algorithm take on average

D

steps for a cube. However according to, when it is initialized at a random corner of the cube, the criss-cross algorithm visits only

D

additional corners. Both the simplex algorithm and the criss-cross algorithm visit exactly 3 additional corners of the three-dimensional cube on average.

See also

References

Bibliography

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:

Pictures with no linear system

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Klee–Minty cube".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.