A quadratically convergent O( n\;L)-iteration algorithm for linear programming
From MaRDI portal
Publication:2368076
DOI10.1007/BF01581242zbMATH Open0778.90037OpenAlexW2042092751MaRDI QIDQ2368076FDOQ2368076
Authors: Yinyu Ye, Richard Tapia, Yin Zhang, Osman Güler 
Publication date: 22 August 1993
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01581242
Recommendations
quadratic convergencesuperlinear convergencepolynomialitypredictor-corrector interior-point algorithm
Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
- Large-Step Interior Point Algorithms for Linear Complementarity Problems
- Finding an interior point in the optimal face of linear programs
- A Study of Indicators for Identifying Zero Variables in Interior-Point Methods
- On the finite convergence of interior-point algorithms for linear programming
- 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
- Title not available (Why is that?)
- Convergence behavior of interior-point algorithms
- Homotopy Continuation Methods for Nonlinear Complementarity Problems
- On the Superlinear and Quadratic Convergence of Primal-Dual Interior Point Linear Programming Algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Superlinear Convergence of Interior-Point Algorithms for a General Class of Problems
- A Superlinearly Convergent Polynomial Primal-Dual Interior-Point Algorithm for Linear Programming
Cited In (59)
- Iteration complexity of an interior-point algorithm for nonlinear p∗-complementarity problems
- A step-truncated method in a wide neighborhood interior-point algorithm for linear programming
- General central path and the largest step general central path following algorithm for linear programming
- Interior-point methods
- An \(O(\sqrt {n} L)\) iteration bound primal-dual cone affine scaling algorithm for linear programming
- An Algorithm for Convex Quadratic Programming That Requires O(n3.5L) Arithmetic Operations
- An \(O(nL)\) infeasible-interior-point algorithm for LCP with quadratic convergence
- Predictor–corrector methods for sufficient linear complementarity problems in a wide neighborhood of the central path
- The iteration-complexity upper bound for the Mizuno-Todd-Ye predictor-corrector algorithm is tight
- Corrector-predictor methods for sufficient linear complementarity problems
- Fast convergence of the simplified largest step path following algorithm
- The largest step path following algorithm for monotone linear complementarity problems
- Solving linear systems involved in constrained optimization
- A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points
- A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming
- An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
- On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP
- Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem
- An \(O(\sqrt nL)\) iteration primal-dual second-order corrector algorithm for linear programming
- Finding an interior point in the optimal face of linear programs
- Limiting behavior of weighted central paths in linear programming
- Trajectory-following methods for large-scale degenerate convex quadratic programming
- Polynomial convergence of two higher order interior-point methods for \(P_*(\kappa)\)-LCP in a wide neighborhood of the central path
- Solving the logit-based stochastic user equilibrium problem with elastic demand based on the extended traffic network model
- An improved predictor-corrector interior-point algorithm for linear complementarity problems with \(O(\sqrt{n}L)\)-iteration complexity
- The curvature integral and the complexity of linear complementarity problems
- Predictor-corrector method for nonlinear complementarity problems
- An interior point parameterized central path following algorithm for linearly constrained convex programming
- A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for linear programming over symmetric cones
- Superlinear convergence of the affine scaling algorithm
- Superlinearly Convergent $O ( \sqrt{n} L )$-Iteration Interior-Point Algorithms for Linear Programming and the Monotone Linear Complementarity Problem
- A quadratically convergent \(\text{O}((\kappa +1)\sqrt n L)\)-iteration algorithm for the \(P_ *(\kappa)\)-matrix linear complementarity problem
- 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
- A primal-dual interior point method whose running time depends only on the constraint matrix
- Local Superlinear Convergence of Polynomial-Time Interior-Point Methods for Hyperbolicity Cone Optimization Problems
- A primal-dual infeasible-interior-point algorithm for linear programming
- A new second-order corrector interior-point algorithm for \(P_\ast (\kappa)\)-LCP
- A primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils
- Asymptotic behavior of underlying NT paths in interior point methods for monotone semidefinite linear complementarity problems
- A superlinearly convergent wide-neighborhood predictor-corrector interior-point algorithm for linear programming
- Quadratic Convergence in a Primal-Dual Method
- Mehrotra-type predictor-corrector algorithms for sufficient linear complementarity problem
- Asymptotic convergence in a generalized predictor-corrector method
- A New Iteration-Complexity Bound for the MTY Predictor-Corrector Algorithm
- On the convergence of primal-dual interior-point methods with wide neighborhoods
- Strict complementarity in semidefinite optimization with elliptopes including the maxcut SDP
- Asymptotic behavior of helmberg-kojima-Monteiro (HKM) paths in interior-point methods for monotone semidefinite linear complementarity problems: General theory
- A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for symmetric optimization with the arc-search strategy
- 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
- On the Superlinear and Quadratic Convergence of Primal-Dual Interior Point Linear Programming Algorithms
- Polynomial Interior Point Cutting Plane Methods
- Quadratic convergence of the Iri-Imai algorithm for degenerate linear programming problems
- 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
- A quadratically convergent scaling newton’s method for nonlinear complementarity problems
- A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problems
- On the probabilistic complexity of finding an approximate solution for linear programming
This page was built for publication: A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2368076)
