How partial knowledge helps to solve linear programs

Yinyu Ye

We present results on how partial knowledge helps to solve linear programs. In particular, if a linear inequality system, $A\x=\b$ and $\x\ge 0$, is known to have an interior feasible point, then we show that finding a feasible point to this system can be done in $O(n^{2.5}c(A))$ iterations by the layered interior-point method, and each iteration solves a least-squares problem, where $n$ is the dimension of vector $\x$ and $c(A)$ is the condition number of matrix $A$ defined in \cite{VavasisYe}. This complexity bound is reduced by a factor $n$ from that when no such knowledge exists.