4

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?

Leokins
  • 89
  • 11
DerWeh
  • 1,721
  • 1
  • 15
  • 26
  • 1
    One question per question, please. The second one is covered by [Bounded root finding in scipy](https://stackoverflow.com/q/32814173) with the conclusion: use constrained minimization [`least_squares`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.least_squares.html#scipy.optimize.least_squares) –  Jul 09 '18 at 19:45

1 Answers1

7

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.

  • Thanks for the good answer. I understand, that numerical differences exist, I am however no really sure what **naturally** really means. The problems are equivalent, how could I know what the right formulation is? My guess would be that the natural thing is self-consistency, so I guess everything should be a fixed point. I will just give it a try, to see if it performs better. – DerWeh Jul 10 '18 at 07:35
  • 1
    I expanded the answer. The executive summary would be: if you don't know what to use, use `root`. –  Jul 10 '18 at 12:31
  • Thanks a lot, now it is way more clear to me. From what I have heard, the more *sophisticated* algorithms often have problems for a very large number of degrees of freedom as well es noisy data. In these cases `fixed_point` might be a better approach according to your answer. Thanks a lot. – DerWeh Jul 11 '18 at 11:05