Minimize $\frac{1}{2}\sum_{k=1}^m (x_{k+1}-x_{k})^2$

Question

Given sequence: $$ \begin{cases} x_{n+1}(2\cos(\frac{\pi}{m})-x_n)=1,\forall n\geq 1\\ x_1=x\in\mathbb R,m\in\mathbb N,m\geq 2 \end{cases} $$ Minimize $$A=\frac{1}{2}\sum_{k=1}^m (x_{k+1}-x_{k})^2$$ Edit

I've proved that $\frac{dA}{dx}|_{x=-1}=0$ (see my answer). The problem now is to show that $A_{\min}=A|_{x=-1}$ is the global minimum.

The part below belongs to the original post

$A$ is actually the area bounded by the zig-zag loop between $y=\frac{1}{2\cos(\frac{\pi}{m})-x}$ and $y=x$. I tried it on a computer and observed that $A$ minimizes at $x=-1,\forall m$, and other $m-1$ values of $x$, resulting in the same minimal value of $A$ (the only minimum of $A$). I did try to prove the necessary condition $\frac{dA}{dx} |_{x=-1}=0$, after some algebra, the equivalent equation is:$$\sum_{k=1}^m \left(x_k-2\cos\left(\frac{\pi}{m}\right)x_{k+1}^2+x_{k+1}^3\right)\prod_{i=1}^k x_i^2|_{x=-1}=0$$ I recognized a sort of symmetry inside the sum (sum of two terms (of the sum above) with indices adding up to $m$ is $0$ and the last term is $0$ as well) but I couldn't figure out how to deal with the product in the sum. How do I proceed from here?
Also, with the necessary condition proved, how can I show that there is exactly one minimal value of $A$ for every $m$?

[Feel free to check out this graph]

Answer 1

Not yet the solution, but I found

1. The closed form expression of $(x_k)_k$
2. The minimum and the $m$ values of $x$ such that $A$ reaches its minimum
3. It is not necessary to find the miminum for $\color{red}{x \in \mathbb{R}} $. It suffices to find the global minimum $A_{\min}$ for $\color{red}{x\in (-\infty,0)}$.

---

1

For the sake of simplicity, let us denote $\alpha = \pi/m$ and $t_1,t_2$ be the two solutions of $$t= \frac{1}{2\cos\left(\frac{\pi}{m} \right) -t } $$ then $$t_{1,2} = e^{\pm \mathbf{i} \frac{\pi}{m}} = e^{\pm \mathbf{i} \alpha} = \cos(\alpha) \pm\mathbf{i}\sin(\alpha)$$ We have: $$\begin{align} x_{k+1} -t_1&= \frac{1}{2\cos\left(\frac{\pi}{m} \right) -x_k }-\frac{1}{2\cos\left(\frac{\pi}{m} \right) -t_1 }\\ & = \frac{x_k-t_1}{2\cos\left(\frac{\pi}{m} \right) -x_k }\cdot\frac{1}{2\cos\left(\frac{\pi}{m} \right) -t_1 }\\ x_{k+1} -t_1& = \frac{x_k-t_1}{2\cos\left(\frac{\pi}{m} \right) -x_k }\cdot t_1 \tag{1} \end{align}$$ Same for $t_2$, we have: $$x_{k+1} -t_2= \frac{x_k-t_2}{2\cos\left(\frac{\pi}{m} \right) -x_k }\cdot t_2\tag{2}$$

$(1)/(2)$ we deduce: $$\frac{x_{k+1} -t_1}{x_{k+1} -t_2} = \frac{x_{k} -t_1}{x_{k} -t_2}\cdot \frac{t_1}{t_2}\tag{3}$$ From $(3)$, we deduce the closed form expression of $x_k$ for $k \in \{1,...,m \}$: $$\begin{align} \frac{x_{k} -t_1}{x_{k} -t_2} = \frac{x -t_1}{x -t_2} \left(\frac{t_1}{t_2}\right)^{k-1} &\implies x_k= \frac{x(t_2^{k-2}-t_1^{k-2})-(t_2^{k-1}-t_1^{k-1})}{x(t_2^{k-1}-t_1^{k-1})-(t_2^{k}-t_1^{k})}\\ &\implies \color{red}{x_k= \frac{x\sin((k-2)\alpha) - \sin((k-1)\alpha)}{x\sin((k-1)\alpha) - \sin(k\alpha)}} \tag{4} \end{align}$$

---

Thanks to Mathematica, from $(4)$ we have: $$\begin{align} (x_{k+1}-x_k)^2 &= \left(\frac{x\sin((k-1)\alpha) - \sin(k\alpha)}{x\sin(k\alpha) - \sin(({k+1})\alpha)} - \frac{x\sin((k-2)\alpha) - \sin((k-1)\alpha)}{x\sin((k-1)\alpha) - \sin(k\alpha)}\right)^2 \\ &= \frac{(1-2\cos(\alpha)x+x^2)^2 \cdot \sin^4 (\alpha)}{(x\sin(k\alpha) - \sin(({k+1})\alpha))^2(x\sin((k-1)\alpha) - \sin(k\alpha))^2} \end{align}$$ Then $$\color{red}{A = \frac{\sin^4 (\alpha) }{2}\cdot\sum_{k=1}^m \frac{(1-2\cos(\alpha)x+x^2)^2}{(x\sin(k\alpha) - \sin(({k+1})\alpha))^2(x\sin((k-1)\alpha) - \sin(k\alpha))^2}}$$

---

2

$A$ reaches its minimum

$$\color{red}{A_{\min} =2\sin^4(\alpha)\cdot\sum_{k=1}^m\frac{1}{(\cos(\alpha)-\cos(2k\alpha))^2}}$$

if and only if $x$ is equal to one of these $m$ values

$$\color{red}{x = \frac{\sin\left(\left(h-\frac{1}{2}\right)\alpha\right)}{\sin\left(\left(h+\frac{1}{2}\right)\alpha\right)} \hspace{1cm }\text{for }h=1,...,m}$$

---

3

From $(4)$, we notice that

• the product of $(x_k)_k$ is negative: $$\prod_{k=1}^m x_k = \prod_{k=1}^m\frac{x\sin((k-2)\alpha) - \sin((k-1)\alpha)}{x\sin((k-1)\alpha) - \sin(k\alpha)} = -1$$ So, there exists at least a $h \in \{ 1,2,...,m\}$ such that $x_h<0$ (just for information, graphically, we can see that there exist a unique $x_h$ such that $x_h<0$, all others are positive).
• the sequence is cyclic with period $m$ (i.e $x_{m+1} = x_1$) and the sum $A$ is also cyclic. So, if there exists a $x^*$ such that $A(x^*) = A_{ \min}$, the sequence will be $$x_1 = x^{*} \to x_2(x^*) \to ... \to x_m(x^*)$$ then there exists a $h \in \{ 1,2,...,m\}$ such that $x_h(x^*)<0$ and we can consider $x_h(x^*)$ as the first element $x_1 = x:= x_h(x^*)<0$.

By consequence, we can restrict the domain to $x \in (-\infty,0)$ for finding the mimimum of $A$.

Besides, if there exists a $x^*<0$ such that $A(x^*) = A_{ \min}$, the other $m-1$ values $x_k(x^*)$ ($k=2,..,m$) also satisfy $$A(x_k(x^*)) = A_{ \min} \hspace{1cm} \text{for }k=2,...,m$$

Objective: What we need to prove $$\color{red}{\min_{x \in (-\infty,0)}A(x) = A(-1)}$$

Remark: in the domain $x\in (-\infty,0)$, graphically, $A(x)$ is a convex function and has a unique mimimum at $x = -1$.

Answer 2

I decided to answer my own question but it is not yet a complete answer. I will only prove $\frac{dA}{dx}|_{x=-1}=0$.

Continuing from NN2's work: $$A=2\sin(\alpha)^4\sum_{k=1}^m \frac{1}{(\cos(\alpha)-\cos(2k\alpha)+(x+1)G_k(x))^2};\alpha=\frac{\pi}{m}$$ Where $$G_k(x)=\frac{(\cos(2k\alpha)-\cos((2k-1)\alpha))(x+1)+2\sin(\alpha)\sin(2k\alpha)}{x^2-2\cos(\alpha)x+1}$$ [This can be verified easily by algebra] $$\frac{dA}{dx}|_{x=-1}=-4\sin(\alpha)^4\sum_{k=1}^m \frac{G_k(x)+(x+1)G'_k(x)}{(\cos(\alpha)-\cos(2k\alpha)+(x+1)G_k(x))^3}|_{x=-1}$$ $$=-4\sin(\alpha)^4\sum_{k=1}^m \frac{G_k(-1)}{(\cos(\alpha)-\cos(2k\alpha))^3}=\frac{-4\sin(\alpha)^5}{1+\cos(\alpha)}\sum_{k=1}^mB(k)$$ Where $$B(k)=\frac{\sin(2k\alpha)}{(\cos(\alpha)-\cos(2k\alpha))^3}$$ It is straightforward that:$$B(k)+B(m-k)=0,\forall k$$ Hence $$\sum_{k=1}^mB(k)=0\Rightarrow \frac{dA}{dx}|_{x=-1}=0$$

Answer 3

First note that the problem in the OP:

minimization of $$ \frac{1}{2}\sum_{k=1}^m (x_{k+1}-x_{k})^2$$

subject to:

$$ x_{n+1}(2\cos(\frac{\pi}{m})-x_n)=1, \quad n\geq 1\\ x_1=x\in\mathbb R,m\in\mathbb N,m\geq 2 $$

can be written as the following convex optimization model (for $m\in\mathbb N,m\geq 2$):

$$ \color{blue}{\text{P:} \, \min \quad \frac{1}{2}\sum_{k=1}^m (x_{k+1}-x_{k})^2}$$

subject to:

$$ \color{blue}{2\cos(\frac{\pi}{m})-x_n+x_{n+1} \ge \sqrt{4+\left (2\cos(\frac{\pi}{m})-x_n-x_{n+1}\right )^2},\quad n\geq 1\\ x_1=x\in\mathbb R }. $$

This optimization model is classified as a second-order cone programming model. It worth noting that for any $\epsilon >0$, an $\epsilon$-optimal solution of such an optimization model can be found in polynomial time, and many powerful solvers have been developed for solving this class of optimization models, which includes convex quadratic programming models. Hence, the above model can be used to solve the problem in the OP for any other similar function other than $$y=\frac{1}{2\cos(\frac{\pi}{m})-x}.$$

Let $\color{blue}{A(a)}$ denote the optimal value of the model $\text{P}$ by fixing $\color{blue}{x}$ to $a$, i.e., the optimal value of the following model, called $\text{P}(a)$:

$$ \color{blue}{\text{P}(\color{blue}{a }): \, \min \quad \frac{1}{2}\sum_{k=1}^m (x_{k+1}-x_{k})^2}$$

subject to:

$$ 2\cos(\frac{\pi}{m})-x_n+x_{n+1} \ge \sqrt{4+\left (2\cos(\frac{\pi}{m})-x_n-x_{n+1}\right )^2},\quad n\geq 1\\ x_1=x, \color{blue}{x=a }. $$

Let $(x(a)^*_1, \cdots, x(a)^*_{m+1})$ denote an optimal solution of $\text{P}(a)$. Now I show for any $a$ and $b$ and any $\alpha \in [0,1]$,

$$A(\alpha a+(1-\alpha) b) \le \alpha A( a)+ (1-\alpha)A(b). $$

As the feasible space of the original model $\text{P}$ is a convex set, then $$(y^*_1, \cdots, y^*_{m+1})=\alpha (x^*(a)_1, \cdots, x^*(a)_{m+1})+(1-\alpha) (x^*(b)_1, \cdots, x^*(b)_{m+1})$$ is a feasible solution for model $\text{P}(\alpha a+(1-\alpha) b)$. Moreover, from the convexity of the objective function, we have

$$A(\alpha a+(1-\alpha) b)=\frac{1}{2}\sum_{k=1}^m \left (x^*(\alpha a+(1-\alpha) b)_{k+1}-x^*(\alpha a+(1-\alpha) b)_{k} \right)^2 \le \\ \frac{1}{2} \sum_{k=1}^m (y_{k+1}-y_{k})^2 \le \\ \alpha\frac{1}{2}\sum_{k=1}^m (x^*(a)_{k+1}-x^*(a)_{k})^2+(1-\alpha)\frac{1}{2}\sum_{k=1}^m (x^*(b)_{k+1}-x^*(b)_{k})^2\alpha \\= A( a)+ (1-\alpha)A(b) $$

Therefore, $A(x)$ is a convex function.

Also, from @QuýNhânĐặngHoàng's answer, in which @NN2's answer was used, we know that $$\frac{dA(x)}{dx}\Bigg|_{x=-1}=0.$$ Thus, $x=-1$ is the optimal solution, and the proof of the claim in the OP is completed.