3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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}$!? $\endgroup$ – Wolfgang Bangerth Oct 3 '13 at 12:44
  • $\begingroup$ 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. $\endgroup$ – RobVerheyen Oct 3 '13 at 13:38
  • $\begingroup$ I take it that you want to find all of the zeroes? $\endgroup$ – Geoff Oxberry Oct 3 '13 at 17:52
  • $\begingroup$ Well, there will probably be infinite zeroes. I'd like to start by just being able to find a zero, given some starting point. $\endgroup$ – RobVerheyen Oct 3 '13 at 19:35
6
$\begingroup$

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. $$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – RobVerheyen Oct 4 '13 at 7:43
  • $\begingroup$ Or minimize the square of this function. $\endgroup$ – RobVerheyen Oct 4 '13 at 9:17
  • $\begingroup$ I adapted the answer a little bit, and it seems that the problem can be tackled on an analytical level -- no numerics needed. $\endgroup$ – Nico Schlömer Oct 4 '13 at 10:51
  • $\begingroup$ 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$. $\endgroup$ – RobVerheyen Oct 4 '13 at 15:21
  • 1
    $\begingroup$ 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$. $\endgroup$ – Nico Schlömer Oct 4 '13 at 19:22

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.