# Finding a global minimum

I seek the function $$f$$ which satisfies the 100 equations (i=1,2...100)

$$\sum_{j=1}^{2000} f(A_{ij},B_{ij},C_{ij})=Q_i$$.

Where $$A,B,C$$ are 100x2000 matrices and all entries are between 0 and 1.

So I know Q, A, B and C
How can one find the function?

I tried to parametrize the function $$f_w$$ using trilinear interpolation. And then I minimized the error function $$\Psi(w) = \sum_i \left(\left(\sum_j f_w(A_{ij},B_{ij},C_{ij})\right) - Q_i\right)^2.$$

I minimized by just walking around randomly until a minimum is found. But when I ran the simulation many times it finds different minimums. I want to find the smallest minimum, or at least a pretty good one. Is there any method for this? Would neural networks work better?

I have a second dataset to test the function.

If I understand these methods (such as neural networks and gradient descent) correctly they approximate the gradient at your current point, so it will just find a local minimum and wont work any better then my method that just walks a step in a random direction and keeps it if the error function decreases?

Are there any methods to find a good global minimum? What is the best method to find a function that fits this data with least error function?

• It actually depends on the parameterization you choose. What does it mean 'trilinear interpolation' in your case? What are the grid points? If you can write your function $f$ as a linear combination of basis functions, then you get a simple linear least-squares problem. – Alex Shtof Mar 4 at 11:45
• @AlexShtof I used a 5x5x5 cubic grid and interpolated between lattice values – KALLE DA BAWS Mar 4 at 11:50
• @AlexShtof Can you explain this method a bit more, and why you think it will work ? – KALLE DA BAWS Mar 4 at 11:51

## 1 Answer

For solving this kind of problem, one cannot avoid choosing a parametrisation. You may choose it yourself like you have done above, or you may write something more general like a neural network (which is just a very nonlinear parametrisation). However the choice matters and you are likely to find different minima when you vary it. Do you have any intuition about the data? Do you expect $$f$$ should have a certain property? This might help making the right choice.

About finding the global minimum; this is a hard problem in optimisation. Simple gradient descent methods (direct gradient descent, neural network gradient descent...) will stumble unless the error function is differentiable and convex. If you desperately require the global minimiser, then you have to use derivative-free methods such as Simulated Annealing and Particle Swarm Optimisation. These are more complicated algorithms to use, but your programming language of choice is likely to have a global optimisation library which already implements them.