0
$\begingroup$

Consider the function which maps $\mathbb{R}^n$ to $\mathbb{R}$ \begin{align} f(x) = \sum_{i=1}^{n} b_i\phi_i(x) \end{align} where $\phi_i(x) = \exp(-\frac{||x-x_i||_2^2}{2})$ are Gaussian functions each centered at $x_i\in \mathbb{R}^n$ and $b_i \geq 0$. Simply, this is a linear combination of gaussian functions centered at $x_i$. It seems intuitive to me that the maximum of this function should lie in the convex hull of the points $x_1,\dots,x_n$. This is because, if $b_i$ were 1, $f(x)$ is effectively the sum of exponentiated distances of $x$ to each point $x_i$. Thus $f(x)$ in general is the weighted sum of distance. Thus maximizing this function is equivalent to finding the point which is close to everyone. If it was any point outside the convex hull, it should have been easy to find another point which is closer to the hull and thus closer to one of the points and thus improving $f(x)$ further. Is this thought process correct?

$\endgroup$
1
$\begingroup$

Yes, and this has nothing to do with Gaussian: you can take $\phi_i(x)=g_i(|x-x_i|)$ where $g_i$ are any strictly decreasing functions.

Lemma. If all $x_j$ are all on one side of a hyperplane $H$ (or on $H$), and $x$ on the other side (strictly), and $x^*$ is the orthogonal projection of $x$ onto $H$, then $$f(x^*)> f(x).$$

This is true because $|x-x_j|>|x^*-x_j|$ for each $j$, by an easy explicit computation.

Suppose that an absolute maximum $x$ is outside of the convex hull. (It is clear that absolute maximum exists.) Applying this lemma to a hyperplane which contains a facet of the convex hull, we obtain a point $x^*$ where $f(x^*)>f(x)$ which gives a contradiction. This proves the statement.

$\endgroup$
  • $\begingroup$ Thanks Professor. In addition, what if $f(x) = \sum_{i}b_i\phi_i (x) - \sum_{i,j}K_{ij}\phi_i (x) \phi_j (x)$ where K is a positive definite matrix. Does the answers change then? Is there any possible hope then. $\endgroup$ – dineshdileep Jan 14 at 1:33
  • $\begingroup$ @dineshdileep: take $b_j=0$ and $K=I$. Then there is no maximum: it is at infinity. $\endgroup$ – Alexandre Eremenko Jan 14 at 13:39

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.