Convergence behavior of interior-point algorithms
From MaRDI portal
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.
Recommendations
- Convergence of Interior Point Algorithms for the Monotone Linear Complementarity Problem
- On the finite convergence of interior-point algorithms for linear programming
- Superlinearly Convergent $O ( \sqrt{n} L )$-Iteration Interior-Point Algorithms for Linear Programming and the Monotone Linear Complementarity Problem
- Local convergence of interior-point algorithms for degenerate monotone LCP
- On the Superlinear Convergence of Interior-Point Algorithms for a General Class of Problems
Cites work
- A long-step barrier method for convex quadratic programming
- A modification of Karmarkar's linear programming algorithm
- A new polynomial-time algorithm for linear programming
- A polynomial method of approximate centers for linear programming
- A polynomial-time algorithm for a class of linear complementarity problems
- A polynomial-time algorithm, based on Newton's method, for linear programming
- A variation on Karmarkar’s algorithm for solving linear programming problems
- An $O(\sqrt{n} L)$-Iteration Large-Step Primal-Dual Affine Algorithm for Linear Programming
- An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
- An \(O(n^ 3L)\) potential reduction algorithm for linear programming
- An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
- An analogue of Moreau's proximation theorem, with application to the nonlinear complementarity problem
- An Extension of Karmarkar Type Algorithm to a Class of Convex Separable Programming Problems with Global Linear Rate of Convergence
- An Implementation of a Primal-Dual Interior Point Method for Linear Programming
- Complexity analysis of a linear complementarity algorithm based on a Lyapunov function
- Existence of Interior Points and Interior Paths in Nonlinear Monotone Complementarity Problems
- scientific article; zbMATH DE number 4131946 (Why is no real title available?)
- scientific article; zbMATH DE number 3121284 (Why is no real title available?)
- scientific article; zbMATH DE number 4164543 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3788387 (Why is no real title available?)
- scientific article; zbMATH DE number 4126998 (Why is no real title available?)
- scientific article; zbMATH DE number 3301975 (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
- Large Step Path-Following Methods for Linear Programming, Part I: Barrier Function Method
- Large Step Path-Following Methods for Linear Programming, Part II: Potential Reduction Method
- Large-Step Interior Point Algorithms for Linear Complementarity Problems
- Long steps in an \(O(n^ 3L)\) algorithm for linear programming
- Near boundary behavior of primal-dual potential reduction algorithms for linear programming
- On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
- On the Superlinear and Quadratic Convergence of Primal-Dual Interior Point Linear Programming Algorithms
- Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
- Theoretical convergence of large-step primal-dual interior point algorithms for linear programming
Cited in
(56)- On interior algorithms for linear programming with no regularity assumptions
- Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming
- On parametric semidefinite programming
- Finding an interior point in the optimal face of linear programs
- On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP
- Local convergence of interior-point algorithms for degenerate monotone LCP
- Constant potential primal-dual algorithms: A framework
- Recovering an optimal LP basis from an interior point solution
- On homogeneous and self-dual algorithms for LCP
- Initialization in semidefinite programming via a self-dual skew-symmetric embedding
- A superlinearly convergent wide-neighborhood predictor-corrector interior-point algorithm for linear programming
- On self-regular IPMs (with comments and rejoinder)
- Stabilization of Mehrotra's primal-dual algorithm and its implementation
- On the convergence of primal-dual interior-point methods with wide neighborhoods
- Determining the interior point of a system of linear inequalities
- On the convergence rate of Newton interior-point methods in the absence of strict complementarity
- Analytic centers and repelling inequalities
- Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence
- A primal-dual interior-point method for linear programming based on a weighted barrier function
- A Mehrotra-type predictor-corrector algorithm with polynomiality and \(Q\)-subquadratic convergence
- Identifying an optimal basis in linear programming
- Interior-point methods for nonlinear complementarity problems
- A general parametric analysis approach and its implication to sensitivity analysis in interior point methods
- A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks
- Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming
- On the behavior of Lagrange multipliers in convex and nonconvex infeasible interior point methods
- A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion
- Necessary and sufficient conditions of solution uniqueness in 1-norm minimization
- On the convergence of a predictor-corrector variant algorithm
- A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming
- Input design for discrimination between classes of LTI models
- Dynamic non-diagonal regularization in interior point methods for linear and convex quadratic programming
- On the uniqueness of optimal strategies in symmetric matrix games
- A smoothing-type algorithm for solving linear complementarity problems with strong convergence properties
- On the probabilistic complexity of finding an approximate solution for linear programming
- An efficient arc-search interior-point algorithm for convex quadratic programming with box constraints
- A quadratically convergent polynomial long-step algorithm for A class of nonlinear monotone complementarity problems*
- A STUDY ON SENSITIVITY ANALYSIS FOR CONVEX QUADRATIC PROGRAMS
- A polynomial arc-search interior-point algorithm for convex quadratic programming
- Conic convex programming and self-dual embedding
- Convergence of Interior Point Algorithms for the Monotone Linear Complementarity Problem
- scientific article; zbMATH DE number 1444279 (Why is no real title available?)
- Primal-dual path-following methods and the trust-region updating strategy for linear programming with noisy data
- ON THE PROPERTIES OF ∊-SENSITIVITY ANALYSIS FOR LINEAR PROGRAMMING
- Substantiation of interior point algorithms
- General central path and the largest step general central path following algorithm for linear programming
- A step-truncated method in a wide neighborhood interior-point algorithm for linear programming
- On a class of interior point algorithms
- Quadratic regularizations in an interior-point method for primal block-angular problems
- On the finite convergence of interior-point algorithms for linear programming
- On the geometry and refined rate of primal-dual hybrid gradient for linear programming
- A new algorithm for solving convex parametric quadratic programs based on graphical derivatives of solution mappings
- Characterizing the universal rigidity of generic frameworks
- Theory of semidefinite programming for sensor network localization
- Identifying the optimal partition in convex quadratic programming
- Bi-parametric optimal partition invariancy sensitivity analysis in linear optimization
This page was built for publication: Convergence behavior of interior-point algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q689124)
