3
$\begingroup$

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,)$.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Jean Marie Mar 14 '17 at 20:36
  • $\begingroup$ @JeanMarie Thanks. I added a few examples. $\endgroup$ – Lisa Mar 14 '17 at 20:48
  • 1
    $\begingroup$ @Surb can't you rewrite it with $2n$ inequalities ? $\endgroup$ – Gabriel Romon Mar 14 '17 at 21:02
  • 1
    $\begingroup$ By the way, is it a research problem, an olympiad problem, a textbook problem ? $\endgroup$ – Gabriel Romon Mar 15 '17 at 21:08
  • 1
    $\begingroup$ @Surb Can you elaborate why it is so? $\endgroup$ – Lisa Mar 15 '17 at 22:09
1
$\begingroup$

(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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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