Empirical Optimization with Divergent Fixed Point Algorithm — When All Else Fails
While the technique discussed here is a last resort solution when all else fails, it is actually more powerful than it seems at first glance. First, it also works in standard cases with “nice” functions. However, there are better methods when the function behaves nicely, taking advantage of the differentiability of the function in question, such as the Newton algorithm (itself a fixed-point iteration). It can be generalized to higher dimensions, though I focus on univariate functions here.
Perhaps the attractive features are the fact that it is simple and intuitive, and quickly leads to a solution despite the absence of convergence. However, it is an empirical method and may require working with different parameter sets to actually find a solution. Still, it can be turned into a black-box solution by automatically testing different parameter configurations. In that respect, I compare it to the empirical elbow rule to detect the number of clusters in unsupervised clustering problems. I also turned the elbow rule into a fully automated black-box procedure, with full details offered in the same book.
Why would anyone be interested in an algorithm that never converges to the solution you are looking for? This version of the fixed-point iteration, when approaching a zero or an optimum, emits a strong signal and allows you to detect a small interval likely to contain the solution: the zero or global optimum in question. It may approach the optimum quite well, but subsequent iterations do not lead to convergence: the algorithm eventually moves away from the optimum, or oscillates around the optimum without ever reaching it. It works with highly chaotic functions such as the one in red in the picture. The first step is to use a transformation.
Read more, get the full PDF document and Python code here (12 pages, free, no subscription required). You will see how I use synthetic data to test the procedure on random functions that mimic the real case pictured in the image.
