On finding a vertex solution using interior point methods
An approach is proposed to generate a vertex solution while using a primal-dual interior-point method to solve linear programs \(\min\{z=c^ Tx\mid Ax=b, x\geq 0\}\). Let \(z^*\) denote the optimal objective value of the linear program, and \(v^*\) be a vertex solution of the linear program satisfying \(c^ Tv^*-z^*\leq\varepsilon\). The problem of finding the vertex solution \(v^*\) can be solved within the framework of implementations of interior-point methods. When the choice of \(\varepsilon\) is properly small the vertex solution \(v^*\) is the optimal solution of the linear program. The known practical approaches to finding a vertex from an interior solution perform computations similar to those in the simplex method. However there are potential disadvantages in using such approach to find a vertex solution. In the paper, an approach is proposed. The approach makes a controlled random perturbation to the cost vector to improve the likelihood that the perturbed linear program has unique solution. The size of the perturbation is controlled so that the objective value at the optimal solution of the perturbed problem is within the specified tolerance of \(z^*\). A method to identify the active constraints at the vertex to which the solutions are converging is given. The basic method is further refined to save computational effort. The proposed approach is tested by using a variation of the primal-dual interior-point method on problems from the NETLIB test set.
- scientific article; zbMATH DE number 434731
- Interior proximal point algorithm for linear programs
- Finding an interior point in the optimal face of linear programs
- Determination of optimal vertices from feasible solutions in unimodular linear programming
- An interior point method for linear programming
- A Self-Correcting Version of Karmarkar’s Algorithm
- An Implementation of a Primal-Dual Interior Point Method for Linear Programming
- An implementation of Karmarkar's algorithm for linear programming
- Computational experience with a dual affine variant of Karmarkar's method for linear programming
- Computational experience with a primal-dual interior point method for linear programming
- Further Development of a Primal-Dual Interior Point Method
- scientific article; zbMATH DE number 3717147 (Why is no real title available?)
- scientific article; zbMATH DE number 193993 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- Implementation of a Dual Affine Interior Point Algorithm for Linear Programming
- Implementations of Affine Scaling Methods: Approximate Solutions of Systems of Linear Equations Using Preconditioned Conjugate Gradient Methods
- On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
- On the Implementation of a Primal-Dual Interior Point Method
- Superlinear and quadratic convergence of primal-dual interior-point methods for linear programming revisited
- Some disadvantages of a Mehrotra-type primal-dual corrector interior point algorithm for linear programming
- Finding the closest extreme vertex to a fixed point
- Selected bibliography on degeneracy
- Degeneracy in interior point methods for linear programming: A survey
- Primal-dual interior point approach for computing \(l_ 1\)-solutions and \(l_ \infty\)-solutions of overdetermined linear systems
- Solving symmetric indefinite systems in an interior-point method for linear programming
- Recovering an optimal LP basis from an interior point solution
- Asymptotic convergence in a generalized predictor-corrector method
- Symmetric indefinite systems for interior point methods
- Multiple centrality corrections in a primal-dual method for linear programming
- On complexity of a new Mehrotra-type interior point algorithm for \(P_\ast(\kappa )\) linear complementarity problems
- A Mehrotra type predictor-corrector interior-point algorithm for linear programming
- A finite termination Mehrotra-type predictor-corrector algorithm
- Search for feasible solutions by interior point algorithms
- Vertex-searching method for linear interaction programming
- Mehrotra-type predictor-corrector algorithm revisited
- An \(\operatorname{O}(\sqrt{r}(\operatorname{cond}(G))^{1 / 4}\log \varepsilon^{- 1})\) iteration predictor-corrector interior-point method with a new one-norm neighbourhood for symmetric cone optimization
- An O( nL) iteration primal-dual second-order corrector algorithm for linear programming
- On the finite convergence of interior-point algorithms for linear programming
- Postponing the choice of the barrier parameter in Mehrotra-type predictor-corrector algorithms
- Cubically convergent method for locating a nearby vertex in linear programming
This page was built for publication: On finding a vertex solution using interior point methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1174841)
