A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming
From MaRDI portal
Publication:2368076
DOI10.1007/BF01581242zbMath0778.90037OpenAlexW2042092751MaRDI QIDQ2368076
Yin Zhang, Yinyu Ye, Richard A. Tapia, 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
quadratic convergencesuperlinear convergencepolynomialitypredictor-corrector interior-point algorithm
Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items
Superlinear convergence of the affine scaling algorithm ⋮ Limiting behavior of weighted central paths in linear programming ⋮ Solving the logit-based stochastic user equilibrium problem with elastic demand based on the extended traffic network model ⋮ A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for linear programming over symmetric cones ⋮ Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence ⋮ Asymptotic convergence in a generalized predictor-corrector method ⋮ A primal-dual interior point method whose running time depends only on the constraint matrix ⋮ A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming ⋮ Solving linear systems involved in constrained optimization ⋮ Local Superlinear Convergence of Polynomial-Time Interior-Point Methods for Hyperbolicity Cone Optimization Problems ⋮ Fast convergence of the simplified largest step path following algorithm ⋮ The curvature integral and the complexity of linear complementarity problems ⋮ The largest step path following algorithm for monotone linear complementarity problems ⋮ A quadratically convergent \(\text{O}((\kappa +1)\sqrt n L)\)-iteration algorithm for the \(P_ *(\kappa)\)-matrix linear complementarity problem ⋮ Predictor–corrector methods for sufficient linear complementarity problems in a wide neighborhood of the central path ⋮ Trajectory-following methods for large-scale degenerate convex quadratic programming ⋮ 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 ⋮ A quadratically convergent scaling newton’s method for nonlinear complementarity problems ⋮ A primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils ⋮ A superlinearly convergent wide-neighborhood predictor-corrector interior-point algorithm for linear programming ⋮ Predictor-corrector method for nonlinear complementarity problems ⋮ A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for symmetric optimization with the arc-search strategy ⋮ An improved predictor-corrector interior-point algorithm for linear complementarity problems with \(O(\sqrt{n}L)\)-iteration complexity ⋮ A step-truncated method in a wide neighborhood interior-point algorithm for linear programming ⋮ Asymptotic behavior of underlying NT paths in interior point methods for monotone semidefinite linear complementarity problems ⋮ Asymptotic behavior of helmberg-kojima-Monteiro (HKM) paths in interior-point methods for monotone semidefinite linear complementarity problems: General theory ⋮ 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 ⋮ Polynomial Interior Point Cutting Plane Methods ⋮ Mehrotra-type predictor-corrector algorithms for sufficient linear complementarity problem ⋮ On the probabilistic complexity of finding an approximate solution for linear programming ⋮ Corrector-predictor methods for sufficient linear complementarity problems ⋮ General central path and the largest step general central path following algorithm for linear programming ⋮ Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem ⋮ Polynomial convergence of two higher order interior-point methods for \(P_*(\kappa)\)-LCP in a wide neighborhood of the central path ⋮ 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 ⋮ Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem ⋮ On the analyticity of underlying HKM paths for monotone semidefinite linear complementarity problems ⋮ Strict Complementarity in Semidefinite Optimization with Elliptopes Including the MaxCut SDP ⋮ The Mizuno-Todd-Ye algorithm in a larger neighborhood of the central path ⋮ Interior-point methods ⋮ A primal-dual infeasible-interior-point algorithm for linear programming ⋮ A new second-order corrector interior-point algorithm for P*(k)-LCP ⋮ Iteration complexity of an interior-point algorithm for nonlinear p∗-complementarity problems ⋮ 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 ⋮ An interior point parameterized central path following algorithm for linearly constrained convex programming
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