如何求解这样的比率函数？

Question

假设W是一个已知向量，这里我想求唯一解a，使得：

Sum(min(1,W(i)/a))=M (M is known)

这种函数有具体的名称吗？如果你们能给我 link 一些说明，那就太好了。

谢谢。

Answer 1

我假设 W 的条目是正的；负数在您的问题上下文中没有多大意义（因为您在 1 而不是 -1 处截断），而零没有任何贡献，可以使用 nonzeros 命令删除。

以下是解决问题的方法：

将W从小到大排序
对于每个 i，使用 a = W(i) 计算您将获得的总和。
选择总和 >=M 的最大 i。这告诉你 a 在 W(i) 和 W(i+1)
根据需要增加 a 以获得 sum = M。这是一个简单的代数问题，因为您知道索引 > i 的元素的贡献将被截断为 1。

这是一个实现。 candidates 是用 a=W(i) 得到的总和的各种值，如上所述。

W = [3 1 4 1 5 9 2 6 5 3];  M = 7;    % test data

n = numel(W);
sorted = sort(W);
cs = cumsum(sorted);
candidates = cs./sorted+(n-1:-1:0);    % what you get with a = sorted(i)
i = find(candidates>=M, 1, 'last');    
if (numel(i)==0)
    disp('No solution');                % M is too big
else
    a = cs(i)/(M-(n-i))         % from the equation  cs(i)/a + (n-i) = M
    disp(min(W/a,1));           % for confirmation of correctness
    disp(sum(min(W/a,1)));      % for confirmation of correctness
end

这个returns

a = 4.6667

0.6429    0.2143    0.8571    0.2143    1.0000    1.0000    0.4286    1.0000    1.0000    0.6429

 7

如何求解这样的比率函数？

How to solve such a ratio function?

matlab

math

linear-programming