5
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ You have to know something about the function you are investigating because for an arbitrary function there could always be critical points hiding somewhere and there is no tractable way of finding all of them. However, if the function is smooth, for example, you could decide to approximate it and use as many evaluations as necessary to determine the approximation. Once you have a global approximation you have some chance of finding all critical points. It all depends on what you can say about your function. $\endgroup$
    – Amit Hochman
    Mar 31, 2021 at 16:14
  • 3
    $\begingroup$ If the physical system can be described with polynomials, you could try homotopy continuation on the gradient system for some reasonable certainty that you have all the zeros. (Or if it can be approximated by polynomials) $\endgroup$
    – Thijs Steel
    Mar 31, 2021 at 20:50
  • 1
    $\begingroup$ If you're using a local optimizer based on a starting point it might be worthwhile to investigate using a Metropolis-Hastings approach to walk the space of starting points. Good question @G.Fougeron, it'll be interesting to see what advice you get. $\endgroup$
    – A rural reader
    Mar 31, 2021 at 21:17
  • 2
    $\begingroup$ You could try removing the critical points once you’ve found them, for example, by multiplying the gradient by x - x0. That way you avoid finding the same ones more than once. This might mess with the conditioning, but it is a simple thing to try. If this doesn’t work, there might be some more sophisticated way of removing points once you’ve found them. In eigenvalue problems “deflation” methods are such a scheme, for example. $\endgroup$
    – Amit Hochman
    Apr 1, 2021 at 5:26
  • 1
    $\begingroup$ Another possibility (similar to the one suggested by Amit above) is to place a “pole” in the minima you already found - using the same technique as the Tunneling global optimization technique. The pole could be a simple division by (x-x0) or an exponential tunneling function: researchgate.net/publication/… or infinity77.net/global_optimization/ampgo.html $\endgroup$
    – Infinity77
    Apr 1, 2021 at 5:39

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.