Find vector with values in [0, c_max] such that it sums to K [closed]

Question

General problem

I am trying to find an analytical solution to the following problem: Given a vector $v$ with non-negative entries, find a way to normalize it into a vector $v'$ such that:

1. If $v_i < v_j$, then $v_i' < v_j'$
2. $v'_i \in [0, c_\max]$, so each entry is bounded below and above
3. $\sum_i v'_i = K$

I have been trying to find a non-iterative solution for a few days. I want to find a solution that only uses "simple" operations, eg rescaling, subtracting the mean, etc, but I simply cannot find anything.

Typical values

Some "numerical" details for the problem I am interested in:

• $v$ contains $N > 1$ values, say 100 or 1000, but the solution should not depend on the length.
• $c_\max$ is a scalar, and $K$ is also a scalar.

Ideally, I would like to use operations that can be computed easily in numpy and by simple function, I mean I would like to use only differentiable operations, or in the worst case if not possible, some min/max, but no clipping.

Special case

For the special case $c_\max = 2$, you can do the following:

$\mu = \frac{1}{N}\sum_i v_i$. Let $m = \max_i |v_i|$. Then, the vectoz $v'$ such that $v'_i = 1 + \frac{v_i - \mu}{m}$ works. I don't know how to generalize this to the general case, or even whether this approach can generalize.

Any suggestions on how to proceed would be extremely helpful.

Answer 1

This question is not research level and would be more appropriate on Mathematics SE. That said, the following is a simple answer.

---

Let $N$ be the dimension and $\bar1 = (1,\dots,1) \in \mathbb R^N$ the vector of ones. There are three cases:

• If $K > Nc_\max$, then clearly there is no $v'$ satisfying conditions 2 and 3.
• If $K = Nc_\max$, then $v' = c_\max\bar1$ is the unique vector satisfying 2 and 3. This is only compatible with condition 1 if $v = \alpha\bar1$ for some $\alpha>0$, otherwise the three conditions cannot all be met.
• Lastly, suppose $K < Nc_\max$ and let $\delta = \min\{\frac KN,c_\max - \frac KN\} > 0$. Notice that if $w$ is any vector with $\lVert w\rVert_\infty < \delta$ and $w_1+\cdots+w_N = 0$, then $v' = \frac KN\bar1+w$ satisfies 2 and 3. I claim we can find such a $w$ so that 1 holds as well, namely, let $w = \varepsilon(v - \mu\bar1)$ where $\mu = \frac1N(v_1+\cdots+v_N)$ is the mean of the components of $v$ and $\varepsilon > 0$ is small enough that $\lVert w\rVert_\infty < \delta$. (E.g., $\varepsilon = \frac\delta{2\max_i\lvert v_i-\mu\rvert}$ if $v \ne \mu\bar1$. If $v=\mu\bar1$, then $w=0$ works and $\varepsilon$ is irrelevant.) Then, $v'_j-v'_i = w_j-w_i = \varepsilon(v_j-v_i)$ and so $v_j'>v_i'$ if and only if $v_j>v_j$.

So it's easy to decide given $N,K,c_\max,v$ if there is any such $v'$ and when there is, we can find one using only scaling and taking the mean of the $v_i$.