Containing and shrinking ellipsoids in the path-following algorithm
DOI10.1007/BF01580848zbMATH Open0746.90049OpenAlexW1966422374MaRDI QIDQ1813834FDOQ1813834
Authors: 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
Recommendations
convex quadratic programmingellipsoid methodpotential functionKarmarkar's algorithmpath-following algorithmsequence of ellipsoids
Numerical mathematical programming methods (65K05) Quadratic programming (90C20) Convex programming (90C25) Linear programming (90C05) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- A new polynomial-time algorithm for linear programming
- Title not available (Why is that?)
- A polynomial-time algorithm, based on Newton's method, for linear programming
- Complementary pivot theory of mathematical programming
- Title not available (Why is that?)
- An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
- A polynomial-time algorithm for a class of linear complementarity problems
- Interior path following primal-dual algorithms. II: Convex quadratic programming
- Conical projection algorithms for linear programming
- The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories
- Title not available (Why is that?)
- Karmarkar's algorithm and the ellipsoid method
- Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm
- The Ellipsoid Method Generates Dual Variables
- Recovering Optimal Basic Variables in Karmarkar's Polynomial Algorithm for Linear Programming
Cited In (17)
- Navigation of a quadratic potential with ellipsoidal obstacles
- On improved Choi-Goldfarb solution-containing ellipsoids in linear programming
- Solving linear systems involved in constrained optimization
- On some efficient interior point methods for nonlinear convex programming
- Degeneracy in interior point methods for linear programming: A survey
- Global ellipsoidal approximations and homotopy methods for solving convex analytic programs
- Primal-dual-infeasible Newton approach for the analytic center deep-cutting plane method
- Karmarkar's algorithm and the ellipsoid method
- An \(O(n^ 3L)\) potential reduction algorithm for linear programming
- On solution-containing ellipsoids in linear programming
- Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem
- On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm
- An optimal-basis identification technique for interior-point linear programming algorithms
- Cubically convergent method for locating a nearby vertex in linear programming
- On the convergence of the method of analytic centers when applied to convex quadratic programs
- Ellipsoids containing optimal solutions of the linear programming problem
- A new potential reduction algorithm for smooth convex programming
This page was built for publication: Containing and shrinking ellipsoids in the path-following algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1813834)
