I want to find the argument $x$ that maximizes
$f(x)=\sum_i e^{-(x-d_i)^2/c}$
for some data values $d_i$ and an arbitrary positive constant $c$.
I assume that $f(x)$ has only a single maximum (most of the $d_i$ are close to each other).
I think I could use some derivative based numerical maximization method (steepest gradient, Newton-Raphson).
However, calculating the gradient and setting it to zero gives:
$x \sum_i e^{-(x-d_i)^2/c} = \sum_i d_i e^{-(x-d_i)^2/c}$
which gave me inspiration to construct a sequence like:
$x_{j+1} = \frac{\sum_i d_i e^{-(x_j-d_i)^2/c}}{\sum_i e^{-(x_j-d_i)^2/c}}$
And testing on some data it looks as if this sequences already converges to the desired solution.
The question(s):
- Under which circumstances will this sequences converge to the argmax of $f(x)$?
- How can I prove that it converges?
- Is the convergence speed linear, quadratic, ..?
Define $$w_n(x) = \frac {e^{-(x - d_n)^2/c}}{\sum_ie^{-(x - d_i)^2/c}}$$ Then $\sum_i w_i(x) = 1$ for all $x$. Then $$x_{j+1} = \sum_i d_iw_i(x_j)$$ That is, $x_j$ is a weighted average of the $d_i$, with the weights given by $w_i(x_j)$. This alone tells us that for all $j$, $\min\{d_i\} \le x_j \le \max\{d_i\}$, but it isn't enough to prove convergence. For that you will need to get into the forms of the $w_i$ functions. Right now I don't have time to do that, but I'll try to get at it later.
But if you can prove convergence, then defining $g(x) = \sum_id_ie^{-(x - d_n)^2/c}$, then what you discovered is that $$f'(x) = \frac{-2}c\left(xf(x) - g(x)\right)$$ and your recursion formula is $x_{j+1} = \frac{g(x_j)}{f(x_j)}$. Letting $j \to \infty$ in the recursion formula gives $$x_\infty = \frac{g(x_\infty)}{f(x_\infty)}$$ where $x_\infty$ is the limit of $x_j$ (since $f$ and $g$ are easily seen to be continuous). Or, $g(x_\infty) = x_\infty f(x_\infty)$. Plugging this into the formula for $f'$ gives $$\begin{align}f'(x_\infty) &= \frac{-2}c\left(x_\infty f(x_\infty) - g(x_\infty)\right)\\&= \frac{-2}c\left(x_\infty f(x_\infty) - x_\infty f(x_\infty)\right) = 0\end{align}$$
Thus $x_\infty$ is indeed a stationary point of $f$ (a little more investigation settles that it is a maximum).