计算科学 - 大号2L2具有整数约束和规定总和的投影 - 吾爱随笔录

假设给了我一个向量 $v^0\in\mathbb{R}^n$ 和整数 $k,\ell\in\mathbb{Z}$ . 假设 $k$ 接近于零（例如 $0\leq k\leq5$ )，是否有解决以下整数优化问题的算法？

\begin{aligned} min_{v} & ‖ v - v^{0} ‖_{2} \\ s . t . & v_{i} \in {- k, \dots, 0, \dots, k} \forall i \\ \sum_{i} v_{i} = ℓ . \end{aligned}

$\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} }$ 换句话说，我希望用一个向量

，该向量 v总和为

和

之间具有整数条目。这里需要

范数。

v^{0}

$v^0$

v

$v$

ℓ

$\ell$

- k

$-k$

k

$k$

L_{2}

$L_2$

这看起来有点像背包问题的一个实例，但是 $L_2$ 范数和潜在的负条目让我感到困惑如何将其形式化，例如使用某种动态编程技术。 $v$