# $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.

Presuming you have a suitable solver (CPLEX, GUROBI, MOSEK, SCIP, many others), you can solve this as a Mixed-Integer Quadratic Program (by squaring the objective) or as a Mixed-Integer Second Order Cone Problem.

Here is code to solve it in YALMIP under MATLAB.

v = intvar(size(v_o))
optimize([-k <= v <= k, sum(v) == l],norm(v-v_0))
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