Optimization Online


A Redundant Klee-Minty Construction with All the Redundant Constraints Touching the Feasible Region

Eissa Nematollahi(nematoe***at***mcmaster.ca)
Tamas Terlaky(terlaky***at***mcmaster.ca)

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.

Download: [PDF]

Entry Submitted: 01/05/2008
Entry Accepted: 01/05/2008
Entry Last Modified: 01/05/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society