iteratively (approximately) solving a sum of exponentials

Question

I would iteratively have to solve the following equation at iteration $n$:

$C = \sum_{1 \leq i \leq n}{e^{\frac{x_i}{T}}x_i}$ for $T$.

Each iteration $i$ an unknown $x_i$ will be observed and $C$ is a constant.

For the first iteration obtaining $T$ is trivial, but I have no clue how to do so for later iterations as it would involve logarithms of sums.

I could settle for a (crude) approximation, but I would like to limit the computation in each iteration, thus I would like to reuse $T$ or some other partial result (recursive formula) to avoid summing over all observations (as $n$ can become very large).

Thank you in advance for your help.

Answer 1

Here is an idea that may work.

Assume we are interested in minimizing the expected value

\begin{equation*} f(T) := E_z[F(T,z)], \end{equation*} where $F'(T,z) = x(z)e^{x(z)/T}-C$. If the $z$'s are sampled independently, then $E_z[F'(T,z)]=f'(T)$, and you can run the Robbins-Monro iteration (stochastic gradient) to update

\begin{equation*} T_{k+1} = T_k - \alpha_k F'(T_k,z_k), \end{equation*} where $\alpha_k \propto 1/k$.

Assuming the theory applies to your case, in principle it'll lead to the following iteration:

\begin{equation*} T_{k+1} = T_k - \alpha_k(x_ke^{x_k/T_k}-C),\quad k \ge 0, \end{equation*} which only depends on updating our guess $T_k$ as every new example comes along. It solves the equation only in expectation (under additional assumptions that stochastic approximation usually requires)---but hopefully, this approximation suits your purpose.

Answer 2

I would just expand the exponents into the Taylor series with 100 terms or so and update the sums of powers, which have trivial cumulative dynamics. The programming issue is that summing $x_i^{100}$ directly even in the float point arithmetic is not very nice, so I would just keep the polynomial in the form $\sum_{k=0}^{100} (a_k/T)^k$ and update $a_k$ as $$ a_k'=(a_k^k+x_n^{k+1}/k!)^{1/k}=M\cdot(1+q^k)^{1/k} $$ where $M=\max(a_k,y_n)$, $q=\min(a_k,y_n)/\max(a_k,y_n)$, $y_n=(x_n)^{1+1/k}/v_k$ and $v_k=(k!)^{1/k}=exp(-\frac 1k\sum_{j=2}^k\log j)$. This way you should be able to get away with double precision arithmetic in all but most extreme cases and still have reasonable accuracy in the final answer.

Solving a polynomial (in $1/T$) equation of this form should not be a problem.

Answer 3

After some simple algebra, this is equivalent to the calculation of "internal rate of return" in finance, on which there is a large literature and many implementations (e.g. in Microsoft Excel).

In general, this can only be solved numerically, by a nonlinear root-finding algorithm. The function you're searching for the root of is bounded and smooth, so there's no problem of convergence. I recently implemented this using Brent's method, but bisection or the secant method work almost as well and are easier to implement.