Cubically convergent method for locating a nearby vertex in linear programming
From MaRDI portal
Given a point sufficiently close to a nondegenerate basic feasible solution \(x^*\) of a linear program, we show how to generate a sequence \(\{p^ k\}\) that converges to the 0-1 vector \(sign(x^*)\) at a Q-cubic rate. This extremely fast convergence enables us to determine, with a high degree of certainty, which variables will be zero and which will be nonzero at optimality and then construct \(x^*\) from this information.
Recommendations
- scientific article; zbMATH DE number 4062817
- On finding a vertex solution using interior point methods
- On the finite convergence of interior-point algorithms for linear programming
- scientific article; zbMATH DE number 4047434
- An optimal-basis identification technique for interior-point linear programming algorithms
Cites work
- A modification of Karmarkar's linear programming algorithm
- A new polynomial-time algorithm for linear programming
- A variation on Karmarkar’s algorithm for solving linear programming problems
- An implementation of Karmarkar's algorithm for linear programming
- Computational experience with a dual affine variant of Karmarkar's method for linear programming
- Containing and shrinking ellipsoids in the path-following algorithm
- scientific article; zbMATH DE number 4164543 (Why is no real title available?)
- scientific article; zbMATH DE number 3301975 (Why is no real title available?)
This page was built for publication: Cubically convergent method for locating a nearby vertex in linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911456)
