On improved Choi-Goldfarb solution-containing ellipsoids in linear programming (Q1591595)

The author proposes an approach to diminish the size of the solution-containing ellipsoids derived in [\textit{I. C. Choi} and \textit{D. Goldfarb} [J. Optim. Theory Appl. 80, 161-173 (1994; Zbl 0797.90060)]. To get a tighter estimation of the ellipsoid size a certain localization of the optimal solution set is used. It is shown that the proper choice of the localization results in a smaller containing ellipsoid. A similar approach is used to derive the primal-dual containing ellipsoid. In section 2 basic notations and results associated with Choi-Goldfarb ellipsoids are stated. In section 3 the improved primal ellipsoids are constructed. Section 4 is on primal-dual ellipsoids: a new criterion for identifying the optimal basis is stated and compared with previous results.