Containing and shrinking ellipsoids in the path-following algorithm

The authors describe a new potential function and a sequence of ellipsoids in the path-following algorithm for convex quadratic programming. Each ellipsoid in the sequence contains all of the optimal primal and dual slack vectors. Furthermore, the volumes of the ellipsoids shrink at the ratio , in comparison to in Karmarkar's algorithm and in the ellipsoid method. The authors also show how to use these ellipsoids to identify the optimal basis in the course of the algorithm for linear programming.