On the computational complexity of piecewise-linear homotopy algorithms

DOI10.1007/BF01585104MaRDI QIDQ4749612zbMATH OpenOpenAlexFDO

Authors 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 complexityexponential growthfixed point algorithmlinear complementarity problempiecewise linear homotopy algorithmsolutions nonlinear equations

Mathematics Subject Classification ID

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

Cites work

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

Cited in

(5)

• Rudiments of an average case complexity theory for piecewise-linear path following algorithms
• 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
• Exponential lower bounds for finding Brouwer fixed points

Describes a project that uses

Uses Software

• PLALGO

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4749612)