# How to find the number of non-zeros weights needed to minimise the distance between a weighted sum and a population

**URL:** <https://discourse.julialang.org/t/how-to-find-the-number-of-non-zeros-weights-needed-to-minimise-the-distance-between-a-weighted-sum-and-a-population/46442>\
**Category:** Optimization (Mathematical)\
**Created:** [September 11, 2020, 9:15am UTC](https://discourse.julialang.org/t/how-to-find-the-number-of-non-zeros-weights-needed-to-minimise-the-distance-between-a-weighted-sum-and-a-population/46442 "2020-09-11T09:15:55Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![sylvaticus](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sylvaticus/32/203883_2.png) [@sylvaticus](https://discourse.julialang.org/u/sylvaticus)\
**Post date:** [September 11, 2020, 9:15am UTC](https://discourse.julialang.org/t/how-to-find-the-number-of-non-zeros-weights-needed-to-minimise-the-distance-between-a-weighted-sum-and-a-population/46442/1 "2020-09-11T09:15:55Z")

</div>

Hello, I need to use some individual elements (x\_n, in my application agricultural farms of which I know every details) as building blocks to reconstruct an observed aggregate V\_d \>=0 for the d dimensions (in my application the agricultural system as we know from census data… hectars of lands, number of farms, cows and so on).

I want to find the minimum number of K non-zero weights so that my distance between the reconstructed aggregated and the observed one is below a threshold.

In mathematical terms the problem can be expressed as:

min\_{x\_n} K  
s.t.  
x\_n \geq 0  
\frac{\sqrt{\sum\_d((\sum\_n x\_n \* a\_{n,d}) - V\_d)^2}}{\sum\_d V\_d} \leq \epsilon  
\sum\_n \mathbf{1}(X\_n \> 0) = K

where the last line in an indicator function.

I can simplify the problem by just minimising the distance given K and then simply check which K is within my tolerance:

min\_{x\_n} \sum\_d((\sum\_n x\_n \* a\_{n,d}) - V\_d)  
s.t.  
x\_n \geq 0  
\sum\_n \mathbf{1}(X\_n \> 0) \leq K

When I try to implement it in Jump however I have a problem with the Hessian (`AssertionError: length(hess_I) > 0`) in both cases:

```julia
using DelimitedFiles

coeff = readdlm(download("https://lef-nancy.org/files/index.php/s/gkxxYxqWcGCYAEM/download"),',') # Few KB
POP = readdlm(download("https://lef-nancy.org/files/index.php/s/4dwiDtDfyoC5mbH/download"),',') # Few Bytes

using JuMP, Ipopt

(N,D) = size(coeff)
ϵ = 0.1

# Rescaling POP to 1 on all dimensions...
scCoeff = 1 ./ POP
POP = ones(D)
coeff = coeff .* scCoeff'
sumPOP = sum(POP[d] for d in 1:D)

upscaling = Model(optimizer_with_attributes(Ipopt.Optimizer)) # would require "using Ipopt" instead of GLPK
@variables upscaling begin
    x[1:N] >= 0;
    K >= 0
end

set_start_value.(x, 1)
set_start_value.(K, 100)
@NLobjective upscaling Min begin
    K
end
@NLconstraints upscaling begin
        sqrt(sum( (sum(coeff[n,d]*x[n] for n in 1:N) - POP[d])^2 for d in 1:D))/sumPOP <= ϵ
end
@NLconstraints upscaling begin
        sum( (x[n] > 0.0) for n in 1:N) == K
end
optimize!(upscaling)

upscaling2 = Model(optimizer_with_attributes(Ipopt.Optimizer)) # would require "using Ipopt" instead of GLPK
@variables upscaling2 begin
    x[1:N] >= 0;
end
set_start_value.(x, 1)
@objective upscaling2 Min begin
    sum( (sum(coeff[n,d]*x[n] for n in 1:N) - POP[d])^2 for d in 1:D)
end
@NLconstraints upscaling2 begin
        sum( (x[n] > 0.0) for n in 1:N) <= 5
end
optimize!(upscaling2)

```

Note that if I remove the constraint on K the model find a (local) minima without problems…

Is there a more specific way to solve these kind of problems ?

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [September 11, 2020, 11:36am UTC](https://discourse.julialang.org/t/how-to-find-the-number-of-non-zeros-weights-needed-to-minimise-the-distance-between-a-weighted-sum-and-a-population/46442/2 "2020-09-11T11:36:35Z")

</div>

I have the impression that your problem can be thought as a case of robust fitting, with outlier elimination. Take a look at this, for example:

> **[RAFF.jl](https://juliapackages.com/p/raff)**
>
> Robust Algebraic Fitting Function project