Briefly stated, I would like to find "all" local minima / critical points of a function.
This function comes from the discretization of a continuous problem with infinitely many degrees of freedom (dofs), but after discretization, there remains actually rather "few" dofs. Let's say, n_dof ~ 1000 - 10k.
This function (let's denote it $S$) is a discretization of the action of a physical system. Glossing over some details, saying that a set of parameters $x$ "follow the rules of physics" is equivalent to saying that "$x$ is a critical point of $S$", i.e. " $\nabla S (x) = 0$". Since local minima are critical points, which might be easier to find numerically, I would also be happy with answers specifically addressing minima.
I would qualify my current approach as "Monte-Carlo like". It can be summed up as :
- I first designed an efficient way to find a nearby critical point from a given estimate, using Newton-like methods, dealing with conditioning, etc.
- I then randomly select starting points for the algorithm, and apply the above "local" method to find a critical point
- I then check the newly found critical point against my database of already found points. If it is unknown, I add it to the database, else I start over.
Although this method is very easy to implement, it offers little theoretical guarantees. I don't know how many critical points "remain to be found" (say, within a compact set of parameters). In practice, the local method very often converges towards points that were already found (this morning : 100k initial guesses => 50 unique critical points). I don't know when to stop the algorithm, or what would be the expectation of finding a new critical point in less than a given number of iterations.
Do you have any suggestion on how to find more unique critical points / all critical points ?
Remark: I think there might be links to Morse theory which I know only little about.