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

Fix a positive integer $$n$$. Out of all possible $$0\le x_{1}\le x_{2}\le\cdots\le x_{n}\le \pi$$, find the minimum of the value of $$F=\sum_{1\le i

I have try since $$2F=(\sum_{i=1}^{n}i\sin{x_{i}})^2+(\sum_{i=1}^{n}i\cos{x_{i}})^2-\sum_{i=1}^{n}i^2$$

• The first sums in the expression for $2F$ can be joined to produce $$2F = \left| \sum_{k=1}^n k e^{i kx_k}\right|^2 - \sum k^2,$$ which might be helpful. Dec 11 '19 at 6:16
• it's same as me.because $|\sum_{k=1}^{n}ke^{ikx_{k}}|^2=(\sum_{i=1}^{n}i\sin{x_{i}})^2+(\sum_{i=1}^{n}i\cos{x_{i}})^2$ Dec 11 '19 at 6:20
• I did some simulation. It seems $\{x_1, x_2, \cdots, x_n\}=\{0, \pi\}$ at optimum. Dec 15 '19 at 12:15
• @inequality I wrote the question logically, emphasizing that $n$ is fixed, and $x_1,\dots,x_n$ is the stuff we optimize over. Dec 15 '19 at 17:51
• @Omnomnomnom I think it's $ke^{ix_k}$ instead of $ke^{ikx_k}$. Dec 19 '19 at 13:55

2 Answers

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$$

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

The next step is to rewrite $$\sum_{1\leq i.

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

• Great solution! One (minor) edit. Note that $0 \leq x_i \leq x_j \leq \pi$ means that $-\pi \leq x_i - x_j \leq 0$. So $-\sin(x_i - x_j)$ is strictly positive unless $x_i=x_j$ or both $x_i$ and $x_j$ are in $\{0, \pi\}$. Maximums occur where $x_i=x_j$. The rest follows as @AngelaRichardson has described. Thanks! Dec 23 '19 at 14:06
• "This derivative must equal 0 at any local minima" (с) It is not true for constrained optimization. For example, consider $\min_{x\in[0,1]} x$. The local/global min is at $x=0$, but the derivative is not zero there.
– A.Γ.
Dec 26 '19 at 14:26
• Unfortunately, after thinking about this a bit more, I have come to realize we were a bit hasty in calculating the formula for the partial with respect to $x_k$. In fact, $$\displaystyle D_{x_k}F = \sum_{1 \leq i < k} ik \sin(x_i - x_k) - \sum_{k < j \leq n} kj \sin(x_k - x_j),$$ the difference of two negative quantities for the given domain/conditions on the $x_i$. Dec 26 '19 at 16:38
• If $n=5$ and we set $F_3(x):= (D_{x_3}F)(x_1,x_2,x,x_4,x_5)$ and put $x_1=0, x_2=1, x_3=x, x_4=3, x_5=\pi$, the graph desmos.com/calculator/ogcyxcg7bv shows there is some $x \in (1,3)$ for which $F_3(x)=0$. Dec 26 '19 at 17:08
• Even with just $n=3$ there is another point, $(1, \approx 2.81, \pi)$, at which the partial with respect to $x_2$ is $0$ ... desmos.com/calculator/oh11uedp63 Dec 26 '19 at 17:11