# Best method to run an optimizing function millions of times

My goal is to find the local minimums of a smooth multivariate function $$f_t(\vec y)$$ for multiple values of $$t$$. I have created an algorithm $$foo(t,\vec x)$$ which returns the results of Newton's Method (by "results", I mean that $$foo(t,\vec x)$$ returns $$\vec a$$, where $$\vec a$$ is a local minimum for $$f_t(\vec y)$$) on $$f_t(\vec y)$$, where the initial guess is $$\vec x$$. I have 1,000 values of $$t$$ to solve for, and for each $$t$$, I try half-million values of $$\vec x$$. I then push all the return values of $$foo(t,\vec x)$$ into an array.

Essentially, I need to run $$foo(t,\vec x)$$ about half-billion times for different $$t$$ and $$\vec x$$. Currently, I have split the computations into four threads, each running $$foo(t,\vec x)$$ about 125,000,000 times. On my laptop this takes around 2 hours. I would like to shorten the running time as much as possible. What can I possibly do to achieve this?

Here are some details about $$f_t(\vec y)$$ and $$foo(t,\vec x)$$:

• $$f_t: \mathbb R^4 \to \mathbb R$$, so this is a very low dimensional optimization problem.

• $$f_t$$ is a radical function.

• $$foo(t,\vec x)$$ uses a standard Newton's Method, i.e. tries to find the roots of the gradient $$\nabla f_t$$. It finds the descent direction $$\vec p_{n+1} = -H_n^{-1}\nabla f_t$$, where $$H_n$$ is the hessian matrix, and using inexact line search finds descent length $$\alpha$$. Then it sets $$x_{n+1}=x_n+\alpha p_n$$.

I have heard that machine learning uses GPU. Would my program also be able to utilize the GPU in some way? Maybe run $$foo(t,\vec x)$$ on each core of a GPU?

• It's hard to say without knowing more about the function being evaluated, but as a general comment, if computation can't be shared between evaluations of $f_t$, then throwing a GPU at it might make sense. Vector instructions, to do multiple evaluations in parallel, might also help. Jun 1 at 3:49
• As an example, Newton's method requires computing both the function and its Jacobian at a point. Presumably you can save some computation there. If this is a high-dimensional problem, you might also consider Gauss-Newton, which uses the Moore-Penrose pseudoinverse of the Jacobian and so exploits sparsity. It might be worth trying gradient descent, too. Jun 1 at 4:23
• From what little I know of GPU programming, GPU's are very inefficient at serial computations and are bad with memory. Would it be possible for a GPU core to calculate $foo(t,\vec x)$ in a reasonable amount of time? $foo(t,\vec x)$ itself consists of hundreds of iterations of loops. Jun 2 at 4:37
• What a GPU would buy you, if anything, is the ability to evaluate $f$ many times with different arguments in a SIMD manner. Jun 2 at 5:07