5
$\begingroup$

I have a differentiable function $\mathbb{R}^n \to \mathbb{R} $ of several variables $f(x_1,\ldots,x_n)$, whose form I can write down and compute derivatives of. Typically $n = 8$.

The function is unbounded from below, going to negative infinity when some of the variables go to infinity, and also has a few local minima. I can specify a box in $\mathbb{R}^n$ which I know contains all the local minima, however, it also contains regions towards the corners of the box where the function is already smaller than at these local minima (i.e those corners are already on the "cliff" where $f$ falls off to infinity at large values of the inputs).

The problem: I am looking for an efficient algorithm, implemented in Python, to find the value of the inputs $(x_1^*,\ldots,x_n^*)$ corresponding to the smallest value of $f$ amongst these local minima, where I specify the box as my bounds.

Let us assume that the basin of attraction of the local minimum occupies some volume that is an order 1 fraction of the volume of the bounding box - i.e., my guess about the bounds containing the local minima is not too conservative.

Some reflections:

  • Note that a differential optimization algorithm to find the global minimum will not work here, as the global minimum of $f$ within the box is not a local minimum of $f$.

  • One idea is to try $G$ initial guesses within the box, and for each do a gradient descent to find the nearest local minimum, stopping after some number of iterations at points $p_i$ ($i=1,\ldots,G)$. Then, eliminate the points $p_i$ which are too close to the faces of the box (as these won't be the local minima), and amongst the remaining ones, choose the one which gives the smallest $f(p_i)$. The issue is one needs to be smart about how the guesses are made, as a uniform sampling would give a complexity like $m^n$ with $m$ the number of sampling points along a given dimension, and this is prohibitive.

  • Maybe a better idea is to solve the system of $N$ equations $\partial f /\partial x_i = 0 $, which I can write down analytically and express in the form $X = G(X)$, with $X=(x_1,\ldots,x_n)$. This could probably be solved by some iterative method, again with multiple initial guesses, but I am not sure about the details and if convergence is guaranteed.

Improve this question
$\endgroup$
4
  • $\begingroup$ I don't think the question is answerable in its current form, without more information. The problem might be anywhere from easy (if the "basin of attraction" for the best local minimum is very large) to completely intractable (if the "basin of attraction" is tiny). In general, there is no single answer to optimization problems; there are many possible methods for optimization, and picking one depends on the application domain and the properties of $f$. $\endgroup$
    – D.W.
    Commented May 16 at 5:20
  • $\begingroup$ @D.W. sure, while I will avoid specifying the precise form of $f$ here as it is quite complicated, I edited the question to indicate that the basin of attraction occupies an order one fraction of the volume of the bounding box. Does that help narrow down the good search strategies, or should I specify more information? Really any method that could work here, ideally already available through some scientific Python package, would be useful here - looking at scipy's optimization functions, I have not found any that would do the job. $\endgroup$
    – math_lover
    Commented May 16 at 8:06
  • $\begingroup$ Two questions: i) what are you trying to achieve? If you describe your motivation, we might be able to find a better strategy. ii) is your function purely analytical? If so, you might want to give interval methods a try: github.com/JuliaIntervals/IntervalConstraintProgramming.jl $\endgroup$
    – Charlie Vanaret
    Commented May 16 at 10:01
  • $\begingroup$ @CharlieVanaret: the goal is pretty much what I stated in the question - I am trying to find the local minima of $f$, which I know are not global minima, which makes the problem hard (the motivation is from physics: to locate metastable states of a potential which has an unstable minimum at infinity). The function can be written down, but it involves integrals over some variable $u$ , and the $x_i$ appear in the integrand. $\endgroup$
    – math_lover
    Commented May 16 at 19:46

1 Answer 1

Reset to default
6
$\begingroup$

If the "basin of attraction" for the best local minimum occupies 1% of the volume of the bounding box, then the following strategy suffices:

Repeat a few hundred times: Pick a random starting point in the bounding box, use gradient descent starting from there, check if the result is a local minimum, and keep the best one found so far.

There is no need to try exponentially many initializations. Instead, you just need the initialization to fall into the "basin of attraction" for the best local minimum. If there is a 1% chance that a random choice falls there, then after $n$ tries, there is a $(1-1/100)^n\approx e^{-n/100}$ chance you fail to find the best local minimum, so if you take $n=700$, then there is at most a 0.1% chance you fail to find the local minimum.

Improve this answer
$\endgroup$
4
  • $\begingroup$ is there any way to be smarter about the initialization of points for gradient descent? On my small test problem the basin of attraction is indeed something like 1% of the volume of the bounding box, but as I add more dimensions this number goes down. $\endgroup$
    – math_lover
    Commented May 16 at 20:08
  • 1
    $\begingroup$ @math_lover, I don't know. It might depend on the properties and structure of $f$. Optimization tends to be harder in high dimensions... $\endgroup$
    – D.W.
    Commented May 16 at 20:22
  • 3
    $\begingroup$ If you know that samples near the boundaries of the boxes are more likely to yield erroneous minima then you can sample from a distribution with more measure towards the center of the box. This obviously introduces central bias, but if you only care about local minima and already know that the edges are bad then this seems fine $\endgroup$
    – whpowell96
    Commented May 16 at 21:53
  • $\begingroup$ I like this approach - I am doing pretty much the same thing with Nelder-Mead - it makes a surprisingly good global optimizer ;) $\endgroup$
    – m4r35n357
    Commented May 20 at 14:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.