MATLAB Answers

0

What starting point to choose so fsolve always returns a solution when any exists?

Asked by Richárd Tóth on 4 Oct 2019
Latest activity Edited by John D'Errico
on 4 Oct 2019
Hello
I want to check if a circle/sphere has any intersection point with a curve/surface.
I did some experiment on this, but on some starting point it doesn't find solution, while it finds on others.
Can I choose such a starting point so that fsolve will always find a solution if there is any? Maybe the center of the circle/sphere?

  2 Comments

I have a reason why I need this, so let's focus on the question

Sign in to comment.

Tags

3 Answers

Answer by John D'Errico
on 4 Oct 2019
Edited by John D'Errico
on 4 Oct 2019
 Accepted Answer

I tend to describe tools like fsolve with a metaphor of a blind man set down on the surface of the earth, then tasked with finding the lowest point in elevation. All I allow him is a cane to see which direction is locally downhill (along with a full set of scuba gear.)
In the case of fsolve, you are effectively asking the person to actually find a point that lies at a SPECIFIC elevation for multiple equations, and to solve all of them at once.
What happens is the solver can sometimes get stuck in a local valley, but one that does not lead to a solution. Or, it may diverge to a bad place, always moving in a direction that looks like it may be good, but in reality, going noplace good.
In these degenerate cases, nothing magical can be done. You just needed to start in a better place. And since every problem will be different, there is no perfect set of starting values that will always get you to a solution.
Once approach that can help is to use multi-start techniques, where the solver is started multiple tmimes from random start points in the domain of interest. Even though one or more of them may fail, one hopes that at least one start point will be a good choice. This is still not a perfect solution of course, but if can highly improve your chances of a valid solution being found. Other approaches are to use tools like GA, simulated annealing, PSO, etc. These stochastic solvers can often survive a bad problem.
However no solver is perfect, ALL the time. One can always provide a problem that will blow any specific solver out of the water. The solution there is often to understand the various tools, to know how they can fail so you will recognize failure when you see it, and to know which solvers can work better on specific problems.

  0 Comments

Sign in to comment.


Answer by Matt J
on 4 Oct 2019
Edited by Matt J
on 4 Oct 2019

Can I choose such a starting point so that fsolve will always find a solution if there is any? Maybe the center of the circle/sphere?
There is no way to choose the starting point in a way that is independent of the surface. It is the shape of your surface that will determine where the local minima (which you wish to avoid) lie.

  0 Comments

Sign in to comment.


Answer by Bjorn Gustavsson on 4 Oct 2019

This depends on how you have parameterized your surface. For the most general case (curve - circle), where you have a curve parameterized as: and you want to know if it intersects a circle , this is difficult, if you don't have a simple way of determining t for a point on the curve, or determining how far a point is from the curve.
Looking at this from the most tricky angle given the information you've presented any arbitrarily selected starting-point on the curve might have a large number of very steep local minima in the distance to the nearest point on the circle, so any distance minimization algorithm might have convergence conditions making it give up a search.
If you give more information about the character of the curve/surface answer might change to more useful.

  0 Comments

Sign in to comment.