The Solution of Systems of Piecewise Linear Equations

DOI10.1287/MOOR.1.1.1zbMath0458.65056OpenAlexW2062780857MaRDI QIDQ3908415

Herbert E. Scarf, B. Curtis Eaves

Publication date: 1976

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

Full work available at URL: https://cowles.yale.edu/sites/default/files/files/pub/d03/d0390.pdf

zbMATH Keywords

fixed pointsparametric programmingpath followingcomplementarityconvex polyhedrapiecewise linearcomplementary pivot algorithms

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Numerical computation of solutions to systems of equations (65H10) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items (56)

On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials ⋮ Pivotal methods for computing equilibrium points: Unified approach and new restart algorithm ⋮ Parametric fixed point algorithms with applications to economic policy analysis ⋮ The Homotopy Continuation Method: Numerically Implementable Topological Procedures ⋮ Homotopy techniques in linear programming ⋮ Constructing pure-exchange economies with many equilibria ⋮ On the efficiency of algorithms of analysis ⋮ Finding Zeroes of Maps: Homotopy Methods That are Constructive With Probability One ⋮ A new simple homotopy algorithm for linear programming. I ⋮ On the geometry of paths generated by PL homotopy methods ⋮ A New and Constructive Proof of the Borsuk-Ulam Theorem ⋮ Notes on computation of Kakutani fixed points ⋮ An \((m+1)\)-step iterative method of convergence order \((m+2)\) for linear complementarity problems. An \((m+1)\)-step iterative method for LCPs ⋮ Complementarity in Oriented Matroids ⋮ Nonlinear input-output model with piecewise affine coefficients ⋮ Computation of equilibrium values in the Baron and Ferejohn bargaining model ⋮ A globally convergent algorithm for computing fixed points of \(C^2\) maps ⋮ Characterizing total positivity: Single vector tests via linear complementarity, sign non‐reversal and variation diminution ⋮ A generalized Newton method of high-order convergence for solving the large-scale linear complementarity problem ⋮ Matrices and the linear complementarity problem ⋮ Complementary pivoting and the Hopf degree theorem ⋮ Engineering applications of the Chow-Yorke algorithm ⋮ Regular production economies ⋮ An accelerated Newton method of high-order convergence for solving a class of weakly nonlinear complementarity problems ⋮ Foreword. What is numerical algebraic geometry? ⋮ Computing Nash equilibria by iterated polymatrix approximation ⋮ Uniqueness of equilibrium for smooth multistage concave games ⋮ On generalizing shapley's index theory to labelled pseudomanifolds ⋮ Simulated annealing and its application to cobb-douglas economic model ⋮ On the average number of steps of the simplex method of linear programming ⋮ Constructive proofs of theorems relating to:F(x) = y, with applications ⋮ Computation of equilibria in an economy with increasing returns to scale technologies ⋮ A quadratically-convergent fixed-point algorithm for economic equilibria and linearly constrained optimization ⋮ A convergent process of price adjustment and global Newton methods ⋮ A finite steepest-ascent algorithm for maximizing piecewise-linear concave functions ⋮ Exploiting structure in piecewise-linear homotopy algorithms for solving equations ⋮ A variable dimension algorithm for the linear complementarity problem ⋮ On the enumeration of subcells within hypercubes and its application to the Borsuk-Ulam theorem ⋮ A note on a theorem of Yamamuro ⋮ A PL homotopy for finding all the roots of a polynomial ⋮ A simplicial approach for discrete fixed point theorems ⋮ A geometrical interpretation of the without-exception feasibility of PL homotopy methods ⋮ The fundamental theorem of algebra and complexity theory ⋮ Solving generalized equations via homotopies ⋮ On the expected number of linear complementarity cones intersected by random and semi-random rays ⋮ Piecewise linear paths to minimize convex functions may not be monotonic ⋮ Finding all solutions to polynomial systems and other systems of equations ⋮ Computation of all solutions to a system of polynomial equations ⋮ Variable dimension algorithms: Basic theory, interpretations and extensions of some existing methods ⋮ On the computational complexity of piecewise-linear homotopy algorithms ⋮ Oriented Euler complexes and signed perfect matchings ⋮ Computing all of the equilibria of economies with two factors of production ⋮ The relation between the path of centers and Smale's regularization of the linear programming problem ⋮ On stable piecewise linearization and generalized algorithmic differentiation ⋮ A variable dimension fixed point algorithm and the orientation of simplices ⋮ A new variable dimension algorithm for the fixed point problem

This page was built for publication: The Solution of Systems of Piecewise Linear Equations