A Fully Polynomial-Time Approximation Algorithm for Computing a Stationary Point of the General Linear Complementarity Problem

DOI10.1287/moor.18.2.334zbMath0791.90060OpenAlexW2008774137WikidataQ92953125 ScholiaQ92953125MaRDI QIDQ5287986

Yinyu Ye

Publication date: 5 August 1993

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.18.2.334

zbMATH Keywords

linear complementaritypolynomial-time approximation schemepotential reduction algorithm\(\varepsilon\)-approximate stationary pointpolynomal-time algorithm

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

A modified damped Gauss–Newton method for non-monotone weighted linear complementarity problems ⋮ The convergence of the modulus-based Jacobi (MJ) iteration method for solving horizontal linear complementarity problems ⋮ On the extended linear complementarity problem ⋮ On the complexity of approximating a KKT point of quadratic programming ⋮ Sensor fault detection and isolation via networked estimation: rank-deficient dynamical systems ⋮ Algorithms for linear programming with linear complementarity constraints ⋮ A dynamic model to solve weighted linear complementarity problems ⋮ A new interior-point algorithm based on modified Nesterov-Todd direction for symmetric cone linear complementarity problem ⋮ Local uniqueness of solutions to the extended linear complementarity problem ⋮ A smoothing Gauss-Newton method for the generalized HLCP ⋮ A proximal gradient descent method for the extended second-order cone linear complementarity problem ⋮ On convergence of the modulus-based matrix splitting iteration method for horizontal linear complementarity problems of \(H_+\)-matrices ⋮ Approximate Equilibria for Strategic Two Person Games ⋮ Quadratic convergence analysis of a nonmonotone Levenberg-Marquardt type method for the weighted nonlinear complementarity problem ⋮ On the solution of the extended linear complementarity problem ⋮ An interior point potential reduction method for constrained equations ⋮ A class of smoothing functions for nonlinear and mixed complementarity problems ⋮ On the equivalence of linear complementarity problems

This page was built for publication: A Fully Polynomial-Time Approximation Algorithm for Computing a Stationary Point of the General Linear Complementarity Problem