  The ellipsoid algorithm is a fundamental algorithm for computing a solution
to the system of $m$ linear inequalities in $n$ variables $(P): A^{\top}x \le
u$ when its set of solutions has positive volume. However, when $(P)$ is
infeasible, the ellipsoid algorithm has no mechanism for proving that $(P)$ is
infeasible. This is in contrast to the other two fundamental algorithms for
tackling $(P)$, namely the simplex method and interior-point methods, each of
which can be easily implemented in a way that either produces a solution of
$(P)$ or proves that $(P)$ is infeasible by producing a solution to the
alternative system $\mathrm{({\it Alt})}: A\lambda= 0$, $u^{\top}\lambda < 0$,
$\lambda \ge 0$. This paper develops an Oblivious Ellipsoid Algorithm (OEA)
that either produces a solution of $(P)$ or produces a solution of
$\mathrm{({\it Alt})}$. Depending on the dimensions and on other natural
condition measures, the computational complexity of the basic OEA may be worse
than, the same as, or better than that of the standard ellipsoid algorithm. We
also present two modified versions of OEA, whose computational complexity is
superior to that of OEA when $n \ll m$. This is achieved in the first modified
version by proving infeasibility without actually producing a solution of
$\mathrm{({\it Alt})}$, and in the second modified version by using more
memory.

Optimization and Control