CONDITION NUMBERS FOR POLYHEDRA WITH REAL NUMBER DATA

We consider the complexity of finding a feasible point inside a polyhe dron specified by homogeneous linear constraints. A primal-dual interi or point method is used. The running time of the interior point method can be bounded in terms of a condition number of the coefficient matr ix A that has been proposed by Ye. We demonstrate that Ye's condition number is bounded in terms of another condition number for weighted le ast squares discovered by Stewart and Todd, Thus, the Stewart-Todd con dition number, which is defined for real-number data, also bounds the complexity of finding a feasible point in a polyhedron.