Polynomiality of infeasible-interior-point algorithms for linear programming
From MaRDI portal
An infeasible interior point algorithm for solving a primal-dual pair of linear programming problems finds approximate optimal solutions of the pair if both problems have interior points and detects infeasibility when the sequence of iterates diverges. Polynomial-time convergence of this algorithm under the assumption that both primal and dual problems have feasible points are proved. The author shows that a modification of the infeasible interior point algorithm ``solves the pair of problems in polynomial time, without assuming the existence of the LP solution. Furthermore, he develops an \(O(nL)\)-iteration complexity result for a variant of the algorithm.
Recommendations
- scientific article; zbMATH DE number 1322430
- Global and polynomial-time convergence of an infeasible-interior-point algorithm using inexact computation.
- scientific article; zbMATH DE number 1047678
- Basic lemmas in polynomial-time infeasible-interior-point methods for linear programs
- Infeasible-Interior-Point Primal-Dual Potential-Reduction Algorithms for Linear Programming
Cites work
- A polynomial-time algorithm for a class of linear complementarity problems
- A primal-dual infeasible-interior-point algorithm for linear programming
- An Infeasible-Interior-Point Predictor-Corrector Algorithm for Linear Programming
- Computational experience with a primal-dual interior point method for linear programming
- Feasibility issues in a primal-dual interior-point method for linear programming
- scientific article; zbMATH DE number 4164543 (Why is no real title available?)
- scientific article; zbMATH DE number 4072729 (Why is no real title available?)
- scientific article; zbMATH DE number 4126998 (Why is no real title available?)
- Interior path following primal-dual algorithms. I: Linear programming
- Interior path following primal-dual algorithms. II: Convex quadratic programming
- On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
- On the Convergence of a Class of Infeasible Interior-Point Methods for the Horizontal Linear Complementarity Problem
Cited in
(74)- Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming
- A primal-dual infeasible-interior-point algorithm for linear programming
- A predictor-corrector infeasible-interior-point algorithm for linear programming
- A constant-potential infeasible-start interior-point algorithm with computational experiments and applications
- Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming
- Global and polynomial-time convergence of an infeasible-interior-point algorithm using inexact computation.
- Average number of iterations of some polynomial interior-point -- algorithms for linear programming
- An arc-search \({\mathcal {O}}(nL)\) infeasible-interior-point algorithm for linear programming
- A modified and simplified full Nesterov-Todd step \(\mathcal {O}(N)\) infeasible interior-point method for second-order cone optimization
- A generalized homogeneous and self-dual algorithm for linear programming
- A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problems
- Basic lemmas in polynomial-time infeasible-interior-point methods for linear programs
- An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution
- An infeasible-interior-point algorithm using projections onto a convex set
- An \(O(nL)\) infeasible-interior-point algorithm for LCP with quadratic convergence
- New infeasible interior-point algorithm based on monomial method
- An infeasible-interior-point potential-reduction algorithm for linear programming
- Two computationally efficient polynomial-iteration infeasible interior-point algorithms for linear programming
- A full-Newton step infeasible interior-point algorithm based on darvay directions for linear optimization
- Status determination by interior-point methods for convex optimization problems in domain-driven form
- Simplified infeasible interior-point algorithm for linear optimization based on a simple function
- An infeasible interior-point algorithm for linear optimization over Cartesian symmetric cones
- Validated infeasible interior-point predictor-corrector methods for linear programming
- New complexity analysis of IIPMs for linear optimization based on a specific self-regular function
- An infeasible interior-point algorithm with full-Newton step for linear optimization
- The complexity of self-regular proximity based infeasible IPMs
- A primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils
- Estimating the probability that a given vector is in the convex hull of a random sample
- Probabilistic analysis of an infeasible-interior-point algorithm for linear programming
- An infeasible interior-point algorithm based on modified Nesterov and Todd directions for symmetric linear complementarity problem
- A full-Newton step infeasible interior-point method for linear optimization based on a trigonometric kernel function
- A modified full-Newton step infeasible interior-point algorithm for linear optimization
- An improved interior-point cutting-plane method for binary quadratic optimization
- On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems
- A new feasible interior-point algorithm with full step for linear optimization based on a simple function
- A wide neighborhood infeasible-interior-point method with arc-search for linear programming
- The practical behavior of the homogeneous self-dual formulations in interior point methods
- Infeasible interior-point methods for linear optimization based on large neighborhood
- A class of infeasible interior point algorithms for convex quadratic programming
- Interior-point methods for linear programming: a review
- A full Nesterov-Todd step infeasible interior-point method for second-order cone optimization
- A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming
- A new complexity analysis for full-Newton step infeasible interior-point algorithm for horizontal linear complementarity problems
- Search directions and convergence analysis of some infeasibnle path-following methods for the monoton semi-definite lcp∗
- scientific article; zbMATH DE number 1300325 (Why is no real title available?)
- scientific article; zbMATH DE number 1322430 (Why is no real title available?)
- scientific article; zbMATH DE number 1047678 (Why is no real title available?)
- Convergence and polynomiality of primal-dual interior-point algorithms for linear programming with selective addition of inequalities
- An infeasible interior-point method for the \(P_*\)-matrix linear complementarity problem based on a trigonometric kernel function with full-Newton step
- Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem
- A Surface of Analytic Centers and Primal-Dual Infeasible-Interior-Point Algorithms for Linear Programming
- scientific article; zbMATH DE number 778139 (Why is no real title available?)
- Two Infeasible Interior-Point Predictor-Corrector Algorithms for Linear Programming
- An adaptive infeasible interior-point algorithm with full-Newton step for linear optimization
- A new strategy in the complexity analysis of an infeasible-interior-point method for symmetric cone programming
- A modified infeasible-interior-point algorithm for linear optimization problems
- New complexity analysis of full Nesterov-Todd step infeasible interior point method for second-order cone optimization
- Primal-dual interior-point methods for domain-driven formulations
- A new infeasible interior-point algorithm for linear complementarity problem
- SimplifiedO(nL) infeasible interior-point algorithm for linear optimization using full-Newton steps
- scientific article; zbMATH DE number 2195332 (Why is no real title available?)
- Detecting infeasibility in infeasible-interior-point methods for optimization
- A primal-dual infeasible-interior-point algorithm for multiple objective linear programming problems
- A primal-dual infeasible-interior-point algorithm for multiple objective linear programming problems
- Design of continuous-time recurrent neural networks with piecewise-linear activation function for generation of prescribed sequences of bipolar vectors
- A full-Newton step \(O(n)\) infeasible-interior-point algorithm for linear complementarity problems
- Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming
- Full Nesterov-Todd step infeasible interior-point method for symmetric optimization
- A new full-Newton step \(O(n)\) infeasible interior-point algorithm for semidefinite optimization
- A full-Newton step infeasible interior-point algorithm for linear programming based on a kernel function
- A numerical study of an infeasible primal-dual path-following algorithm for linear programming
- An adaptive infeasible interior-point algorithm with full Nesterov-Todd step for semidefinite optimization
- Convergence of the homotopy path for a full-Newton step infeasible interior-point method
- Improved full-Newton step O(nL) infeasible interior-point method for linear optimization
This page was built for publication: Polynomiality of infeasible-interior-point algorithms for linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1340070)
