A Simpler and Tighter Redundant Klee-Minty Construction
Eissa Nematollahi (nematoemcmaster.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
Entry Submitted: 10/19/2006
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|