# Bouncing ball optimization

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.

• 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$. – Brian Borchers Jan 19 '18 at 4:06
• @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 – Yuriy S Jan 19 '18 at 9:45
• Generally in stochastic search algorithms you keep track of the best solution seen so far and report that at the end. – Brian Borchers Jan 19 '18 at 14:51
• In the same vein (using a physics analogy for optimization, and similarly to using gravity), consider simulated annealing: en.wikipedia.org/wiki/Simulated_annealing – Solomonoff's Secret Jan 21 '18 at 2:55
• 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). – Michael Jan 21 '18 at 22:32

• @ 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 – Yuriy S Jan 21 '18 at 23:31