A finite improvement algorithm for the linear complementarity problem
type: Item
instance of: scholarly article
title: A finite improvement algorithm for the linear complementarity problem
zbMATH Open document ID: 0679.90083
DOI: 10.1016/0377-2217(89)90168-9
author: Konstantinos Paparrizos
author: Daniel Solow
published in: European Journal of Operational Research
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C33
Mathematics Subject Classification ID: 90C30
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 4114416
zbMATH Keywords: piecewise linear functions
zbMATH Keywords: simplex-like algorithm
zbMATH Keywords: linear complementarity
zbMATH Keywords: Computational comparisons
reviewed by: Dorel I. Duca
MaRDI profile type: Publication
full work available at URL: 0377-2217(89)90168-9
OpenAlex ID: W1965005791
cites work: Complementary pivot theory of mathematical programming
cites work: On solving linear complementarity problems as linear programs
cites work: A Least-Element Theory of Solving Linear Complementarity Problems as Linear Programs
cites work: Generalized upper bounding techniques
cites work: An algorithm for a piecewise linear model of trade and production with negative prices and bankruptcy
cites work: A Partial Characterization of a Class of Matrices Defined by Solutions to the Linear Complementarity Problem
cites work: The Linear Complementarity Problem
cites work: On Quadratic Programming
cites work: More with the Lemke complementarity algorithm
cites work: Q5340130
cites work: A Probelm in Linear Inequalities
cites work: Bimatrix Equilibrium Points and Mathematical Programming
cites work: Equilibrium Points of Bimatrix Games
cites work: Q5589748
cites work: Characterizations of bounded solutions of linear complementarity problems
cites work: Linear complementarity problems solvable by A single linear program
cites work: Characterization of linear complementarity problems as linear programs
cites work: On the number of solutions to the complementarity problem and spanning properties of complementary cones
cites work: Computational complexity of complementary pivot methods
cites work: A matrix structural theory of piecewise linear elastoplasticity with interacting yield planes
cites work: On a class of least-element complementarity problems
cites work: A New and Efficient Algorithm for a Class of Portfolio Selection Problems
cites work: A Parametric Linear Complementarity Technique for Optimal Portfolio Selection with a Risk-Free Asset
cites work: On the solution of some (parametric) linear complementarity problems with applications to portfolio selection, structural engineering and actuarial graduation
cites work: Generalized equations and their solutions, Part I: Basic theory
cites work: A Partition Theorem for Euclidean n-Space
cites work: A finite descent theory for linear programming, piecewise linear convex minimization, and the linear complementarity problem
cites work: A variable dimension algorithm for the linear complementarity problem
description: scientific article; zbMATH DE number 4114416