Improved Complexity Results on Solving Real-Number Linear Feasibility Problems

Yinyu Ye
Department of Management Science and Engineering
Stanford University
Stanford, CA

We present complexity results on solving real-number standard linear programs LP(A, b, c), where the constraint matrix A 0 Umn , the right-hand-side vector b 0 Um and the objective coefficient vector c 0 Un are real. In particular, we present a two-layered interior-point method and show that LP(A, b, 0), i.e., the linear feasibility problem Ax = b and x $0, can be solved in in O(n2.5 c(A)) interior-point method iterations. Here z is the vector of all zeros and c(A) is the condition measure of matrix A defined by Vavasis and Ye [1]. This complexity iteration bound is reduced by a factor n from that for general LP(A, b, c) comparing the results of Vavasis and Ye [1]. We also prove that the iteration bound will be further reduced to O(n1.5 c(A)) for LP(A, 0, 0), i.e., for the homogeneous linear feasibility problem.

[1] S.A. Vavasis and Y. Ye, A Primal-Dual Interior Point Method Whose Running Time Depends Only on the Constraint Matrix, Mathematical Programming, 74, (1996) 79-120.