Maximizar la suma $\sum\limits_{i=1}^nx_ix_{i+1}$ con sujeción a $\sum\limits_{i=1}^nx_i=0$ y $\sum\limits_{i=1}^nx_i^2=1$

Question

¿Existe una forma eficaz de resolver el siguiente problema?

Dado $x_i\in \mathbb R$ y que $\sum\limits_{i=1}^nx_i=0$ y $\sum\limits_{i=1}^nx_i^2=1$ . Quiero maximizar $\sum\limits_{i=1}^nx_ix_{i+1}$ donde tomamos $x_{n+1}=x_1$ .

No sé si esto es relevante/útil en absoluto pero tal vez representando los sistemas como $\vec{x}^TI\,\,\vec{x}$ y $\vec{x}^T\{\delta_{i , \,\,i+1}\}\,\,\vec{x}$ ¿podría ayudar?

Gracias.

Answer 1

Para simplificar la notación, utilizaremos $x_0=x_n$ y $x_{n+1}=x_1$ .

Porque $\sum\limits_{i=1}^nx_i=0$ las variaciones permitidas $\{\delta x_i\}$ debe satisfacer $$ \sum_{i=1}^n\delta x_i=0\tag{1} $$ y porque $\sum\limits_{i=1}^nx_i^2=1$ , $$ \sum_{i=1}^nx_i\delta x_i=0\tag{2} $$ Para maximizar $\sum\limits_{i=1}^nx_ix_{i+1}$ cualquier variación que satisfaga $(1)$ y $(2)$ también debe satisfacer $$ \sum_{i=1}^n(x_{i-1}+x_{i+1})\delta x_{i}=0\tag{3} $$ Si $(x_{i-1}+x_{i+1})$ es ortogonal a todos los vectores ortogonales a $1$ y $x_i$ , entonces debe haber $\mu$ y $\lambda$ para que $$ x_{i-1}+x_{i+1}=\mu+2\lambda x_i\tag{4} $$ Resumiendo $(4)$ en $i$ y considerando $\sum\limits_{i=1}^nx_i=0$ , obtenemos que $\mu=0$ . Por lo tanto, $$ x_{i+1}=2\lambda x_i-x_{i-1}\tag{5} $$ Cuadrando $(5)$ , sumando en $i$ y utilizando $\sum\limits_{i=1}^nx_i^2=1$ produce $$ \lambda=\sum_{i=1}^nx_ix_{i-1}\tag{6} $$ Dado que la solución de $(5)$ debe ser $n$ -periódica, las raíces de $x^2-2\lambda x+1=0$ deben tener ambos $r^n=1$ .

Si utilizamos $r=1$ entonces $\lambda=1$ , pero todos $x_i$ sería lo mismo. En este caso, no podemos satisfacer las restricciones dadas.

Respuesta:

Si utilizamos $r_1=e^{\frac{i2\pi}{n}}$ y $r_2=e^{\frac{-i2\pi}{n}}$ entonces $\lambda=\cos\left(\frac{2\pi}{n}\right)$ y por lo tanto, para $n\ge3$ , $$ x_i=\sqrt{\frac{2}{n}}\cos\left(\frac{2\pi}{n}i\right)\tag{7} $$ produce el máximo $$ \sum_{i=1}^nx_ix_{i-1}=\cos\left(\frac{2\pi}{n}\right)\tag{8} $$ Verificación:

Utilizando la fórmula de la suma de una serie geométrica se obtiene $$ \sum_{k=0}^{n-1}e^{\frac{i2\pi}{n}k}=\frac{e^{\frac{i2\pi}{n}n}-1}{e^{\frac{i2\pi}{n}}-1}=0\tag{9a} $$ $$ \sum_{k=0}^{n-1}e^{\frac{i4\pi}{n}k}=\frac{e^{\frac{i4\pi}{n}n}-1}{e^{\frac{i4\pi}{n}}-1}=0\tag{9b} $$ Por lo tanto, las partes reales de $(9)$ dicen que para $n\ge3$ $$ \sum_{i=1}^n\cos\left(\frac{2\pi}{n}i\right)=0\tag{10a} $$ $$ \sum_{i=1}^n\cos\left(\frac{4\pi}{n}i\right)=0\tag{10b} $$ Así, $\mathrm{(10a)}$ verifica que $(7)$ satisface $\sum\limits_{i=1}^nx_i=0$ . Además, $\mathrm{(10b)}$ produce $$ \begin{align} \sum_{i=1}^n\cos^2\left(\frac{2\pi}{n}i\right) &=\sum_{i=1}^n\frac{\cos\left(\frac{4\pi}{n}i\right)+1}{2}\\ &=\frac{n}{2}\tag{11} \end{align} $$ que verifica que $(7)$ satisface $\sum\limits_{i=1}^nx_i^2=1$ .

Utilizando la identidad $\cos(x+y)+\cos(x-y)=2\cos(x)\cos(y)$ muestra que $$ \begin{align} \sum_{i=1}^n\cos\left(\frac{2\pi}{n}i\right)\cos\left(\frac{2\pi}{n}(i-1)\right) &=\frac{1}{2}\sum_{i=1}^n\left(\cos\left(\frac{2\pi}{n}\right)+\cos\left(\frac{2\pi}{n}(2i-1)\right)\right)\\ &=\frac{n}{2}\cos\left(\frac{2\pi}{n}\right)+\frac{1}{2}\sum_{i=1}^{2n}\cos\left(\frac{2\pi}{n}i\right)-\frac{1}{2}\sum_{i=1}^n\cos\left(\frac{4\pi}{n}i\right)\\ &=\frac{n}{2}\cos\left(\frac{2\pi}{n}\right)\tag{12} \end{align} $$ que verifica que $(7)$ produce $\sum\limits_{i=1}^nx_ix_{i-1}=\cos\left(\frac{2\pi}{n}\right)$ .

Answer 2

Puede utilizar Multiplicadores de Lagrange . Probablemente hay buenos libros que explican mejor este tema que este artículo de la Wikipedia.

---

EDIT: Lo que antes era una conjetura ahora está demostrado.

---

Siguiendo este enfoque, el valor máximo es la mitad del mayor valor propio de una determinada matriz $M$ abajo.

Tienes una función que optimizar: $$F(\vec{x})=\sum x_ix_{i+1}$$ con dos restricciones: \begin{align}G(\vec{x})&=\sum x_i=0\\ H(\vec{x})&=\sum x_i^2=1 \end{align}

Con funciones polinómicas tan simples como éstas, el método de los multiplicadores de Lagrange establece que si $\vec{x}$ es un punto extremo potencial, entonces para algún $\lambda$ y $\mu$ , \begin{align}\nabla F&=\lambda\nabla G+\mu\nabla H\\ M\vec{x} & = \lambda\vec{1}+2\mu\vec{x} \end{align} donde \begin{align} M&=\ \begin{bmatrix}0&1&0&0&\cdots&0&1\\ 1&0&1&0&\cdots&0&0\\ 0&1&0&1&\cdots&0&0\\ 0&0&1&0&\cdots&0&0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots&\vdots\\ 0&0&0&0&\cdots&0&1\\ 1&0&0&0&\cdots&1&0\end{bmatrix} \\ \vec{1}&= \begin{bmatrix}1\\1\\1\\1\\\vdots\\1\\1\end{bmatrix} \end{align}

Suma de la ecuación $M\vec{x} = \lambda\vec{1}+2\mu\vec{x}$ sobre todas las filas y utilizando la primera restricción muestra que $\lambda=0$ y $\vec{x}$ debe ser un vector propio de $M$ en el eigespacio $V_{2\mu}$ . Esto da más limitaciones: $J(\vec{x})=(M-2\mu I)\vec{x}=0$ . Desde $\nabla F$ es una combinación lineal de $\nabla J$ y $\nabla H$ , $F$ debe ser constante con las restricciones $H(\vec{x})=1$ y $J(\vec{x})=0$ .

Así que $F$ toma valores constantes en los eigenspaces de $M$ intersectada con la esfera dada por $H(\vec{x})=1$ . "Todo" lo que queda es encontrar un vector propio de cada espacio propio de $M$ (que no sea $V_2$ que es ortogonal a la restricción $G(\vec{x})=0$ ) y calcular $F$ . No conozco una forma de manejar esta matriz $M$ para todos los valores de $n$ simultáneamente, sin embargo.

Si $\vec{x}$ es un vector propio de $M$ con valor propio $2\mu$ Satisfaciendo a $H(\vec{x})=1$ entonces \begin{align} F(\vec{x}) & =\vec{x}^t\left(\frac{1}{2}M\right)\vec{x}\\ &=\vec{x}^t\frac{1}{2}(2\mu\vec{x})\\ &=\mu\ \vec{x}^t\vec{x}\\ &=\mu \end{align}

Así que, en resumen, los únicos puntos extremos potenciales para $F$ ocurren en las intersecciones de la esfera unitaria con los distintos eigenspaces de $M$ . En estas intersecciones, $F$ tiene un valor constante $\mu$ que es la mitad del valor propio de $M$ para ese eigespacio. Si puedes encontrar los valores propios de $M$ tienes las respuestas a tu pregunta.

Answer 3

Esto es similar a la respuesta de alex.jordan, pero desde una perspectiva diferente. Dejemos que $P\ $ sea la matriz de permutación $(\delta_{i+1,j})$ y $A=\frac12(P+P^\top)$ . Dejemos también $\mathbf{u}=(1,1,\ldots,1)^\top$ . Entonces $$ \max\{\mathbf{x}^\top P\mathbf{x} : \|\mathbf{x}\|=1,\ \mathbf{x}\perp \mathbf{u}\} = \max\{\mathbf{x}^\top A\mathbf{x} : \|\mathbf{x}\|=1,\ \mathbf{x}\perp \mathbf{u}\}. $$ Desde $\mathbf{u}$ es un vector propio de $A$ correspondiente al valor propio $1$ el lado derecho es igual al valor propio máximo de $A$ cuando el valor propio $1$ está excluida. Tenga en cuenta que $A$ es un matriz circulante . En general, para una matriz circulante cuya primera fila es alguna $(c_0, c_1, \ldots, c_{n-1})$ los valores propios vienen dados por

$$ \lambda_k = c_0 + c_1\omega_k + c_2\omega_k^2 + \ldots + c_{n-1}\omega_k^{n-1}; \quad k=0,1,\ldots,n-1, $$ donde $\omega_k=\exp\left(2\pi k\sqrt{-1}/n\right)$ . El vector propio correspondiente a $\lambda_k$ es $$ \mathbf{v}_k = (1,\,\omega_k,\,\omega_k^2,\ldots,\omega_k^{n-1})^\top. $$ Para nuestro $A$ tenemos $c_1=c_{n-1}=\frac12$ y $c_k=0$ por otra parte. Por lo tanto, $$ \lambda_k=\frac12(\omega_k + \omega_k^{n-1})=\cos\left(2\pi k/n\right). $$ Por lo tanto, el máximo de los valores propios (excluyendo $1$ ) es $\lambda_1=\cos\left(2\pi/n\right)$ . Tomando la parte real de $\mathbf{v}_1$ obtenemos un vector propio real $\mathrm{Re}(\mathbf{v}_1) = \left(1, \mathrm{Re}(\omega_1), \mathrm{Re}(\omega_1^2), \ldots, \mathrm{Re}(\omega_1^{n-1})\right)^\top$ . Normalizándolo, obtenemos las soluciones $(x_1,\ldots,x_n)=\mathrm{Re}(\mathbf{v}_1)/\|\mathrm{Re}(\mathbf{v}_1)\|$ . Como robjohn ha calculado, el factor de normalización es $\sqrt{\dfrac2n}$ y por lo tanto $x_j = \sqrt{\dfrac2n}\cos\left(\dfrac{2\pi j}{n}\right)$ .

Answer 4

El método que propones debería funcionar. Estás tratando de maximizar una forma cuadrática en un espacio vectorial (concretamente el $(n-1)$ -subespacio dimensional de ${\mathbb R}^n$ dada por la ecuación $\sum_{i=1}^n x_i = 0$ ) restringido a vectores de longitud 1 (ese es el efecto de la segunda restricción). La respuesta va a estar relacionada con el valor propio dominante de la matriz correspondiente en ese (sub)espacio.

Answer 5

Algunos experimentos sugieren que para un tamaño razonable $n$ , $$x_i = \sqrt{\frac{2}{n}}\cos\left(2\pi\frac{ i}{n}\right)$$ funciona bien, y da $\sum\limits_{i=1}^nx_ix_{i+1}$ ligeramente por encima de $1-\frac{20}{\; n^2}$ . Está claro que hay más soluciones con una fase diferente.