On improved Choi-Goldfarb solution-containing ellipsoids in linear programming
type: Item
instance of: scholarly article
title: On improved Choi-Goldfarb solution-containing ellipsoids in linear programming
zbMATH Open document ID: 0997.90046
DOI: 10.1016/S0167-6377(00)00026-2
author: I. Litvinchev
published in: Operations Research Letters
publication date: 2000-12-20T00:00:00Z
review text: 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.
reviewed by: Reinhardt Euler
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C51
zbMATH DE Number: 1547257
zbMATH Keywords: linear programming
zbMATH Keywords: interior point methods
zbMATH Keywords: solution-containing ellipsoids
zbMATH Keywords: primal-dual containing ellipsoid
zbMATH Keywords: Choi-Goldfarb ellipsoids
MaRDI profile type: Publication
cites work: On solution-containing ellipsoids in linear programming
cites work: On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm
cites work: Determining basic variables of optimal solutions in Karmarkar's new LP algorithm
cites work: Q3738934
cites work: Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm
cites work: Q5691079
cites work: Recovering Optimal Basic Variables in Karmarkar's Polynomial Algorithm for Linear Programming
cites work: A ``build-down'' scheme for linear programming
cites work: Containing and shrinking ellipsoids in the path-following algorithm
Wikidata QID: Q127064087
Recommended article: On solution-containing ellipsoids in linear programming
Recommended article: Q5289572
Recommended article: Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm
Recommended article: Ellipsoids containing optimal solutions of the linear programming problem
Recommended article: Q5323411
Recommended article: Q3328257
Recommended article: Q4823512
Recommended article: An ellipsoid algorithm for equality-constrained nonlinear programs
Recommended article: An improved ellipsoid method for solving convex differentiable optimization problems
Recommended article: Q3033572
description: scientific article; zbMATH DE number 1547257