# $L_2$ projection with integer constraints and prescribed sum

Suppose I am given a vector $v^0\in\mathbb{R}^n$ and integers $k,\ell\in\mathbb{Z}$. Assuming $k$ is close to zero (e.g. $0\leq k\leq5$), is there an algorithm for solving the following integer optimization problem? $$\boxed{ \begin{array}{rl} \min_v & \|v-v^0\|_2\\ \mathrm{s.t.} & v_i\in\{-k,\ldots,0,\ldots,k\}\ \forall i\\ & \sum_i v_i = \ell. \end{array} }$$ In other words, I wish to approximate $v^0$ with a vector $v$ that sums to $\ell$ and has integer entries between $-k$ and $k$. The $L_2$ norm here is needed.

This looks somewhat like an instance of the knapsack problem, but the $L_2$ norm and potentially negative entries in $v$ have me confused how to formalize this, e.g. using some sort of dynamic programming technique.

v = intvar(size(v_o))
disp(value(v)) $displays the optimal value of v  • Thanks for the tip! Indeed, when$k\$ is small enough you can even reduce it to an integer program rather than a quadratic objective --- my current implementation calls Mosek. I'm really hoping to find a direct algorithm, however! – Justin Solomon Aug 16 '17 at 1:53