A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming

From MaRDI portal
Revision as of 18:03, 2 February 2024 by Import240129110113 (talk | contribs) (Created automatically from import240129110113)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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


zbMATH Keywords

quadratic convergencesuperlinear convergencepolynomialitypredictor-corrector interior-point algorithm


Mathematics Subject Classification ID

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 (49)

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




This page was built for publication: A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:2368076&oldid=14985378"
Powered by MediaWiki