The Ellipsoid Method Generates Dual Variables
The Ellipsoid Method Generates Dual Variables
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 …