Piecewise linear methods for nonlinear equations and optimization

摘要

Piecewise linear methods had their beginning in the mid-1960s with Lemke's algorithm for calculating solutions to linear complementarity problems. In the 1970s and 1980s activity moved on to computing fixed points of rather general maps and economic equilibria. More recently, they have been used to approximate implicitly defined manifolds, with applications being made to computer graphics and approximations of integral over implicitly defined manifolds. In this paper we present the basic ideas of piecewise linear algorithms and a selection of applications. Further references to the literature on piecewise linear algorithms are indicated.