Containing and shrinking ellipsoids in the path-following algorithm

DOI10.1007/BF01580848zbMath0746.90049OpenAlexW1966422374MaRDI QIDQ1813834

Yinyu Ye, Michael J. Todd

Publication date: 25 June 1992

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01580848

zbMATH Keywords

convex quadratic programmingpotential functionpath-following algorithmellipsoid methodKarmarkar's algorithmsequence of ellipsoids

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20) Linear programming (90C05)

Related Items

Solving linear systems involved in constrained optimization, Cubically convergent method for locating a nearby vertex in linear programming, On some efficient interior point methods for nonlinear convex programming, An optimal-basis identification technique for interior-point linear programming algorithms, On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm, Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem, On the convergence of the method of analytic centers when applied to convex quadratic programs, A new potential reduction algorithm for smooth convex programming, Global ellipsoidal approximations and homotopy methods for solving convex analytic programs, Primal-dual-infeasible Newton approach for the analytic center deep-cutting plane method, On improved Choi-Goldfarb solution-containing ellipsoids in linear programming, Degeneracy in interior point methods for linear programming: A survey, An \(O(n^ 3L)\) potential reduction algorithm for linear programming, On solution-containing ellipsoids in linear programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
• Karmarkar's algorithm and the ellipsoid method
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Conical projection algorithms for linear programming
• Interior path following primal-dual algorithms. II: Convex quadratic programming
• A polynomial-time algorithm for a class of linear complementarity problems
• Complementary pivot theory of mathematical programming
• Recovering Optimal Basic Variables in Karmarkar's Polynomial Algorithm for Linear Programming
• The Ellipsoid Method Generates Dual Variables
• Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm
• The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories