chapter05-lattice-programming.tex

% Copyright 2013 Nicolai Hähnle <nhaehnle@gmail.com>
%
% This work is licensed under the Creative Commons Attribution-ShareAlike 3.0
% Unported License, see http://creativecommons.org/licenses/by-sa/3.0/
%
% Among other things, this means that yes, you may take e.g. illustrations from
% the book and use them in your own work. However, (a) you must give proper
% attribution by naming me as its original author and (b) you must make your
% derivative work available under the same or similar license terms.
%
% See the Creative Commons website for the exact licensing terms.

\chapter{Lattice programming}

We now consider the problem of deciding whether a given convex body $K \subset \R^d$
contains a point from a lattice $\Lambda \subset \R^d$.
As was already hinted at in the previous chapter,
the Flatness Theorem plays a crucial role in this problem.
We have seen that if the lattice width of $K$ is large,
then the answer is ``yes'': $K$ does contain a lattice point.
On the other hand,
if the lattice width of $K$ is small,
then recursing into all lattice hyperplanes that intersect $K$ is not too bad.
The resulting recursion tree can still be quite large:
if our bound on the lattice width is $d^c$ when we recurse,
then the number of leaves is bounded from above by
\[
  d^c \cdot (d-1)^c \cdots 2^c = 2^{O(d \log d)},
\]
which will dominate the running time of our algorithm.
Indeed, it is an important open research problem
whether the lattice programming problem can be decided
with a running time whose dependence on $d$ is only $2^{O(d)}$.

How does one determine the lattice width of $K$?
In the previous chapter,
we have seen that we can get an approximation if we approximate $K$ by its Löwner-John ellipsoid.
This ellipsoid can be approximated efficiently using linear programming techniques,
and we could use such approximations as a black box.
However, there is a slight technical issue:
if $K$ is given by a separation oracle rather than explicitly,
then all black box algorithms require some knowledge about the minimum volume of $K$.
To sidestep this issue,
we will follow an approach in which the
ellipsoid method and lattice programming recursion are integrated in a single algorithm.

Throughout this chapter, we will assume that we can perform basic operations, including square roots,
on real numbers in constant time.
This is obviously a simplification,
since ironically one does not compute with reals on real computers.
In reality, the algorithms outlined in this chapter would be implemented using approximations with rational numbers.
It turns out that this can be done without loss of correctness and within essentially the same asymptotic running time.
However, those details tend to become highly technical, and we avoid them for clarity of presentation.



\section{Separation and the half-ball lemma}

We assume that convex bodies $K \subset \R^d$ are given by an enclosing ellipsoid $E \supset K$
and access to a \emph{separation oracle}.
The separation oracle is a black box algorithm which, given $z \in \R^d$,
tells us whether $z \in K$.
Furthermore, if $z \not\in K$, it returns a separating hyperplane $a^Tx \leq \beta$,
see Figure~\ref{fig:separating-hyperplane}.
We assume that each call to the oracle takes constant time.
\begin{figure}
  \begin{center}
    \begin{tikzpicture}
      \fill (0,0) circle[radius=2pt] node[below] {$z$};

      \draw[thick,fill=black!10] (3,0.5) node {$K$} circle[radius=1.2cm];

      \draw[thick] (2,-1) node[below] {$a^Tx \leq \beta$} -- (-1,2);
      \draw[->] (-0.5,1.5) -- +(-0.5,-0.5) node[above] {$a$};
    \end{tikzpicture}
  \end{center}
  \caption{A separating hyperplane exists for every $z \not\in K$.}
  \label{fig:separating-hyperplane}
\end{figure}

\begin{remark}
  In fact, analogous results can be achieved even if $K$ is only given by a \emph{weak} separation oracle,
  where some imprecision is allowed in the oracle for points close the boundary of $K$.
  In this case, most of the analysis can proceed as if the oracle were in fact supplying the answer
  for a convex body $K'$ that is only slightly different from $K$.
  We will ignore such details to keep the presentation simple.
\end{remark}

We are given an ellipsoid $E \supset K$.
In fact, we can assume that $E$ is a ball with center $z'$
by applying the same linear transformation to $E$, $K$, and $\Lambda$.
We can now compute a closest vector $z \in \Lambda$ to $z'$ as a candidate lattice point
in time $2^{O(d)} \poly(b)$.
If $z \not\in E$, we can conclude that $K$ contains no lattice point.
Otherwise, we can feed $z$ into the separation oracle for $K$.
If $z \in K$, we are done.

Otherwise, if $z \not\in K$,
we obtain a linear inequality $a^Tx \leq \beta$ that separates $z$ from $K$.
In fact, the inequality splits $E$ into two parts,
and we are guaranteed that $K$ is entirely contained in one of them.
We will now compute a new ellipsoid $E'$ that contains this second part,
see Figure~\ref{fig:ellipsoid-method}.
\begin{figure}
  \begin{center}
  \begin{tikzpicture}
    \fill (0,0) circle [radius=2pt];
    \draw (0,0) node[below left] {$z$};

    \draw[very thick,fill=black!10] (1,0.1) -- (1.3,0.7) -- (2.3,0.6) -- (2.3,-0.1) -- (1.5,-0.5) --cycle;

    \begin{scope}[rotate=12,xscale=3]
      \draw (0,0) circle [x radius=1,y radius=1];
      \draw (0,-1.5) -- (0,1.5);
      \draw (0.333,0) circle [x radius=0.666,y radius=1.16];
    \end{scope}
  \end{tikzpicture}
  \end{center}
  \caption{Computing a tighter ellipsoid containing $K$.}
  \label{fig:ellipsoid-method}
\end{figure}

To simplify the argument,
assume first that $E$ is a unit ball centered at the origin
and the linear equality is $x_1 \geq -\eta$ with $\eta \geq 0$.
This can always be achieved by an affine transformation of $E$ and possibly by shifting the hyperplane
so that the enclosed part of $E$ becomes larger.
By symmetry, the smallest volume ellipsoid containing $E \cap \{ x_1 \geq -\eta \}$ is of the form:
\[
  E' = \{ x \in \R^d ~:~ \alpha^2 (x_1 - c)^2 + \beta^2 (x_2^2 + \dots + x_d^2) \leq 1 \}
\]
Intuitively, we expect $|\alpha| > 1$ and $|\beta| < 1$ so that $E'$ results from the unit ball
by compressing it in the $x_1$ direction and scaling it in the other directions.
The centroid of $E'$ is at $(c,0,\ldots,0)$.

The point $x_1$ should lie on the boundary of $E'$, which implies:
\[
  \alpha^2 (1-c)^2 = 1 \quad\implies\quad \alpha^2 = \frac{1}{(1-c)^2}
\]
Furthermore, the sphere $\partial E \cap \{ x_1 = -\eta \}$ should also lie on the boundary of $E'$.
For points in this set, one has
\[
  x_2^2 + \dots + x_d^2 = 1 - \eta^2,
\]
and hence we obtain the condition
\[
  \alpha^2 (c + \eta)^2 + \beta^2 (1 -\eta^2) = 1
\]
on the parameters of $E'$.
We can solve for $\beta^2$:
\begin{align*}
  \beta^2
    &= \frac{1}{1 - \eta^2} \left( 1 - \frac{(c+\eta)^2}{(1-c)^2} \right) \\
    &= \frac{(1-c)^2 - (c+\eta^2)}{(1-c)^2 (1-\eta^2)} \\
    &= \frac{1-2c - 2c\eta - \eta^2}{(1-c)^2 (1-\eta)(1+\eta)} \\
    &= \frac{(1-\eta)(1+\eta) - 2c(1 + \eta)}{(1-c)^2 (1-\eta)(1+\eta)} \\
    &= \frac{(1-\eta) - 2c}{(1-c)^2 (1-\eta)}
\end{align*}
Now that we have expressed both $\alpha$ and $\beta$ in terms of $c$,
observe that
\[
  \left(\frac{\vol(E)}{\vol(E')}\right)^2 = \alpha^2 (\beta^2)^{d-1} = \frac{(\kappa - 2c)^{d-1}}{(1-c)^{2d} \kappa^{d-1}} = \frac{(1 - \frac{2c}{\kappa})^{d-1}}{(1-c)^{2d}},
\]
where $\kappa = 1 - \eta$.
We want this fraction to be as large as possible,
so that the volume of $E'$ is minimal.
Let us compute the derivative with respect to $c$:
\[
  2d \frac{(1 - \frac{2c}{\kappa})^{d-1}}{(1-c)^{2d+1}} - \frac{(d-1) \frac{2}{\kappa} (1-\frac{2c}{\kappa})^{d-2}}{(1-c)^{2d}}
\]
We set this quantity to $0$ and simplify to
\begin{align*}
  d(1-\frac{2c}{\kappa}) &= \frac{d-1}{\kappa} \cdot (1-c).
\end{align*}
Isolating the multiples of $c$, we get
\[
  d - \frac{d-1}{\kappa} = \frac{2d - (d-1)}{\kappa} c
\]
and eventually:
\[
  c = \frac{1 - \eta d}{d + 1}
\]
Note how a larger $\eta$ means that the centroid of $E'$ moves closer to the origin.
Intuitively, this means that $E'$ approaches the unit ball,
and we do not get a genuinely new ellipsoid if $\eta > \frac{1}{d}$.
Still, we do obtain the following result:

\begin{lemma}[Generalized half-ball lemma]
  \label{lemma:generalized-half-ball}
  Let $E \subseteq \R^d$ be an ellipsoid and let
  $a^Tx \leq \beta$ be an inequality.
  Let
  \[
    \eta := \max(\{ 0 \} \cup \{ r > 0 ~:~ r \star E \text{ satisfies } a^Tx \leq \beta \}).
  \]
  There is a global constant $c > 0$
  such that if $\eta \leq \frac{1}{2d}$,
  there exists an ellipsoid $E' \supset E \cap \{ x ~:~ a^Tx \leq \beta \}$
  with $\vol(E') \leq e^{-c/(d+1)}\vol(E)$.
\end{lemma}
\begin{proof}
  The condition on $\eta$ ensures that a linear transformation can be used to reduce the problem to the setting we just discussed,
  with the same value for $\eta$.
  The ellipsoid computed above satisfies
  \begin{align*}
    \frac{\vol E'}{\vol E}
      &= \alpha^{-1} \beta^{-(d-1)}
  \end{align*}
  Plugging in the value for $c$ that we obtained above, we get
  \begin{align*}
    1 - c &= \frac{d(1 + \eta)}{d + 1} \\
    \alpha^2 &= \frac{1}{(1-c)^2} = \left( \frac{d+1}{d(1+\eta)} \right)^2 \\
    \beta^2 &= \frac{1}{1 - \eta^2} \left( 1 - \frac{(c+\eta)^2}{(1-c)^2} \right) = \frac{1}{1-\eta^2} \left(1 - \frac{1}{d^2} \right) = \frac{d^2 - 1}{d^2(1 - \eta^2)}
  \end{align*}
  For the inverses, we can use $1 + x \leq e^x$ to estimate
  \begin{align*}
    \alpha^{-2} &= \left(\frac{d(1+\eta)}{d+1}\right)^2 = \left(1 - \frac{1 - d\eta}{d+1}\right)^2 \leq e^{-2 \frac{1 - d\eta}{d+1}} \\
    \beta^{-2} &= \frac{d^2(1 - \eta^2)}{d^2 - 1} = 1 + \frac{1 - d^2\eta^2}{d^2-1} \leq e^{\frac{1 - d^2\eta^2}{d^2 - 1}}
  \end{align*}
  We can put these together to get a bound on the ratio of squared volumes:
  \begin{align*}
    \alpha^{-2} \beta^{-2(d-1)}
      &\leq e^{-2 \frac{1-d\eta}{d+1} + (d-1) \frac{1 - d^2\eta^2}{d^2 - 1}}
      = e^{-\frac{2 - 2d\eta - 1 + d^2\eta^2}{d+1}}
      = e^{-\frac{(1 - d\eta)^2}{d+1}}
  \end{align*}
  Observe that $1 - d\eta \geq 1/2$ and the desired bound on the volume follows.
  In fact, we can compute the constant $c$:
  \begin{align*}
    \frac{\vol E'}{\vol E}
    &\leq e^{-\frac{1}{2}\cdot \frac{(1/2)^2}{d+1}} = e^{-\frac{1/8}{d+1}}.
  \end{align*}
  It remains to be shown that $E' \supset E \cap \{ x ~:~ a^Tx \leq \beta \}$.
  We show this in the simplified setting of the discussion before,
  where $E$ is a unit ball and the inequality is simply $x_1 \geq -\eta$.
  Due to convexity, it suffices to show that every $x \in \partial E$ with $x_1 \geq -\eta$ is contained in $E'$.
  Let
  \[
    f(x) = \alpha^2 (x_1-c)^2 + \beta^2(x_2^2 + \dots + x_d^2)
  \]
  For points on the surface of $E$, we can think of $f$ as a function in $x_1$ only:
  \[
    f(x_1) = \alpha^2 (x_1-c)^2 + \beta^2(1-x_1^2)
  \]
  This is a quadratic function with leading coefficient $\alpha^2 - \beta^2 > 0$.
  Since $f(-\eta) = f(1) = 1$, it follows that $f(x_1) < 1$ for all $-\eta < x_1 < 1$.
  This completes the proof.
\end{proof}








\section{Weak splits imply good recursion}

Let us return to the problem of lattice programming.
As we discussed before, if the closest vector $z \in \Lambda$
to the center of the ball $E \supset K$ is not contained in $K$,
then we can use the resulting separating hyperplane to get a new ellipsoid bounding $K$.
We obtain a sequence of ellipsoids with exponentially decreasing volume,
unless the separating hyperplane lies so far away from the center of $E$
that the $\eta$ in Lemma~\ref{lemma:generalized-half-ball} is too big.

Let $z'$ be the center of $E$ and $r$ its radius.
We have
\[
  \mu(\Lambda) \geq \|z - z'\|_2 \geq \eta r \geq \frac{r}{2d}
\]
in this case, because $z$ does not lie in $\eta \star E$ by the definition of $\eta$
and the fact that $z$ is cut off by the separating hyperplane.
Using Theorem~\ref{thm:transference-bound},
this implies
\[
  \lambda_1^\star(\Lambda) \leq \frac{d}{\mu(\Lambda)} \leq \frac{2d^2}{r},
\]
which is a statement about lattice hyperplanes of $\Lambda$.
Let $y \in \Lambda^\star$ be a shortest vector.
Then adjacent lattice hyperplanes orthogonal to $y$ lie at distance
\[
  \frac{1}{\|y\|_2} \geq \frac{r}{2d^2},
\]
which implies that at most $4d^2 + 1$ lattice hyperplanes orthogonal to $y$ intersect $E$.
We can now reduce the original problem to one lower-dimensional problem for each of those hyperplanes,
and this gives us the informal outline for our algorithm:
\begin{enumerate}
  \item Assume that $E \supset K$ is a ball, either by an explicit or implicit linear transformation applied
    to $E$, $K$, and $\Lambda$.

  \item Compute a shortest vector $y \in \Lambda^\star$.
    If $\|y\|_2 \leq \frac{2d^2}{r}$,
    there are at most $4d^2 + 1$ lattice hyperplanes orthogonal to $y$
    that intersect $E$.
    We can solve the problem by recursing on the lower-dimensional problem
    in each of these hyperplanes.\footnote{%
Observe that the intersection of an ellipsoid with a hyperplane is an ellipsoid.
Furthermore, the ratio $\vol(E)/\det(\Lambda)$ in the lower-dimensional instances can be polynomially bounded
by the same ratio for the original instance.}
    If none of the lattice hyperplanes orthogonal to $y$ intersect $E$,
    we know that $K$ does not contain a lattice point.

  \item If $\|y\|_2 > \frac{2d^2}{r}$,
    then by the reverse of the argument above,
    there is a closest vector $z \in \Lambda$ at distance at most $\frac{r}{2d}$
    from the center of $E$, which we compute.

  \item Query the separation oracle for $K$ with $z$.
    If $z \in K$, a lattice point in $K$ has been found.

  \item Otherwise,
    we can compute a new ellipsoid using Lemma~\ref{lemma:generalized-half-ball} and repeat.
    The new ellipsoid's volume is smaller by a factor of $e^{-c/(d+1)}$.
\end{enumerate}
This algorithm is clearly correct.
It remains to bound its running time.
We clearly have a bound of
\[
  (c')^d d^2 (d-1)^2 \cdots 2^2 = 2^{O(d \log d)}
\]
on the size of the recursion tree.
But how often do we iterate with a smaller ellipsoid before we enter the recursion?

We will bound this number of iterations using the ratio $\vol E / \det \Lambda$,
which is unaffected by linear transformations.
Let $M_0 := \vol E  / \det \Lambda$ be the initial ratio.
After $t$ iteration, the ratio has dropped to at most $e^{-ct/(d+1)} M_0$.

\begin{lemma}
  If $\vol E / \det \Lambda < d^{2d} (\vol B(0,1))^2$,
  where $E$ is a ball of radius $r$,
  one has $\lambda_1^\star \leq \frac{2d^2}{r}$.
\end{lemma}
\begin{proof}
  Consider the ball $B$ of radius $\frac{2d^2}{r}$ around the origin.
  \[
    \vol B = \left(\frac{2d^2}{r}\right)^d \vol B(0,1)
  \]
  We have
  \[
    d^{2d} (\vol B(0,1))^2 > \frac{\vol E}{\det \Lambda} = r^d \vol B(0,1) \det \Lambda^\star
  \]
  and so
  \[
    \vol B > 2^d \det \Lambda^\star
  \]
  which implies the result by Minkowski's theorem.
\end{proof}

That is, once the relative volume of $\vol E$ becomes small enough,
we are guaranteed to go into the recursive step.
We can bound the number of iterations before this happens by observing that we must have
\begin{align*}
  e^{-ct/(d+1)} M_0 > d^{2d} (\vol B(0,1))^2
\end{align*}
which implies
\[
  t \leq O(d (d \log d + \log M_0))
\]
for the number $t$ of iterations.

\begin{theorem}
  There is an algorithm that,
  given a lattice $\Lambda \subset \Q^d$ and a convex body $K$ given by a separation oracle
  and an enclosing ellipsoid $E$,
  either finds a lattice point in $K$ or asserts that none exist
  in time $2^{O(d \log d)} \cdot \poly(b, \log(\vol E / \det \Lambda))$.
\end{theorem}