Fabian,
Yes, I agree that overfitting doesn't exactly describe what is happening.
I was meaning to post some additional info I found on this. It's one of Raph Levien's blog post on fitting cubic Bézier curves, (specifically in the section on the solutions for quartic polynominals):
raphlinus.github.io/curves/2021/03/11/bezier-fitting.html
My understanding is that in his case, the degree of the curve (in this example quartic) and the fact that there are two parameters (x-moment and signed area) leads to four minimal solutions that the solver could converge to (not infinite solutions, luckily!). I believe that in Raph's case, three of these will be local minima and only one will be the global minimum, so we cannot be certain of converging to the global minimum if we start at a random position in the parameter space, as you said.
Raph says that one of these solutions (when optimising for x-moment and signed area) may contain a loop. This is a valid solution to these parameters because the area inside the loop has the opposite sign to the outside, so the signed area is still minimised.
Raph says that you can generally reject this solution as the arm length is longer than the others. But my understanding is that you can only do this by calculating multiple solutions and rejecting the one with the extreme arm length. You can only do this if you obtain at least two solutions, and even then both may have issues.
What might be happening is that you're regularly converging to a non-global minimum, but normally it's so similar to the global minimum that it isn't evident in the result. It's only when you converge to the solution with the extreme arm length that you notice an issue.
Grotius,
I think your method of fixing this by applying a tiny offset worked because it meant that the the loop was no longer complete so its signed area was a lot larger. Although likewise, adding this offset could technically break a curve which would have worked without it? But that's most likely an edge case.
Also, slightly off-topic, but there might also be instances where this loop with the extreme arm length is the solution the user intended. For example, the intended path did have this loop, but under-sampling in the CAM software means that points are missing which should explicitly indicate the presence of the loop. But since this information is missing, it's probably better to treat this as a bug, and reaffirm that the trajectory planner may choose a solution which doesn't match the path you intended. The way to get around this is to increase your sampling frequency in your CAM software.
Back on topic, the way I see it is that the most rigorous way to solve this problem is to start from enough locations in the parameter space that you obtain all (or some) of the local minima, meaning you can be certain of having found the global minimum (or be sure enough of being close to it). But this is computationally expensive and harder to predict how long it will take to return its output.
So it's probably better to find shortcuts which make you more certain that if you converge to a single value, it's good enough even if not the global minimum. I think the idea you mentioned of initially fitting lower-order curves should help with this.
It also seems that using the gradient descent method along with the appropriate number of parameters will increase this probability of you finding the global minimum.
But I understand that some of these solutions are antagonistic to making the solver work fast, even if it is in a separate thread.
