5
$\begingroup$

Consider a strictly convex function $f: \mathbb{R}^d \rightarrow \mathbb{R}$.

Let $x^* = \min_{\mathbb{R}^d} f(x)$ denote the (unique) minimum of this function over $\mathbb{R}^d$. Similarly, let $x_{\text{int}} = \min_{\mathbb{Z}^d} f(x)$ denote a minimum of this function over $\mathbb{Z}^d$

I am wondering: is it true that $x_{\text{int}}$ is one of the $2^d$ "roundings" of $x^*$. In other words, is it true that:

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

If so, could someone outline a proof (or provide a counterexample if false)?

$\endgroup$
1
  • 2
    $\begingroup$ hardmath is right. But just to emphasize the point $x^*$ and $x_{\text{int}}$ can be arbitrarily far apart. $\endgroup$ – Michael Grant Mar 31 '15 at 13:51
4
$\begingroup$

This holds in one dimension, that a strictly convex function $f:\mathbb{R} \to \mathbb{R}$ with minimum at $x^*$ on the real line will attain its minimum on $\mathbb{Z}$ either at $\lfloor x^* \rfloor$ or $\lceil x^* \rceil$ (or both). [Note that a strictly convex real function need not attain a minimum value, either at real or integer arguments, e.g. $f(x) = e^x$.]

However it fails in dimension two and higher. We sketch the construction of an example in $\mathbb{R}^2$, using a quadratic polynomial as our strictly convex function. We can arrange that the minimum in the real plane occurs arbitrarily far away from where the minimum over the integer lattice occurs.

Pick an integer point $(m,n)$ with coprime coordinates, so that the line segment connecting it to the origin $(0,0)$ contains no other integer point. Take this line segment to be the major axis of an ellipse whose minor axis is small enough that the ellipse and its interior contain no other integer points, which we describe with a quadratic polynomial:

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

Note that the ellipse is centered on the midpoint of its major axis, so that $P$ is of homogeneous degree 2. Then $f(x,y) = P\left(x - \frac{m}{2},y - \frac{n}{2}\right)$ is strictly convex, assuming the leading coefficients are positive, and the minimum of $f:\mathbb{R}^2 \to \mathbb{R}$ occurs at that center:

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

The ellipse itself is a level curve where $f$ attains the value $1$, so that this, the minimum of $f$ on the integer lattice, occurs at both $(0,0)$ and $(m,n)$. All other integer lattice points are outside the ellipse, so $f$ has a greater value at all those points.

Thus the real minimum argument can be as far from the integer minimum argument as we please, making the semi-major axis longer by finding a larger coprime pair $(m,n)$.

$\endgroup$
7
  • $\begingroup$ Thank you for this really well-thought out example. $\endgroup$ – Elements Mar 31 '15 at 16:04
  • $\begingroup$ Shot in the dark: is there some additional condition that we can impose on $f$ to upper bound the distance between $x^*$ and $x_{\text{int}}$ $\endgroup$ – Elements Mar 31 '15 at 17:35
  • 1
    $\begingroup$ I believe requiring the Hessian matrix (of 2nd derivatives) to be well-conditioned has that effect. $\endgroup$ – hardmath Mar 31 '15 at 18:55
  • $\begingroup$ I think you're right. $\endgroup$ – Michael Grant Apr 1 '15 at 18:50
  • 1
    $\begingroup$ Consider a strictly convex quadratic function for $f$, so that its level sets are just ellipses. To construct an example where $x^*$ and $x_{\text{int}}$ are far apart requires that those ellipses be extremely thin so that they can be "threaded" through the lattice without touching lattice points. But narrow ellipses require Hessian matrices with high condition numbers. $\endgroup$ – Michael Grant Apr 8 '15 at 22:07

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.