Convergence behavior of interior-point algorithms (Q689124): Difference between revisions

The author establishes that many interior point algorithms for linear programming generate a solution sequence in which every limit point satisfies the strict complementarity condition. Each limit point maximizes the number of its nonzero components among all solutions.

0 references

zbMATH Keywords

interior point algorithms

0 references

strict complementarity condition

0 references

reviewed by

Ding-Zhu Du

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Long steps in an $O(n^ 3L)$ algorithm for linear programming

0 references

A long-step barrier method for convex quadratic programming

0 references

A variation on Karmarkar’s algorithm for solving linear programming problems

0 references

Q5583564

0 references

Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function

0 references

Q3236242

0 references

Q3033554

0 references

Large Step Path-Following Methods for Linear Programming, Part I: Barrier Function Method

0 references

Large Step Path-Following Methods for Linear Programming, Part II: Potential Reduction Method

0 references

An $O(\sqrt{n} L)$-Iteration Large-Step Primal-Dual Affine Algorithm for Linear Programming

0 references

Existence of Interior Points and Interior Paths in Nonlinear Monotone Complementarity Problems

0 references

A new polynomial-time algorithm for linear programming

0 references

Theoretical convergence of large-step primal-dual interior point algorithms for linear programming

0 references

Large-Step Interior Point Algorithms for Linear Complementarity Problems

0 references

An $O(\sqrt n L)$ iteration potential reduction algorithm for linear complementarity problems

0 references

A polynomial-time algorithm for a class of linear complementarity problems

0 references

Q3491304

0 references

An analogue of Moreau's proximation theorem, with application to the nonlinear complementarity problem

0 references

Q3965924

0 references

An Implementation of a Primal-Dual Interior Point Method for Linear Programming

0 references

Q4206561

0 references

On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming

0 references

Interior path following primal-dual algorithms. I: Linear programming

0 references

Interior path following primal-dual algorithms. II: Convex quadratic programming

0 references

An Extension of Karmarkar Type Algorithm to a Class of Convex Separable Programming Problems with Global Linear Rate of Convergence

0 references

A polynomial-time algorithm, based on Newton's method, for linear programming

0 references

A polynomial method of approximate centers for linear programming

0 references

Q3818127

0 references

Complexity analysis of a linear complementarity algorithm based on a Lyapunov function

0 references

An algorithm for linear programming which requires $O(((m+n)n^ 2+(m+n)^{1.5}n)L)$ arithmetic operations

0 references

A modification of Karmarkar's linear programming algorithm

0 references

Near boundary behavior of primal-dual potential reduction algorithms for linear programming

0 references

An $O(n^ 3L)$ potential reduction algorithm for linear programming

0 references

On the Superlinear and Quadratic Convergence of Primal-Dual Interior Point Linear Programming Algorithms

0 references

full work available at URL

https://doi.org/10.1007/bf01580610

0 references

Identifiers

zbMATH Open document ID

0803.90087

0 references

DOI

10.1007/BF01580610

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:689124

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Long steps in an \(O(n^ 3L)\) algorithm for linear programming
+Normal rank
@@ Property / cites work @@
+A long-step barrier method for convex quadratic programming
+Normal rank
@@ Property / cites work @@
+A variation on Karmarkar’s algorithm for solving linear programming problems
+Normal rank
@@ Property / cites work @@
+Q5583564
@@ Property / cites work: Q5583564 / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
+Normal rank
@@ Property / cites work @@
+Q3236242
@@ Property / cites work: Q3236242 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3033554
@@ Property / cites work: Q3033554 / rank @@
+Normal rank
@@ Property / cites work @@
+Large Step Path-Following Methods for Linear Programming, Part I: Barrier Function Method
+Normal rank
@@ Property / cites work @@
+Large Step Path-Following Methods for Linear Programming, Part II: Potential Reduction Method
+Normal rank
@@ Property / cites work @@
+An $O(\sqrt{n} L)$-Iteration Large-Step Primal-Dual Affine Algorithm for Linear Programming
+Normal rank
@@ Property / cites work @@
+Existence of Interior Points and Interior Paths in Nonlinear Monotone Complementarity Problems
+Normal rank
@@ Property / cites work @@
+A new polynomial-time algorithm for linear programming
+Normal rank
@@ Property / cites work @@
+Theoretical convergence of large-step primal-dual interior point algorithms for linear programming
+Normal rank
@@ Property / cites work @@
+Large-Step Interior Point Algorithms for Linear Complementarity Problems
+Normal rank
@@ Property / cites work @@
+An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
+Normal rank
@@ Property / cites work @@
+A polynomial-time algorithm for a class of linear complementarity problems
+Normal rank
@@ Property / cites work @@
+Q3491304
@@ Property / cites work: Q3491304 / rank @@
+Normal rank
@@ Property / cites work @@
+An analogue of Moreau's proximation theorem, with application to the nonlinear complementarity problem
+Normal rank
@@ Property / cites work @@
+Q3965924
@@ Property / cites work: Q3965924 / rank @@
+Normal rank
@@ Property / cites work @@
+An Implementation of a Primal-Dual Interior Point Method for Linear Programming
+Normal rank
@@ Property / cites work @@
+Q4206561
@@ Property / cites work: Q4206561 / rank @@
+Normal rank
@@ Property / cites work @@
+On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
+Normal rank
@@ Property / cites work @@
+Interior path following primal-dual algorithms. I: Linear programming
+Normal rank
@@ Property / cites work @@
+Interior path following primal-dual algorithms. II: Convex quadratic programming
+Normal rank
@@ Property / cites work @@
+An Extension of Karmarkar Type Algorithm to a Class of Convex Separable Programming Problems with Global Linear Rate of Convergence
+Normal rank
@@ Property / cites work @@
+A polynomial-time algorithm, based on Newton's method, for linear programming
+Normal rank
@@ Property / cites work @@
+A polynomial method of approximate centers for linear programming
+Normal rank
@@ Property / cites work @@
+Q3818127
@@ Property / cites work: Q3818127 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity analysis of a linear complementarity algorithm based on a Lyapunov function
+Normal rank
@@ Property / cites work @@
+An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
+Normal rank
@@ Property / cites work @@
+A modification of Karmarkar's linear programming algorithm
+Normal rank
@@ Property / cites work @@
+Near boundary behavior of primal-dual potential reduction algorithms for linear programming
+Normal rank
@@ Property / cites work @@
+An \(O(n^ 3L)\) potential reduction algorithm for linear programming
+Normal rank
@@ Property / cites work @@
+On the Superlinear and Quadratic Convergence of Primal-Dual Interior Point Linear Programming Algorithms
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/bf01580610
+Normal rank
@@ Property / OpenAlex ID @@
+W2050897335
@@ Property / OpenAlex ID: W2050897335 / rank @@
+Normal rank