An interior point potential reduction algorithm for the linear complementarity problem

DOI10.1007/BF01586054zbMath0764.90083OpenAlexW2062228304MaRDI QIDQ1196718

Yinyu Ye, Nimrod Megiddo, Kojima, Masakazu

Publication date: 16 January 1993

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

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

zbMATH Keywords

linear complementaritysmallest eigenvaluepotential function\(P\)-matrixconvex quadratic minimizationinterior point potential reduction algorithm

Mathematics Subject Classification ID

Quadratic programming (90C20) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (38)

Global convergence in infeasible-interior-point algorithms ⋮ Theoretical convergence of large-step primal-dual interior point algorithms for linear programming ⋮ Extensions of the potential reduction algorithm for linear programming ⋮ On the convergence of two-step modulus-based matrix splitting iteration method ⋮ The convergence of modulus-based matrix splitting iteration methods for implicit complementarity problems ⋮ Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence ⋮ Potential-reduction methods in mathematical programming ⋮ Pivoting in linear complementarity: Two polynomial-time cases ⋮ A quadratically convergent \(\text{O}((\kappa +1)\sqrt n L)\)-iteration algorithm for the \(P_ *(\kappa)\)-matrix linear complementarity problem ⋮ Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems ⋮ A smooth system of equations approach to complementarity problems for frictionless contacts ⋮ Improved error bounds based on \(\alpha (M)\) for the linear complementarity problem ⋮ Complexity analysis of a full-{N}ewton step interior-point method for linear optimization ⋮ Unique end of potential line ⋮ The convergence of a modulus-based matrix splitting iteration method for solving the implicit complementarity problems ⋮ Recent development in computational complexity characterization of Nash equilibrium ⋮ A class of linear complementarity problems solvable in polynomial time ⋮ An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems ⋮ A unified approach to interior point algorithms for linear complementarity problems: A summary ⋮ Comparative analysis of affine scaling algorithms based on simplifying assumptions ⋮ Complexity analysis of a linear complementarity algorithm based on a Lyapunov function ⋮ A little theorem of the big \({\mathcal M}\) in interior point algorithms ⋮ Unnamed Item ⋮ A new polynomial time method for a linear complementarity problem ⋮ The modulus-based matrix double splitting iteration method for linear complementarity problems ⋮ On hidden \(Z\)-matrix and interior point algorithm ⋮ Unnamed Item ⋮ Reformulations in Mathematical Programming: Definitions and Systematics ⋮ Near boundary behavior of primal-dual potential reduction algorithms for linear programming ⋮ Two interior-point methods for nonlinear \(P_*(\tau)\)-complementarity problems. ⋮ An interior point potential reduction method for constrained equations ⋮ A superlinearly convergent projection algorithm for solving the convex inequality problem ⋮ Unique End of Potential Line ⋮ Investigation of path-following algorithms for signomial geometric programming problems ⋮ Interior-point algorithms for global optimization ⋮ On total functions, existence theorems and computational complexity ⋮ An extension of the potential reduction algorithm for linear complementarity problems with some priority goals ⋮ Interior-point methods for linear programming: a review

Cites Work

• A new polynomial-time algorithm for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• A polynomial-time algorithm for a class of linear complementarity problems
• Polynomial affine algorithms for linear programming
• The Jacobian matrix and global univalence of mappings

This page was built for publication: An interior point potential reduction algorithm for the linear complementarity problem