13
$\begingroup$

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<j\le n}ij\cos{(x_{i}-x_{j})}$$

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

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ Dec 11 '19 at 6:16
  • $\begingroup$ 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$ $\endgroup$
    – math110
    Dec 11 '19 at 6:20
  • 2
    $\begingroup$ I did some simulation. It seems $\{x_1, x_2, \cdots, x_n\}=\{0, \pi\}$ at optimum. $\endgroup$
    – River Li
    Dec 15 '19 at 12:15
  • $\begingroup$ @inequality I wrote the question logically, emphasizing that $n$ is fixed, and $x_1,\dots,x_n$ is the stuff we optimize over. $\endgroup$ Dec 15 '19 at 17:51
  • 1
    $\begingroup$ @Omnomnomnom I think it's $ke^{ix_k}$ instead of $ke^{ikx_k}$. $\endgroup$ Dec 19 '19 at 13:55
2
$\begingroup$

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$$ Table for i=2 to 11

$\endgroup$
1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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! $\endgroup$ Dec 23 '19 at 14:06
  • $\begingroup$ "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. $\endgroup$
    – A.Γ.
    Dec 26 '19 at 14:26
  • $\begingroup$ 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$. $\endgroup$ Dec 26 '19 at 16:38
  • $\begingroup$ 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$. $\endgroup$ Dec 26 '19 at 17:08
  • $\begingroup$ 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 $\endgroup$ Dec 26 '19 at 17:11

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.