Given an arbitrary multivariate function $f(x)$ in $\mathbb{R}^n$ I was wondering if there is any method of distinguishing between a local minimum and a global minimum given you already have a point at which $f'(x)=0$ and $f''(x) > 0$. I believe its an unsolvable problem but I'm not sure, perhaps there's an approach from Calculus of Variation?

  • $\begingroup$ If you know $f$ is convex then you know a critical point is a minimizer. If $f$ is not convex, but is differentiable then you can find all the critical points and compare the values of the function at the critical points (if the function is twice-differentiable you might use the second-derivative test to reduce the number of critical points to compare). $\endgroup$ – smcc Nov 6 '18 at 10:33
  • $\begingroup$ I was talking about a function where the total amount of critical points is unknown. (The minimums are found through gradient descent of either a spiking or artificial neural network). And I was hoping there is a method of distinguishing between local and global minimas/maximas without knowing all the possible minimum and maximum values of $x$. $\endgroup$ – John Miller Nov 6 '18 at 11:57
  • $\begingroup$ If you find a smaller value of the function, you know the minimum you found is not local. To know that a local minimum is global, you have to somehow rule out the existence of any deeper "valley" anywhere in the function. I don't see how to do that without having some idea how many critical points there are. $\endgroup$ – David K Nov 6 '18 at 13:33
  • 1
    $\begingroup$ Some kind of Monte-Carlo based approach might work to find the global minimum in a region with certain probability. Imagine diffusion of particles on a potential landscape defined by your function. If you increase the "temperature", the particles won't be able to settle in local minima forever, and will mostly congregate in the global one. Of course, this method will make mistakes when there are minima close in value to the global one $\endgroup$ – Yuriy S Nov 6 '18 at 18:28
  • 1
    $\begingroup$ Given an arbitrary function, you are doomed. What if the function is $x^2$ everywhere except at $\pi$ where the value is $-1$. You would never be able to find that point $\endgroup$ – Johan Löfberg Nov 6 '18 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.