A Redundant Klee-Minty Construction with All the Redundant Constraints Touching the Feasible Region
Abstract: By introducing some redundant Klee-Minty constructions, we have previously shown that the central path may visit every vertex of the Klee-Minty cube having $2^n-2$ ``sharp'' turns in dimension $n$. In all of the previous constructions, the maximum of the distances of the redundant constraints to the corresponding facets is an exponential number of the dimension $n$, and those distances are decaying geometrically. In this paper, we provide a new construction in which all of the distances are set to zero, i.e., all of the redundant constraints touch the feasible region.
Keywords: Linear optimization, Klee-Minty cube, interior point methods, redundant, central path.
Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )
Citation: McMaster University, January 2008.
Entry Submitted: 01/05/2008
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|