Es la solución óptima de un estrictamente convexa de la función en $\mathbb{Z}^d$ redondeado versión de su solución óptima sobre $\mathbb{R}^d$

Question

Considere estrictamente convexa de la función $f: \mathbb{R}^d \rightarrow \mathbb{R}$.

Deje $x^* = \min_{\mathbb{R}^d} f(x)$ denotar el (único) mínimo de esta función por encima de la $\mathbb{R}^d$. Igualmente, os $x_{\text{int}} = \min_{\mathbb{Z}^d} f(x)$ el valor mínimo de esta función por encima de la $\mathbb{Z}^d$

Me pregunto: ¿es cierto que $x_{\text{int}}$ es uno de los $2^d$ "redondeados" de $x^*$. En otras palabras, es cierto que:

$$x_{\text{int}} \in \big\{x \in \mathbb{Z}^d ~\big|~ x_i = \lceil{x^*_i}\rceil \text{ or } \lfloor{x^*_i}\rfloor \text{ for } i = 1,\ldots d\big\}$$

Si es así, podría alguien esquema de una prueba (o proporcione un contraejemplo si falso)?

Answer 1

Esto se mantiene en una dimensión, que estrictamente convexa de la función $f:\mathbb{R} \to \mathbb{R}$ mínimo en $x^*$ sobre la línea real alcanzará su mínimo en $\mathbb{Z}$ $\lfloor x^* \rfloor$ o $\lceil x^* \rceil$ (o ambos). [Tenga en cuenta que estrictamente convexa de la real función de la necesidad de no alcanzar un valor mínimo, ya sea real o argumentos enteros, por ejemplo,$f(x) = e^x$.]

Sin embargo no en la dimensión dos y superior. Boceto de la construcción de un ejemplo en $\mathbb{R}^2$, utilizando un polinomio cuadrático como nuestro estrictamente convexa de la función. Podemos organizar que el mínimo en el avión real se produce arbitrariamente lejos de donde el mínimo sobre el entero de celosía se produce.

Escoge un entero punto de $(m,n)$ con coprime coordenadas, de modo que el segmento de línea que une al origen $(0,0)$ contiene ningún otro punto entero. Tome este segmento de línea para ser el eje mayor de una elipse cuyo eje menor es lo suficientemente pequeño para que la elipse y en su interior contienen ningún otro número entero de puntos, que se describe con un polinomio cuadrático:

$$ P\left(x - \frac{m}{2},y - \frac{n}{2}\right) = 1 $$

Tenga en cuenta que la elipse centrada en el punto medio de su eje mayor, por lo que el $P$ es homogéneo de grado 2. A continuación, $f(x,y) = P\left(x - \frac{m}{2},y - \frac{n}{2}\right)$ es estrictamente convexa, suponiendo que el líder de los coeficientes son positivos, y el mínimo de $f:\mathbb{R}^2 \to \mathbb{R}$ se produce en ese centro:

$$ f\left(\frac{m}{2},\frac{n}{2}\right) = 0 $$

La elipse en sí es una curva de nivel donde $f$ alcanza el valor de $1$, por lo que este, el mínimo de $f$ sobre el entero de rejilla, se produce en ambos $(0,0)$$(m,n)$. Todos los demás entero entramado puntos están fuera de la elipse, por lo $f$ tiene un mayor valor en todos los puntos.

Por lo tanto el mínimo argumento puede estar lejos de la entero mínimo argumento como queramos, haciendo que el semi-eje mayor no por la búsqueda de una mayor coprime par $(m,n)$.