Problema equivalente a la "Plaza más grande de un cubo"

Question

La "plaza más grande en un cubo" problema, en el que se solicita la plaza más grande en el interior de un cubo, tiene una solución que puede ser visto en esta página, que también dice que el problema general de las dimensiones superiores está sin resolver.

---

         
          ^{MathWorld de la imagen.}

---

El problema es equivalente al siguiente problema de optimización: encontrar dos ortogonal de vectores unitarios en $\mathbb{R}^3$ tal que el máximo de los valores absolutos de todas sus coordenadas es minimizado. Para la "plaza más grande en un cubo" problema de tener la respuesta es no, este mínimo debe ser $2/3$, es decir, que se produce cuando las coordenadas son las $(2/3,2/3,1/3),(1/3,-2/3,2/3)$ (o algunos coordinar permutación-cum-eje de la reflexión de aquellos). ¿Cómo podemos demostrar que esto es de hecho donde el óptimo se produce? Este parece que debería ser algo realmente simple álgebra, pero es eludir mí.

De manera más abstracta, esto es pedir un par de ortogonal de vectores unitarios tal que el máximo de sus $\ell^\infty$-de las normas es minimizado. ¿Qué sucede si nos está tratando de minimizar el más grande de la $\ell^p$-normas, $p > 2$? ¿La minimización de valor tienden a $2/3$$p \to \infty$?

Answer 1

En el estudio de este problema en el caso general, es decir, $m$- dimensional del cubo dentro de $n$-dimensional del cubo para $m<n$, podría tener sentido para buscar en pequeños ejemplos para ganar algo de intuición. A partir de los ejemplos (plaza más grande de (hiper)cubos) uno podría tener la impresión de que las coordenadas de la solución óptima siempre son racionales y, por tanto, el óptimo de la longitud de la arista son siempre de la raíz cuadrada de racionales. En este post voy a argumentar que este no es el caso en general.

Aquí es cómo su formulación como un problema de optimización se generaliza: Vamos a $S$ ser un conjunto de mitad de la $2^m$ vértices de la m-cubo de la longitud de la diagonal de 2 centrado en el origen tal que $S \cup \{-s : s\in S\}$ es todo el conjunto de vértices. Ahora encontrar $2^{m-1}$ unidad-vectores en $\mathbb{R}^n$ de manera tal que cada par de ellos tiene el mismo vector producto como un par en $S$, y tales que el valor absoluto de sus coordenadas en minimizadas.

Por ejemplo, para m=3 se puede tomar como $S$ todos los otros vértices del cubo, que forman un tetraedro regular (ver foto por Kepler) y, a continuación, para cada par de allí vector producto tendría que ser $-\frac{1}{3}$

Un problema potencial con esta formulación como problema de optimización en la práctica es que el número de variables es $n2^{m-1}$ e hay $\frac{2^{m-1}(2^{m-1}+1)}{2}$ ecuaciones cuadráticas.

Junto con esto la optimización de la formulación y métodos que se describen en http://arxiv.org/abs/1407.0683 tengo que calcular algunos casos $f(m,n)$ pequeña $m$$n$. Hay algunos de optimización numérica involucrados, por lo que no es una prueba formal de que el siguiente resultado es óptimo, pero puedo obtener simbólica exacta de los valores de las coordenadas y sin duda es un límite inferior.

En mathworld los casos $f(1,n)$ $f(2,n)$ se explican, de manera que el más pequeño de los casos que parecen ser desconocido se $f(3,n)$. Los casos de $f(3,4)$ $f(3,5) $ también son mencionados en Sloane del oeis: A243309, A243313 .

---

• $f(3,4)$:

El 8 vértices de un mayor 3-cubo dentro de $[0,1]^4$ tiene las siguientes coordenadas:

$$(1, 0, 1-a, b),(1, 0, b, 1-a), (0,c,1-d, 0), (0,c, 0, 1-d),(1, 1-c, 1,d), (1, 1-c,d, 1), (0,1, 1-b, a),(0, 1, a,1-b)$$

donde $a,b,c,d$ son números algebraicos de grado $4$, con la de estos mínimos polinomios y aproximaciones decimales:

$$\begin{align*}a\quad&16x^4 + 8x^3 - 23x^2 + 14x - 2& 0.204901553506651293143\\ b\quad&16x^4 - 24x^3 + 25x^2 - 14x + 1& 0.082734498297453867827\\ c\quad&8x^4 - 32x^3 + 45x^2 - 30x + 1& 0.035139649420907685891\\ d\quad&4x^4 - 4x^3 - x^2 + 4x - 1& 0.287636051804105160970 \end{align*}$$

Esto le da una longitud de la arista s, que tienes la siguiente polinomio mínimo:

$$4x^8 - 28x^6 - 7x^4 + 16x^2 + 16$$

y $1.007434756884279376098253595231$ como aproximación decimal.

---

• $f(3,5)$:

El 8 vértices de un mayor 3-cubo dentro de $[0,1]^5$ tiene las siguientes coordenadas: $$(1, e, 0, e, 0), (1, e, 0, 1, 1-e), (0, 0, e, 0, e), (0, 0, e, 1-e, 1), (1, 1, 1-e, e, 0), (1, 1, 1-e, 1, 1-e), (0, 1-e, 1, 0, e), (0, 1-e, 1, 1-e, 1)$$

donde $e=\sqrt{\frac{3}{2}}-1\approx 0.224744871391589049098$

Esto da como longitud de la arista $\sqrt{11-8\sqrt{\frac{3}{2}}}\approx 1.09637631717731280407593110$.

---

• $f(3,6)$:

El 8 vértices de un mayor 3-cubo dentro de $[0,1]^6$ se encuentran en los vértices de (diagonal en la sección de) el 6-cubo:

$$(0, 1, 1, 0, 1, 0), (0, 0, 0, 1, 1, 1), (1, 0, 1, 0, 0, 1), (1, 1, 0, 1, 0, 0), (1, 0, 0, 1, 0, 1), (1, 1, 1, 0, 0, 0), (0, 1, 0, 1, 1, 0), (0, 0, 1, 0, 1, 1)$$

y esto le da una longitud de la arista de $\sqrt{2}\approx 1.414213562373095048$.

Answer 2

Usted puede reducir un poco las cosas de la siguiente manera. Suponga que los dos vectores son (a,b,c) y (x,y,z). Sin pérdida de generalidad todos los de a, b y c son no negativos. Supongamos que a es mayor que b y c). Escoge un tercer vector (u,v,w) ortogonal a ambos (a,b,c) y (x,y,z). Si u es distinto de cero, entonces se puede añadir una pequeña múltiples de (u,v,w) a (a,b,c) de tal manera que el $\ell_2$ norma aumenta por una ecuación cuadrática, pero la cuantía $\ell_\infty$ norma se reduce en un lineal de la cantidad. Así que después de reescalado tenemos una mejor ejemplo.

No voy a ir a través de todos los casos posibles aquí, pero ahora sabemos que ya sea de u es igual a cero o (WLOG) a=b. La misma prueba también nos dice que el máximo valor absoluto de x, y y z se ha alcanzado dos veces. Probablemente es bastante fácil demostrar, después de un poco de análisis de caso, de que este máximo se alcanza una vez que para un valor positivo y de una vez por un valor negativo, y en los lugares 2 y 3. Si funciona, entonces tenemos que (a,a,b) y (x,-y,y), con una más grande que la de b y x mayor que y en valor absoluto. Esto empieza a parecerse mucho más manejable problema de optimización.

Yo no garantiza que todo esto funciona, pero creo que tiene una buena oportunidad.