Homotopy method

Last updated

The homotopy method is a method for fixed-point computation, based on the mathematical concept of homotopy. The method was devised in 1972 by B. Curtis Eaves. [1]

Contents

Given a function f, for which we want to find a fixed point, the algorithm works by starting with an affine function that approximates f, and deforming it towards f while following the fixed point.

Applications

The homotopy method has been used for market equilibrium computation. [2]

Further reading

The method is further explained in a book by Michael Todd, [3] which surveys various algorithms developed until 1976.

References

  1. Eaves, B. Curtis (December 1972). "Homotopies for computation of fixed points". Mathematical Programming. 3–3 (1): 1–22. doi:10.1007/BF01584975. S2CID   39504380.
  2. Codenotti, Bruno; Pemmaraju, Sriram; Varadarajan, Kasturi (2004-12-01). "The computation of market equilibria" . SIGACT News. 35 (4): 23–37. doi:10.1145/1054916.1054927. ISSN   0163-5700.
  3. The Computation of Fixed Points and Applications. Lecture Notes in Economics and Mathematical Systems. Vol. 124. 1976. doi:10.1007/978-3-642-50327-6. ISBN   978-3-540-07685-8.