A Simpler and Tighter Redundant Klee-Minty Construction

Eissa Nematollahi (nematoemcmaster.ca)
Tamas Terlaky (terlakymcmaster.ca)

Abstract: By introducing redundant Klee-Minty examples, we have previously shown that the central path can be bent along the edges of the Klee-Minty cubes, thus having $2^n-2$ sharp turns in dimension $n$. In those constructions the redundant hyperplanes were placed parallel with the facets active at the optimal solution. In this paper we present a simpler and more powerful construction, where the redundant constraints are parallel with the coordinate-planes. An important consequence of this new construction is that one of the sets of redundant hyperplanes is touching the feasible region, and $N$, the total number of the redundant hyperplanes is reduced by a factor of $n^2$, further tightening the gap between iteration-complexity upper and lower bounds.

Keywords: Linear programming, Klee-Minty example, interior point methods, worst-case iteration complexity, central path.

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Report Number: AdvOL2006/12, Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada

Download: [PDF]

Entry Submitted: 10/19/2006
Entry Accepted: 10/19/2006
Entry Last Modified: 10/19/2006

Modify/Update this entry