Condition numbers for polyhedra with real number data

The authors consider the complexity of finding a feasible point inside a polyhedron specified by homogeneous linear constraints. A primal-dual interior point method is used. The running time of the interior point method can be bounded in terms of a condition number of the coefficient matrix A that has been proposed by Ye. The authors demonstrate that Ye’s condition number is bounded in terms of another condition number for weighted least squares discovered by Stewart and Todd. Thus, the Stewart-Todd condition number, which is defined for real-number data, also bounds the complexity of finding a feasible point in a polyhedron.