relative weights with cutoffs

Question

I have a vector of positive numerical values. I need to normalize it so that the sum of the values is 1 (e.g. a probability). This is simple just use x_i/sum(x) as weights. but here is the caveat: I need that no weight will be less than some minimum cutoff, and not weight is greater than some maximum cutoff. Now, this means two things: First, it means that there are cases with no solutions (e.g. 3 objects can't be weights if the maximum cutoff is 0.2). Second, it means that the "relativity" of weights is broken. That is, in standard normalizations (where w_i is the weight given to x_i for all i), w_i/w_j=x_i/x_j for all i,j. with cutoffs, this can't be done. more Formally I'd like to find a function w=rwc(x,min,max) where x is a vector, that returns a vector of the same length that has the following properties:

1) sum(w)=1

2) min <= w_i <= max for all i

3) if x_i <= x_j then w_i<=w_j for all i,j

4) if w_i and w_j are both different from the cutoffs (min and max) then they keep relativity: that is, if min < w_i < max and min < w_j < max then w_i/w_j=x_i/x_j

if there is no solution NULL should be returned.

so my question is:

a) how do you suggest doing that (in R or any other language)?

b) given x, can there be more than one solution (that is, at least two different vectors, w and v, each conforming to the formal requirements above)

This is not strictly an R problem but I encountered it within an project i'm doing in R, so I post it as R. any suggestion for better classification are welcomed.

update

Following the discussion below and after more thoughts it seems necessary to add a fifth requirement to the the 4 above: 5) of all the possible assignments of weights satisfying 1-4, W is the one with minimum number of extreme weights (min or max).

here is a my r code that (hopefully) does that:

#
mwc = function(x,mxw=1,mnw=0) {
cake = 1
agnts = 1:length(x)
result = numeric(length(x))
while(cake>0 & length(agnts)>0) {
    tmp = cake*x[agnts]/sum(x[agnts])
    low = which(tmp<mnw)
    high = which(tmp>mxw)
    if(length(low)+length(high)==0 ) {
        result[agnts] = tmp[agnts]
        break;
    }
    if (length(low)>0) {
        result[agnts[low]] = mnw
    }
    if (length(high)>0) {
        result[agnts[high]] = mxw
    }
    cake = 1-sum(result)
    agnts=agnts[-c(low,high)]
}
if (cake<0) return(NULL) #no solution
if (abs(sum(result)-1)>1e-17) return(NULL)
return(result)
}   
# the end

Answer 1

a)

I suggest a brute-force iterative algorithm.

1. Let x' = x
2. Calculate sum(x')
3. Calculate cut-off limits min_x, max_x
4. Calculate x' from x, adjusting all values outside the range [min_x, max_x]
5. Repeat 2-4 until x' is stable
6. Calculate w

In most cases the number of iterations should be few.

b) If there is a min or a max (but not both) the solution vector is unique.

If there is both a min and a max I'm not sure. It feels like it should be unique, but I cannot find an easy proof for it.

Answer 2

Do you mean something like this? The example is in Haskell, "[ ]" means an empty list.

weights :: [Double] -> Double -> Double -> [Double]
weights my_vector min max = 
  let s = sum my_vector
      try = map (/s) my_vector
  in if all (>=min) try && all (<=max) try
        then try
        else []

OUTPUT:
*Main> weights [1,2,3,4] 0 2
[0.1,0.2,0.3,0.4]
*Main> weights [1,2,3,4] 1 2
[]

UPDATE:
Here's a rough direction (Haskell again), based on this:

import Data.List
import Data.Ord

normalize :: Double -> Double -> Double -> Double -> Double
normalize targetMin targetMax rawMax val =
  let maxReduce = 1 - targetMax/rawMax
      factor = maxReduce * (abs val) / rawMax
  in max ((1 - factor) * val) targetMin

weights :: [Double] -> Double -> Double -> [Double]
weights myVector targetMin targetMax = 
  let try = map (/(sum myVector)) myVector
  in if all (>=targetMin) try && all (<=targetMax) try
        then try
        else weights normalized targetMin targetMax
    where normalized = 
            let targetMax' = (maximum myVector * targetMin / minimum myVector)
            in map (\x -> normalize targetMin targetMax' (maximum myVector) x) myVector

OUTPUT:
*Main> weights [4,4,4,1000] 0.1 0.7
[0.10782286784365082,0.10782286784365082,0.10782286784365082,0.6765313964690475]
*Main> weights [1,1,1000000] 0.05 0.8
[0.12043818322274577,0.12043818322274577,0.7591236335545084]

Answer 3

This is my second answer which now, I hope, addresses requirement 4) as well. It seems to me that if requirement 4) is to apply then we must divide all elements that are not assigned as cutoffs by:

    denominator = sum non_cutoff_elements / (1 - sum cutoff_elements)

Where 'cutoff_elements' are expressed as their cutoff values. This recursive code tries, I hope, to exhaust the combinations of cutoff assignments. The code seems to solve both amit and rici's examples in their comments. Haskell again:

import Data.List
import Data.Ord

weights :: [Double] -> Double -> Double -> [[Double]]
weights myVector tMin tMax = 
  weights' 0
    where 
      weights' count
        | count == length myVector + 1 = []
        | otherwise =
            let new_list = take count myVector 
                           ++ replicate (length myVector - count) tMax
            in fromLeft new_list 0 ++ weights' (count+1)
                where 
                  fromLeft list' count' = 
                    let non_cutoffs = filter (\x -> x/=tMin && x/=tMax) list'
                        real_count = length list' - length non_cutoffs
                        cutoffs_l = filter (\x -> x==tMin) list'
                        cutoffs_r = filter (\x -> x==tMax) list'
                        denom = sum non_cutoffs / (1 - (sum $ cutoffs_l ++ cutoffs_r))
                        mapped = cutoffs_l ++ (map (/denom) non_cutoffs) ++ cutoffs_r
                        next_list = let left = tMin : cutoffs_l
                                        right = drop 1 cutoffs_r
                                    in left ++ non_cutoffs ++ right
                    in if count' == real_count
                          then []
                          else if sum cutoffs_r > 1 || sum cutoffs_l > 1 
                                  || sum cutoffs_r + sum cutoffs_l > 1
                                  then fromLeft next_list (count'+1)
                          else if sum mapped == 1 && all (>=tMin) mapped && all (<=tMax) mapped
                                  then mapped : fromLeft list' (count'+1)
                                  else fromLeft next_list (count'+1)

OUTPUT:
*Main> weights [4,4,4,1000] 0.1 0.7
[[0.1,0.1,0.1,0.7],[0.1,0.1,0.10000000000000009,0.7],[0.1,0.10000000000000003,0.10000000000000003,0.7],[0.10000000000000002,0.10000000000000002,0.10000000000000002,0.7]]
Rounded to 14 decimal places: [[0.1,0.1,0.1,0.7],[0.1,0.1,0.1,0.7],[0.1,0.1,0.1,0.7],[0.1,0.1,0.1,0.7]]

*Main> weights [1,1,1000000] 0.05 0.8
[[5.0e-2,0.1499999999999999,0.8],[9.999999999999998e-2,9.999999999999998e-2,0.8]]
Rounded to 14 decimal places: [[0.05,0.15,0.8],[0.1,0.1,0.8]]