find the minimum of the values $\sum ij\cos{(x_{i}-x_{j})}$

Solution 1:

Let us minimize the OP expression $$2F = \left(\sum\limits_{i=1}^n i\sin x_i\right)^2 + \left(\sum\limits_{i=1}^n i\cos x_i\right)^2 - \sum\limits_{i=1}^n i^2.\tag1$$ The stationary points of F can be defined from the system $$\dfrac{\partial F}{\partial x_j}=0,\quad j=1,2,\dots,n,$$ or $$j\cos x_j\left(\sum\limits_{i=1}^n i\sin x_i\right) - j\sin x_j\left(\sum\limits_{i=1}^n i\cos x_i\right) =0,\quad j=1,2,\dots,n,\tag2$$ with the solutions in the forms of

• $\sin x_1 =\sin x_2 = \dots = \sin x_n =0,\; F =0,\;$ and
• $\cos x_1=\cos x_2=\dots=\cos x_n=0.$

Since $\;0\le x_1\le x_2\le \dots\le x_n\le \pi,\;$ then in the second case there are $\;(n+1)\;$ stationary points with the first k zero unknowns, or $$x^{(k)}_i = \pi \theta(i-k-\,^1\!/_2),\quad k=0,1,\dots n,\tag3$$ $$2F_k = \left(\sum\limits_{i=1}^k i -\sum\limits_{i=k+1}^n i\right)^2-\dfrac{n(n+1)(2n+1)}6,\tag4$$ where $\;\theta(t)\;$ is the Heaviside's step function.

At the same time, $$d_k=\sum\limits_{i=1}^{k} i - \sum\limits_{i=k+1}^{n} i = \dfrac12(k^2+k-(n-k)(n+k+1)) = k^2+k-\dfrac{n^2+n}2,\tag5$$ and then from $(4)$ should $$\min\limits_k F_k = F_{m},\quad\text{where}\quad d_{\large m\pm1}^2 \ge d_{\large m}^2. \tag6$$ Thus, \begin{cases} (2m^2-2m-n^2-n)^2 - (2m^2+2m-n^2-n)^2 \ge0\\[4pt] (2m^2+6m+4-n^2-n)^2 - (2m^2+2m-n^2-n)^2 \ge0, \end{cases} \begin{cases} 2m^2\le n^2+n\\[4pt] 2(m+1)^2\ge n^2+n, \end{cases} and finally $$\color{green}{\mathbf{\min F = \dfrac18(2m^2+2m-n^2-n)^2 -\dfrac{n(n+1)(2n+1)}{12},}}\tag7$$ where $$\color{green}{\mathbf{m=\left\lfloor\sqrt{\dfrac{n^2+n}2}\;\right\rfloor.}} \tag8$$

Solution 2:

This is not a full answer and contains errors (see comments) but I have left it up in case some of the ideas are useful to other users.

The derivative of $\sum_{1\leq i<j\leq n}ij\cos(x_i-x_j)$ with respect to any chosen $x_i$ is $-i\sum_{j\ne i}j\sin(x_i-x_j)$. This derivative must equal $0$ at any local minima.

$\sin(x_i-x_j)$ is strictly positive unless $x_i$ and $x_j$ are both in $\{0,\pi\}$. This proves River Li's comment.

Let $\sigma(i)=\begin{cases} 1 \ \text{ if } x_i=0\\ -1 \text{ if } x_i=\pi \end{cases}$ so that

$\sum_{1\leq i<j\leq n}ij\cos(x_i-x_j)=\sum_{1\leq i<j \leq n}ij\sigma(i)\sigma(j)$.

The next step is to rewrite $\sum_{1\leq i<j \leq n}ij\sigma(i)\sigma(j)=\frac{1}{2}\left( \sum_{1\leq i\leq n}\sum_{1\leq j\leq n} ij\sigma(i)\sigma(j)-\sum_{1\leq i\leq n} i^2\sigma(i)\sigma(i) \right)=\frac{1}{2}\left(\left(\sum_{1\leq i \leq n}i\sigma(i)\right)^2-\sum_{1\leq i \leq n}i^2\right)$.

It is well known that $\sum_{1\leq i \leq n}i^2=\frac{n(n+1)(2n+1)}{6}$.

All that remains is to minimise $\left(\sum_i i\sigma(i)\right)^2$. The condition $x_1\leq x_2 \leq ...$ means that there is a $k$ such that $\sigma(i)=1$ for $i\leq k$ and $\sigma(i)=-1$ for $i>k$. So we need to minimise $\left|\sum_i i\sigma(i)\right|=\left|2\binom{k+1}{2}-\binom{n+1}{2}\right|$.