A finite improvement algorithm for the linear complementarity problem
From MaRDI portal
The authors consider the linear complementarity problem (LCP) \[ Iw- Mz=q,\quad w\geq 0,\quad z\geq 0,\quad w^ Tz=0, \] where M is an \(n\times n\) real matrix, q is an n-dimensional real vector and I is the \(n\times n\) identity matrix. The authors present an algorithm similar to the simplex method in the sense that it moves between basic points of an associated system of linear equations. Computational comparisons are presented. Also, classes of matrices are characterized for which the algorithm processes LCP for every matrix M in the class and every vector q.
Recommendations
- An Infeasible-Interior-Point Method for Linear Complementarity Problems
- A polynomial-time algorithm for a class of linear complementarity problems
- AN O(n^3L) ALGORITHM USING A SEQUENCE FOR A LINEAR COMPLEMENTARITY PROBLEM
- A rapid algorithm for a class of linear complementarity problems
- scientific article; zbMATH DE number 1326028
Cites work
- A finite descent theory for linear programming, piecewise linear convex minimization, and the linear complementarity problem
- A Least-Element Theory of Solving Linear Complementarity Problems as Linear Programs
- A matrix structural theory of piecewise linear elastoplasticity with interacting yield planes
- A New and Efficient Algorithm for a Class of Portfolio Selection Problems
- A Parametric Linear Complementarity Technique for Optimal Portfolio Selection with a Risk-Free Asset
- A Partial Characterization of a Class of Matrices Defined by Solutions to the Linear Complementarity Problem
- A Partition Theorem for Euclidean n-Space
- A Probelm in Linear Inequalities
- A variable dimension algorithm for the linear complementarity problem
- An algorithm for a piecewise linear model of trade and production with negative prices and bankruptcy
- Bimatrix Equilibrium Points and Mathematical Programming
- Characterization of linear complementarity problems as linear programs
- Characterizations of bounded solutions of linear complementarity problems
- Complementary pivot theory of mathematical programming
- Computational complexity of complementary pivot methods
- Equilibrium Points of Bimatrix Games
- Generalized equations and their solutions, Part I: Basic theory
- Generalized upper bounding techniques
- scientific article; zbMATH DE number 3212891 (Why is no real title available?)
- scientific article; zbMATH DE number 3308846 (Why is no real title available?)
- Linear complementarity problems solvable by A single linear program
- More with the Lemke complementarity algorithm
- On a class of least-element complementarity problems
- On Quadratic Programming
- On solving linear complementarity problems as linear programs
- On the number of solutions to the complementarity problem and spanning properties of complementary cones
- On the solution of some (parametric) linear complementarity problems with applications to portfolio selection, structural engineering and actuarial graduation
- The Linear Complementarity Problem
Cited in
(15)- A short proof of finiteness of Murty's principal pivoting algorithm
- Solving more linear complementarity problems with Murty's Bard-type algorithm
- A new pivoting algorithm for the linear complementarity problem allowing for an arbitrary starting point
- Projective algorithms for solving complementarity problems
- Using vector divisions in solving the linear complementarity problem
- A fast algorithm for solving a class of the linear complementarity problem in a finite number of steps
- scientific article; zbMATH DE number 432996 (Why is no real title available?)
- Least squares with inequality restrictions: a symmetric positive-definite linear complementarity problem algorithm
- On processability of Lemke's algorithm
- Solving the Linear Complementarity Problem in Circuit Simulation
- Solving strongly monotone linear complementarity problems
- A Finite Algorithm for Almost Linear Complementarity Problems
- Improved algorithms for linear complementarity problem arising from collision response
- A constrained optimization approach to solving certain systems of convex equations
- On a ``stability in the linear complementarity problem
This page was built for publication: A finite improvement algorithm for the linear complementarity problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1823161)
