# “Most Similar Vector Problem” on an Integer Lattice

I am currently working on problem that I think could be expressed as an integer lattice problem, and hoping to find some guidance on this forum.

Given $u \in \mathbb{R}^n$ and a bounded integer lattice $L = \mathbb{Z}^n \cap [-M,M]^n$, I would like to find an integer vector $v \in L$ such that the angle between $u$ and $v$ is as small as possible. That is, I would like $$v \in \text{argmax}_{w \in L} \frac{u.w}{\|u\|\|w\|}$$

Here, the objective function is just the cosine between the vectors $u$ and $w$.

I am wondering if this problem can be formulated as a well-known integer lattice problem (such as a closest vector problem). If so, is there an algorithm that I could use to solve it? Any help or resources would be greatly appreciated.

WLOG we can assume $\|u\|=1$ (otherwise replace $u$ with $u/\|u\|$). Now the decision problem is, given $\alpha$, to determine whether there exists $w$ such that $u \cdot w / \|w\| \ge \alpha$, i.e., such that $(u \cdot w)^2 \ge \alpha^2 \|w\|^2$. Define
$$\Phi(w) = \alpha \|w\|^2 - (u \cdot w)^2.$$
Note that $\Phi$ is a quadratic function in the unknowns $w_1,\dots,w_n$, and the decision problem can be solved by maximizing $\Phi(w)$ subject to the constraints $-M \le w_i \le M$. The answer to the decision problem is yes iff there's a solution to this integer quadratic program where $\Phi(w) \ge 0$. Now if you could solve the decision problem, you could use binary search on $\alpha$ to find the largest $\alpha$ for which a solution exists.