7
$\begingroup$

There are many interesting methods of searching for a global minimum of a complicated function of many variables, based on physical/biological analogies. For example, particle swarm optimization and evolutionary algortithms, both of which are stochastic and simulate behaviour of large populations (in this case, populations of solutions).

I've got an idea for another stochastic optimization method, based in physical reality. Let's say we need to minimize a function:

$$y=f(x_1,x_2,\dots,x_n)$$

Let's say the function is continuous and all of its partial derivatives are at least piecewise continuous.

Then let's consider the $(n+1)$-dimensional Cartesian space, with coordinates $$x_1,\dots,x_n,y$$

The idea is to simply turn on "gravity" along the $y$ coordinate and put a ball at a random position inside the region of $x_1,\dots,x_n$ we are searching on (making sure that it's high enough above the surface defined by $y=f(x_1,x_2,\dots,x_n)$, which we can do if the region is finite and the function is nice enough).

So we have three main parameters to set:

  • the "gravitation potential" $g$

  • the coefficient of restitution $c$

  • the initial height of the ball $y_0$ (or some interval of heights, if we want).

Then we just let the ball drop and bounce around on the surface according to the usual laws of classical mechanics, until it loses enough energy and settles down or the time limit is reached.

Then we write down the coordinates where it's settled and initiate another ball. It seems to follow from physical principles that eventually we find the global minimum of the function inside the region we considered as an average of the balls' final positions. (Note: as Brian Borchers pointed out in the comments, the best course of action would be just keeping the best result and using it).

My questions are:

Is this method doable? Are there any problems with the steps I suggested?

Is this method already used in some optimization schemes (or a close enough method)? If so, I would like some references, since I haven't been able to find anything myself.

$\endgroup$
  • 2
    $\begingroup$ averaging the balls final positions is clearly not the right thing to do. If there are two equally likely global minimum points $A$ and $B$, then you'd pick $(A+B)/2$, where the function might be higher than either $A$ or $B$. $\endgroup$ – Brian Borchers Jan 19 '18 at 4:06
  • $\begingroup$ @BrianBorchers, thank you for the comment, I agree that for such cases average would not be suitable. What would you recommend? I think just building a histogram of positions should do the trick for small number of minima $\endgroup$ – Yuriy S Jan 19 '18 at 9:45
  • 1
    $\begingroup$ Generally in stochastic search algorithms you keep track of the best solution seen so far and report that at the end. $\endgroup$ – Brian Borchers Jan 19 '18 at 14:51
  • $\begingroup$ In the same vein (using a physics analogy for optimization, and similarly to using gravity), consider simulated annealing: en.wikipedia.org/wiki/Simulated_annealing $\endgroup$ – Solomonoff's Secret Jan 21 '18 at 2:55
  • 1
    $\begingroup$ The difference between this and standard gradient descent seems to be the "bounce" aspect. You could compute the trajectory of the bounce based on the velocity/direction at time of impact, and the gradient of the function at the impact point. But the hard part seems to be finding where that trajectory hits the function again (i.e., finding the next impact point). A related technique might be a "line search" type method that searches over a line defined by the gradient (not necessarily over a small stepsize). $\endgroup$ – Michael Jan 21 '18 at 22:32
3
+50
$\begingroup$

The method you talk about reminds me gradient descent (GD).

This method is very good for convex problems. But consider cost functions such as De Jong 5 or Rastrigin with a lot of local minima. A single agent can barely find the global minima. This is why GA is popular for non-convex applications.

If you are interested, you can have a look at hybrid methods using both GA and GD [1], [2], [3], [4] (I personally have not read these papers).

Keep in mind, there is a trade-off between speed of convergence and the chance of falling in a local minima. There are so many methods proposed. None of them is better than GA in every aspect for general purpose but they have prones and cons.

$\endgroup$
  • $\begingroup$ Thank you for the answer, but this is not actually gradient descent, it's rather more complicated $\endgroup$ – Yuriy S Jan 21 '18 at 2:46
  • $\begingroup$ @YuriyS, I cannot pick it. Would you please highlight the difference? $\endgroup$ – Arash Jan 21 '18 at 6:21
  • $\begingroup$ @ ArashMohammadi, in this case we are not just making discrete steps along the gradient, we are computing trajectory in $n+1$ space and find the points of intersection $\endgroup$ – Yuriy S Jan 21 '18 at 23:31
  • 2
    $\begingroup$ I consider bouncing as a rolling in a higher dimension when velocities are embedded as higher dimensions. I see no advantage for bouncing over rolling. It just has higher dynamics with no advantageous correlation. GD is a type of rolling with a velocity control mechanism. $\endgroup$ – Arash Jan 23 '18 at 9:39
  • 3
    $\begingroup$ @YuriyS, Let's consider a gradient descent with a high rate (momentum). Sometimes a high rate helps it move faster. Sometimes it drops the GD away from the optimal solution. There is no guarantee that such harsh moves help optimization. The same principal applies to your method as well. A jump might drop the ball into a local minima as well. There is no reason that jump necessarily save the system from the local minima. You only rely on luck. In such case, there are available nondeterministic methods such as GA and PSO. $\endgroup$ – Arash Jan 24 '18 at 10:28

Your Answer

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

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