On the computational complexity of piecewise-linear homotopy algorithms

DOI10.1007/BF01585104zbMath0509.90071OpenAlexW2079908347MaRDI QIDQ4749612

Michael J. Todd

Publication date: 1982

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01585104

zbMATH Keywords

computational complexitylinear complementarity problemexponential growthfixed point algorithmpiecewise linear homotopy algorithmsolutions nonlinear equations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Nonlinear programming (90C30) Numerical computation of solutions to systems of equations (65H10) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Fixed-point and coincidence theorems (topological aspects) (54H25)

Related Items (5)

Rudiments of an average case complexity theory for piecewise-linear path following algorithms ⋮ Exponential lower bounds for finding Brouwer fixed points ⋮ General equilibrium models and homotopy methods ⋮ Computational complexity of a piecewise linear homotopy algorithm ⋮ Computational complexity of Van der Heyden's variable dimension algorithm and Dantzig-Cottle's principal pivoting method for solving LCP's

Uses Software

• PLALGO

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Observations on a class of nasty linear complementarity problems
• The computation of fixed points and applications
• Computational complexity of LCPs associated with positive definite symmetric matrices
• Simplicial and Continuation Methods for Approximating Fixed Points and Solutions to Systems of Equations
• Traversing Large Pieces of Linearity in Algorithms that Solve Equations by Following Piecewise-Linear Paths
• A class of simplicial restart fixed point algorithms without an extra dimension
• The Solution of Systems of Piecewise Linear Equations
• The octahedral algorithm, a new simplicial fixed point algorithm
• On Paths Generated by Fixed Point Algorithms
• Computational complexity of complementary pivot methods
• Improving the convergence of fixed-point algorithms
• Homotopies for computation of fixed points
• An Algorithm for Solving Nonlinear Resistor Networks
• Homotopies for computation of fixed points on unbounded regions

This page was built for publication: On the computational complexity of piecewise-linear homotopy algorithms