On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms

DOI10.1007/BF01585769zbMath0837.90087OpenAlexW1995535418MaRDI QIDQ1890928

Yin Zhang, Detong Zhang

Publication date: 28 May 1995

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01585769

zbMATH Keywords

theoretical convergencepolynomial complexity boundspredictor-corrector primal-dual interior-point algorithm

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items (47)

An predictor–corrector interior-point algorithm for semidefinite optimization based on a wide neighbourhood ⋮ An arc-search infeasible-interior-point method for symmetric optimization in a wide neighborhood of the central path ⋮ An \(O(\sqrt{n}L)\) iteration Mehrotra-type predictor-corrector algorithm for monotone linear complementarity problem ⋮ A wide neighborhood infeasible-interior-point method with arc-search for linear programming ⋮ A wide neighborhood interior-point algorithm with arc-search for \(P_{\ast}(\kappa)\) linear complementarity problem ⋮ A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for linear programming over symmetric cones ⋮ A wide neighborhood arc-search interior-point algorithm for convex quadratic programming ⋮ A wide neighborhood arc-search interior-point algorithm for convex quadratic programming with box constraints and linear constraints ⋮ Polynomial convergence of Mehrotra-type prediction-corrector infeasible-IPM for symmetric optimization based on the commutative class directions ⋮ A wide neighborhood primal-dual predictor-corrector interior-point method for symmetric cone optimization ⋮ A New Second-Order Infeasible Primal-Dual Path-Following Algorithm for Symmetric Optimization ⋮ Improved complexity using higher-order correctors for primal-dual Dikin affine scaling ⋮ A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighbourhood for semi-definite programming ⋮ Trajectory-following methods for large-scale degenerate convex quadratic programming ⋮ A New Iteration-Complexity Bound for the MTY Predictor-Corrector Algorithm ⋮ Polynomial time second order mehrotra-type predictor--corrector algorithms ⋮ An \(\ell_{2}\)-neighborhood infeasible interior-point algorithm for linear complementarity problems ⋮ A Mehrotra-type predictor-corrector algorithm with polynomiality and \(Q\)-subquadratic convergence ⋮ A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming ⋮ A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for symmetric optimization with the arc-search strategy ⋮ A wide neighborhood interior-point method for Cartesian \(P_*(\kappa )\)-LCP over symmetric cones ⋮ A constraint-reduced MPC algorithm for convex quadratic programming, with a modified active set identification scheme ⋮ Optimized choice of parameters in interior-point methods for linear programming ⋮ Polynomial convergence of second-order mehrotra-type predictor-corrector algorithms over symmetric cones ⋮ A step-truncated method in a wide neighborhood interior-point algorithm for linear programming ⋮ A Mehrotra-type second-order predictor–corrector algorithm for nonlinear complementarity problems over symmetric cones ⋮ Polynomial complexity of an interior point algorithm with a second order corrector step for symmetric cone programming ⋮ A constraint-reduced variant of Mehrotra's predictor-corrector algorithm ⋮ An \(O(\sqrt nL)\) iteration primal-dual second-order corrector algorithm for linear programming ⋮ A second-order corrector infeasible interior-point method for semidefinite optimization based on a wide neighborhood ⋮ A wide neighborhood predictor-infeasible corrector interior-point algorithm for linear optimization ⋮ A Mehrotra predictor-corrector interior-point algorithm for semidefinite optimization ⋮ A new infeasible Mehrotra-type predictor-corrector algorithm for nonlinear complementarity problems over symmetric cones ⋮ A second-order corrector wide neighborhood infeasible interior-point method for linear optimization based on a specific kernel function ⋮ An adaptive infeasible-interior-point method with the one-norm wide neighborhood for semi-definite programming ⋮ Mehrotra-type predictor-corrector algorithms for sufficient linear complementarity problem ⋮ A Mehrotra-type predictor-corrector infeasible-interior-point method with a new one-norm neighborhood for symmetric optimization ⋮ Some disadvantages of a Mehrotra-type primal-dual corrector interior point algorithm for linear programming ⋮ Infeasible Mehrotra-Type Predictor-Corrector Interior-Point Algorithm for the CartesianP_*(κ)-LCP Over Symmetric Cones ⋮ On complexity of a new Mehrotra-type interior point algorithm for \(P_\ast(\kappa )\) linear complementarity problems ⋮ A New Predictor-corrector Infeasible Interior-point Algorithm for Linear Optimization in aWide Neighborhood ⋮ Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming ⋮ Polynomial convergence of Mehrotra-type predictor–corrector algorithm for the CartesianP_∗(κ)-LCP over symmetric cones ⋮ A new class of polynomial primal-dual methods for linear and semidefinite optimization ⋮ Solving large-scale linear programs by interior-point methods under the Matlab^∗Environment^† ⋮ User'S guide To Lipsol linear-programming interior point solvers V0.4 ⋮ On the convergence of a predictor-corrector variant algorithm

Cites Work

• Unnamed Item
• On the Implementation of a Primal-Dual Interior Point Method
• On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear Programming
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• On the Convergence of a Class of Infeasible Interior-Point Methods for the Horizontal Linear Complementarity Problem
• The Mehrotra Predictor-Corrector Interior-Point Method As a Perturbed Composite Newton Method

This page was built for publication: On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms