# Optimize \begin{align} \min _{ (x_1,..,x_n) }\sum_{i=1}^n \sum_{k=1}^n e^{-\frac{(x_i-x_k)^2}{2}} \end{align} such that $|x_i|\le a$

Does the following optimization problem have a solution? For some fixed $n \ge 1$ and $a>0$ \begin{align} \min _{ (x_1,..,x_n) }\sum_{i=1}^n \sum_{k=1}^n e^{-\frac{(x_i-x_k)^2}{2}} \end{align} subject to a constraint \begin{align} |x_i| \le a, \forall i\in \{1,...,n\} \end{align}

For the case of $n=1$ the optimization problem is trivial since the valu is always $1$.

For $n=2$

\begin{align} 2 +2 \min_{(x_1,x_2)}e^{-\frac{(x_1-x_2)^2}{2}} \end{align}

Then the optimal solution is to take $x_1=-a$ and $x_2=a$.

It seems that the points must spread as far as possible. But I am not sure if the optimal solution is $(-a,a,-b,b,...,-c,c,)$.

• You should say, as you are a little accustomed to this SE site, what you have already tried ! Have you for example considered elementary cases $n=1$, $n=2$, $n=3$ and see what happens ? – Jean Marie Mar 14 '17 at 20:36
• @JeanMarie Thanks. I added a few examples. – Lisa Mar 14 '17 at 20:48
• @Surb can't you rewrite it with $2n$ inequalities ? – Gabriel Romon Mar 14 '17 at 21:02
• By the way, is it a research problem, an olympiad problem, a textbook problem ? – Gabriel Romon Mar 15 '17 at 21:08
• @Surb Can you elaborate why it is so? – Lisa Mar 15 '17 at 22:09

## 1 Answer

(The following is a comment on the $n=3$ case, though too long to post as an actual comment.)

Solution(s) must exist, since the sum is a continuous function on a compact set, as noted in the comments already. However, the pattern of the solutions will likely depend on the range of $a\,$.

In the $n=3$ case the double sum is $S(x_1,x_2,x_3)=3+2\Big(e^{- \frac{(x_1-x_2)^2}{2}}+e^{- \frac{(x_2-x_3)^2}{2}}+e^{- \frac{(x_3-x_1)^2}{2}}\Big)\,$. Let $T = \frac{S-3}{2}=e^{- \frac{(x_1-x_2)^2}{2}}+e^{- \frac{(x_2-x_3)^2}{2}}+e^{- \frac{(x_3-x_1)^2}{2}}\,$, which varies directly monotonically with $S$.

Assume WLOG that $-a \le x_1 \le x_2 \le x_3 \le a\,$. Then "shifting" $x_3$ to $a$ increases both $x_3-x_2$ and $x_3-x_1\,$, thus decreases $T$. Similarly, shifting $x_1$ to $-a$ further decreases $T$. Therefore, the minimum of $T$ must be attained at some $x \in [-a,a]$ which minimizes:

$$T- e^{- 2a^2}=f(x)=e^{- \frac{(x+a)^2}{2}}+e^{- \frac{(x-a)^2}{2}}$$

Since $f$ is an even function, the minimum on $[-a,a]$ is the same as the minimum on $[0,a]\,$, and it can only be attained either at the ends of the interval, or otherwise inside it at a local minimum.

Leaving potential local minimums aside, the values at the ends of the interval are $f(0)=2 e^{-\frac{a^2}{2}}$ and $f(a)=1+e^{-2a^2}\,$, respectively, and they coincide for $a_0 \simeq 1.104\cdots$ (which can be determined in closed form, per the "exact forms" option in the previous link). For $a \lt a_0$ the minimum appears to be attained at $\,x=a\,$ i.e. $\,S(-a,\pm a,a)\,$, while for $\,a \gt a_0\,$ it is at $\,x=0\,$ i.e. $\,S(-a,0,a)\,$.

[ EDIT ]  The above hints (though doesn't prove) that for $n=3$ and $a \le a_0$ the sum $S_3$ is minimized when $x_{1,2,3}$ are split between the endpoints $\pm a$ of the allowed range.

Assuming this result, a good case could be made (though, again, not a proof) that for $n \gt 3$ and $a \le a_0$ the sum $S_n$ is minimized when $x_k$ are evenly split $\lfloor\frac{n+1}{2}\rfloor+\lfloor\frac{n}{2}\rfloor$ between the endpoints $\pm a\,$. The idea is to iteratively "shift" one of the $n$ points to either endpoint $\pm a$ while showing that $S_n$ decreases at each step, which means that the end configuration is at least a local minimum.

Like in the base case, assume WLOG that $(x_k)$ are sorted ascendingly within $[-a,a]\,$. Then...

• Shifting the largest value $x_n$ to $a$ increases all $x_n-x_i$ for $i \lt n\,$, thus decreases $S_n$.

• Shifting the smallest value $x_1$ to $-a$ increases all $x_i-x_1$ for $i \gt 1\,$, thus decreases $S_n$.

• Shifting the next largest value $x_{n-1}$ to $a$ increases all $x_{n-1}-x_i$ for $1 \lt i \lt n-1\,$, and by the $n=3$ hypothesis it also decreases $S_3(x_1=-a,x_{n-1},x_n=a)$, so in the end it decreases $S_n\,$.

• Shifting the next smallest value $x_2$ to $-a$ increases all $x_i-x_2$ for $2 \lt i \lt n\,$, and it also decreases $S_3(x_1=-a,x_2,x_n=a)$, so in the end it decreases $S_n$ as well.

• Shifting now $x_{n-2}$ to $a$ increases all $x_{n-2}-x_i$ for $2 \lt i \lt n-2\,$, and the rest of terms in $S_n$ add up to $2 \cdot S_3(-a,x_{n-2},a)\,$ which also decreases.

• $\cdots$

The process can be repeated until all points have been evenly "shifted" to the two endpoints.

• Thanks. Very nice and comprehensive "comment". Any chance that these ideas are extendable to $n>3$. – Lisa Mar 17 '17 at 12:01
• @Lisa I think the case $a \le a_0$ can be extended to $n \gt 3\,$, see the new "comment". – dxiv Mar 17 '17 at 20:02