The Ellipsoid Method Generates Dual Variables

Abstract

We show that the ellipsoid algorithm applied to a system of linear inequalities can be implemented in such a way that at each iteration there is a short proof of the containment of the feasible region in the current ellipsoid. Moreover, the data describing each ellipsoid also generate dual variables that provide bounds on the linear functions appearing in the inequalities.