Basins of attraction and Newtons Method

Hi, any idea how to generate basins of attraction of non-differentiable systems? That is it contains abs or max functions. Thanks

Answer 1

[John D'Errico]

Since this is clearly homework, and we don't do homework for people on this site, think about it!

First, you almost always want to plot EVERYTHING. This is my most important rule: Plot everything. Look at what you see. Think about what you just saw.

There are two cases I can see off the top of my head. If the problem is a black box, where all you know is the problem MAY be non-differentiable, then all you can do is to start the optimizer at multiple points, and see what happens. You will then cluster the results based loosely on any tolerances provided, since no two solves need return the exact same solution.

If the problem is not a black box, so you can see the equations, the problem becomes subtly different, and possibly harder or sometimes easier. Now you can look for the points of non-differentiability, information which MAY help you. For example, consider the function

fun= @(x) (x+2).^3/10 - 2*x.^2 + 10*abs(x-3);
fplot(fun,[-10,10])
xline(3);
grid on

Pretty simple. at least visually. If we need to minimize this function, then most optimizers will converge to one of two solutions, at x==-inf, or x==3. Remember that not ALL optimizers behave the same. They can have subtly different basins of attraction, and basins need not be contiguous sets.

But generally, a simple optimizer will converge to the solution at x==3 whenever the start point is greater than roughly 2.5, and diverge to -inf for start points less than that.

Could you have inferred those basins analytically, KNOWING the function? Again, this is difficult. Consider the optimizer fminsearch. If we start the optimizer near x=2.5, depending on the size of the initial polytope, then it might diverge to -inf or converge to 3, and it will depend on EXACTLY where the points for that initial simplex lie.

Or, consider a newton-like method that uses the gradient at a point to decide where to look next. If we start at x==5, then it will depend on the length of the first step it takes. And therefore all of this comes down to the design of the line search scheme used in the optimizer.

So depending on the optimizer, the basins of attraction can be very different. Again, you may find it simplest to just start the optimizer out at various points and then cluster the results.

And no, I won't write code for any of this.

[Marek Lampart]

Thank you for your kind response, it was not homework. All you mentioned is straightforward, I was wondering if there is some tricky way to simplify the situation while dealing with 3D maps. That is probably not known to you.

[John D'Errico]

Is there some tricky way? No. It is not even if is is not known. There is no tricky way, and that is a provable statement.

Answer 2

[Walter Roberson]

https://en.wikipedia.org/wiki/Newton%27s_method#Discontinuous_derivative

If the derivative is not continuous at the root, then convergence may fail to occur in any neighborhood of the root. Consider the function

It seems to me that it follows that with your discontinuous derivatives (because of the abs() or max()) then there are areas near the discontinuities where there might not be basins of attraction. Basins of divergence, perhaps.

But... Newton's method requires that you use the derivative as part of the calculation. That might be manageable for abs() of real values as long as you do not evaluate right at the zero of the expression, but how are you going to take the derivative of max() in a meaningful way?

[Marek Lampart]

Thank you for your kind response and notes. In the case of abs() you can think about one-sided derivatives. In the case of max(), you can easily imagine the situation where relevant Dini's numbers are not equal, hence one-sided derivatives do not exist. So, there is no way to think about this problem using the analogous Newton-Raphson method. I agree with @John D'Errico comment - there is no tricky way. Thank you for your advice.