# Finding zeroes of an infinitely differentiable function of ~100 to ~1000 variables

I have a function that is not only infinitely differentiable, but it is also very cheap to calculate any of those derivatives. It looks like:

$f(\boldsymbol{C}, \boldsymbol{x})=\sum_{i} C_{i} \prod_{j} a_{j}^{x_{i,j}} -\sum_{i}C_{i}$

Where both i run over the same length, and where $a_{j}$ are constants. This function is easily differentiable because after the first, it's either just removing a $C_{i}$ or multiplying with $ln(a_{j})$.

I'm looking for the most efficient method of finding the zeroes of such a function, that takes full advantage of the differentiability. Are there any methods that are preferred in this scenario?

• Err, it sure looks like the absolute value would make the function non-smooth, unless you restrict yourself to very specific values of $a_j,x_{ij}$!? – Wolfgang Bangerth Oct 3 '13 at 12:44
• I'm sorry. I realised I am actually looking for the zeroes of the same function without the absolute value. I edited the question to reflect this. – RobVerheyen Oct 3 '13 at 13:38
• I take it that you want to find all of the zeroes? – Geoff Oxberry Oct 3 '13 at 17:52
• Well, there will probably be infinite zeroes. I'd like to start by just being able to find a zero, given some starting point. – RobVerheyen Oct 3 '13 at 19:35

Your function can be written as $$f(C, x) = C^T d(x), \quad\text{with } (d(x))_i = \prod_j a_j^{x_{i,j}} - 1,$$ so for any fixed $x$, the roots of $f$ are exactly the vectors $C$ in the subspace orthogonal to $d(x)$.
The reverse is also true: For any given $C$, find an orthogonal vector $d$ and solve $$d_i = \prod_j a_j^{x_{i,j}} - 1$$ for $x$. One obvious solution would be $$x_{i,1} = \ln(d_i+1) / \ln(a_1),\\ x_{i,j} = 0, j > 1.$$
• Thanks for this insight. Are there any grounds to assume that it would be impossible to find zeroes for this function as well? Would I have better success repeatedly trying to minimize the absolute value of $f$ from random starting points maybe? – RobVerheyen Oct 4 '13 at 7:43
• Very interesting! I'm going to think about how I can use this. However, there are still the zeroes that have either $C = 0$ or $d = 0$ for all components. In case of C this is trivial, but in case of d, I'd still have to solve $\prod_j a_j^{x_{i,j}} = 1$. – RobVerheyen Oct 4 '13 at 15:21
• This case is covered by setting $d$ (which is formally orthogonal to any $C$) to $0$ in the setting in the answer. One answer is also obvious: $x_{i,j}=0$. – Nico Schlömer Oct 4 '13 at 19:22