A new polynomial time method for a linear complementarity problem

DOI10.1007/BF01580891zbMath0769.90077OpenAlexW2008062072MaRDI QIDQ1207309

Shinji Mizuno

Publication date: 1 April 1993

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

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

zbMATH Keywords

linear complementaritypotential reduction methodpolynomial time method

Mathematics Subject Classification ID

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

A new method for a class of linear variational inequalities ⋮ Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence ⋮ Fast convergence of the simplified largest step path following algorithm ⋮ 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 ⋮ Primal-dual target-following algorithms for linear programming ⋮ An interior-exterior approach for convex quadratic programming ⋮ An \(O(n^ 3L)\) adaptive path following algorithm for a linear complementarity problem ⋮ A little theorem of the big \({\mathcal M}\) in interior point algorithms ⋮ General central path and the largest step general central path following algorithm for linear programming ⋮ Infeasible predictor-corrector interior-point method applied to image restoration in the presence of noise ⋮ Primal-dual-infeasible Newton approach for the analytic center deep-cutting plane method ⋮ Perturbed path following predictor-corrector interior point algorithms ⋮ O(n\({}^ pL)\)-iteration and \(O(n^ 3L)\)-operation potential reduction algorithms for linear programming

Cites Work

• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• Interior path following primal-dual algorithms. I: Linear programming
• A polynomial-time algorithm for a class of linear complementarity problems
• An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
• Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
• An interior point potential reduction algorithm for the linear complementarity problem
• Complementary pivot theory of mathematical programming
• A Centered Projective Algorithm for Linear Programming
• PRACTICAL POLYNOMIAL TIME ALGORITHMS FOR LINEAR COMPLEMENTARITY PROBLEMS
• Bimatrix Equilibrium Points and Mathematical Programming

This page was built for publication: A new polynomial time method for a linear complementarity problem