An algorithm for the linear complementarity problem with upper and lower bounds
type: Item
instance of: scholarly article
title: An algorithm for the linear complementarity problem with upper and lower bounds
zbMATH Open document ID: 0651.90086
DOI: 10.1007/BF00939635
author: Gerard van der Laan
author: Dolf Talman
published in: Journal of Optimization Theory and Applications
publication date: 1989-01-01T00:00:00Z
review text: We adapt the octahedral simplicial algorithm for solving systems of nonlinear equations to solve the linear complementarity problem with upper and lower bounds. The proposed algorithm generates a piecewise linear path from an arbitrarily chosen point \(z^ 0\) to a solution point. This path is followed by linear programming pivot steps in a system of n linear equations, where n is the size of the problem. The starting point \(z^ 0\) is left in the direction of one of the \(2^ n\) vertices of the feasible region. The ray along which \(z^ 0\) is left depends on the sign pattern of the function value at \(z^ 0\). The sign pattern of the linear function and the location of the points in comparison with \(z^ 0\) completely govern the path of the algorithm.
Mathematics Subject Classification ID: 90C33
Mathematics Subject Classification ID: 65H10
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 4062854
zbMATH Keywords: pivoting algorithm
zbMATH Keywords: arbitrary starting point
zbMATH Keywords: octahedral simplicial algorithm
zbMATH Keywords: systems of nonlinear equations
zbMATH Keywords: upper and lower bounds
MaRDI profile type: Publication
cites work: Bimatrix Equilibrium Points and Mathematical Programming
cites work: Q3330405
cites work: A class of simplicial restart fixed point algorithms without an extra dimension
cites work: A Modified Integer Labeling for Complementarity Algorithms
cites work: The octahedral algorithm, a new simplicial fixed point algorithm
cites work: Even more with the Lemke complementarity algorithm
full work available at URL: https://doi.org/10.1007/bf00939635
OpenAlex ID: W2111274455
description: scientific article; zbMATH DE number 4062854