5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Justin Solomon Aug 16 '17 at 1:53

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.