On the condition numbers for polyhedra in Karmarkar's form

Levent Tuncel

We present formulations of two condition measures (one for linear programming (LP) due to Ye, and the other for a matrix) as optimization problems over sign constraints. We construct, based on LP duality, a dual characterization of Ye's condition measure in the setting of Karmarkar's form. The elementary formulations (without utilizing the dual characterization) lead to trivial proofs of some results relating these two condition measures for polyhedra in Karmarkar's form. Such interpretations, using the sign constraints, allow for the definition of families of condition measures that are ``between'' the two condition measures. Our viewpoint provides further understanding of the relationship of the two condition measures. As a result of this new understanding, we point to a connection with oriented matroids and prove that a conjecture of Vavasis and Ye on the relationship of these two condition measures is false.

Research Report CORR 97-24, November 1997.

Contact: ltuncel@math.uwaterloo.ca