A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming
From MaRDI portal
Publication:2368076
DOI10.1007/BF01581242zbMath0778.90037MaRDI QIDQ2368076
Yinyu Ye, Yin Zhang, Osman Güler, Richard A. Tapia
Publication date: 22 August 1993
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
quadratic convergence; superlinear convergence; polynomiality; predictor-corrector interior-point algorithm
90C60: Abstract computational complexity for mathematical programming problems
90C05: Linear programming
90-08: Computational methods for problems pertaining to operations research and mathematical programming
Related Items
Polynomial Interior Point Cutting Plane Methods, Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem, A quadratically convergent scaling newton’s method for nonlinear complementarity problems, Predictor–corrector methods for sufficient linear complementarity problems in a wide neighborhood of the central path, General central path and the largest step general central path following algorithm for linear programming, A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming, Asymptotic behavior of helmberg-kojima-Monteiro (HKM) paths in interior-point methods for monotone semidefinite linear complementarity problems: General theory, Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem, On the analyticity of underlying HKM paths for monotone semidefinite linear complementarity problems, A primal-dual infeasible-interior-point algorithm for linear 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, Limiting behavior of weighted central paths in linear programming, Asymptotic convergence in a generalized predictor-corrector method, A primal-dual interior point method whose running time depends only on the constraint matrix, Fast convergence of the simplified largest step path following algorithm, The largest step path following algorithm for monotone linear complementarity problems, Predictor-corrector method for nonlinear complementarity problems, Interior-point methods, On the convergence of primal-dual interior-point methods with wide neighborhoods, A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points, The Mizuno-Todd-Ye algorithm in a larger neighborhood of the central path, Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence, Solving linear systems involved in constrained optimization, The curvature integral and the complexity of linear complementarity problems, A quadratically convergent \(\text{O}((\kappa +1)\sqrt n L)\)-iteration algorithm for the \(P_ *(\kappa)\)-matrix linear complementarity problem, A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problems, An \(O(nL)\) infeasible-interior-point algorithm for LCP with quadratic convergence, Superlinear convergence of the affine scaling algorithm, A path to the Arrow-Debreu competitive market equilibrium, Corrector-predictor methods for monotone linear complementarity problems in a wide neighborhood of the central path, On the probabilistic complexity of finding an approximate solution for linear programming, Iteration complexity of an interior-point algorithm for nonlinear p∗-complementarity problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the finite convergence of interior-point algorithms for linear programming
- Convergence behavior of interior-point algorithms
- A polynomial-time algorithm for a class of linear complementarity problems
- On the complexity of following the central path of linear programs by linear extrapolation. II
- Finding an interior point in the optimal face of linear programs
- Homotopy Continuation Methods for Nonlinear Complementarity Problems
- On the Superlinear and Quadratic Convergence of Primal-Dual Interior Point Linear Programming Algorithms
- On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
- A Study of Indicators for Identifying Zero Variables in Interior-Point Methods
- A Superlinearly Convergent Polynomial Primal-Dual Interior-Point Algorithm for Linear Programming
- Large-Step Interior Point Algorithms for Linear Complementarity Problems
- On the Superlinear Convergence of Interior-Point Algorithms for a General Class of Problems
