TITLE: 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$
QUESTION [3 upvotes]: 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,)$.

REPLY [1 votes]: (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.
{"set_name": "stack_exchange", "score": 3, "question_id": 2186827}