Search code examples
pythonscipymathematical-optimization

What is the difference between scipy.optimize's 'root' and 'fixed_point' methods


There are two methods in scipy.optimize which are root and fixed_point.

I am very surprised to find that root offers many methods, whereas fixed_point has just one. Mathematically the two are identical. They relate the following fixed points of g(x) with the roots of f(x):

[ g(x) = f(x) - x ]

How do I determine which function to use?

Also, none of the two methods allow me to specify the regions where the functions are defined. Is there a way to limit the range of x?


Solution

  • Summary: if you don't know what to use, use root. The method fixed_point merits consideration if your problem is naturally a fixed-point problem g(x) = x where it's reasonable to expect that iterating g will help in solving the problem (i.e., g has some non-expanding behavior). Otherwise, use root or something else.

    Although every root-finding problem is mathematically equivalent to a fixed-point problem, it's not always beneficial to restate it as such from the numerical methods point of view. Sometimes it is, as in Newton's method. But the trivial restatement, replacing f(x) = 0 as g(x) = x with g(x) = f(x) + x is not likely to help.

    The method fixed_point iterates the provided function, optionally with adjustments that make convergence faster / more likely. This is going to be problematic if the iterated values move away from the fixed point (a repelling fixed point), which can happen despite the adjustments. An example: solving exp(x) = 1 directly and as a fixed point problem for exp(x) - 1 + x, with the same starting point:

    import numpy as np
    from scipy.optimize import fixed_point, root
    
    root(lambda x: np.exp(x) - 1, 3)  # converges to 0 in 14 steps
    fixed_point(lambda x: np.exp(x) - 1 + x, 3) # RuntimeError: Failed to converge after 500 iterations, value is 2.9999533400931266
    

    To directly answer the question: the difference is in the methods being used. Fixed point solver is quite simple, it's the iteration of a given function boosted by some acceleration of convergence. When that doesn't work (and often it doesn't), too bad. The root finding methods are more sophisticated and more robust, they should be preferred.