algorithm - 进行分配时最小化最小二乘的算法？

Question

假设我们必须将 x 数量分配给 k 所需数量。是否有算法可以最小化实际 k 分配值和 k 所需数量之间的平方距离？

例如，假设我们需要将 x=5 分配给 k=3 所需数量的 2,-3,4。

我们可以将 5 分配给 2,-3,6，产生 0^2 + 0^2 + 2^2 = 4 的平方距离。

我们可以将负数或任何金额分配给 k 个金额。唯一的限制是分配的金额必须总计为原始 x。分配的金额也不必是整数，只要是实数。

Answer 1

设 y 是所需数量的总和，设 d 是 x 和 y 之间的差。最小值是通过在 k 个所需数量之间平均分配 d 来获得的。读者练习：使用拉格朗日乘数证明这一点。

在给定的示例中，y = 2 - 3 + 4 = 3 和 d = 5 - 3 = 2。将 d=2 均匀分配到 k 个期望值意味着将 2/3 添加到每个项目，导致分配 2 2/3、-2 1/3 和 4 2/3。

Answer 2

这是一个特例 LP。始终通过分配使您的 delta-k 值都相同来实现最小值。

由于目标函数是平方和，并且所有数据点的权重相同，因此分配除相同值 delta-ks 以外的值会导致平方和更高。（请注意，在 josilber 的 quadprog 解决方案中，delta-k 值都是 2/3。有一个证据隐藏在偏导数领域的某个地方，我太累或太笨而无法解决。）

Answer 3

想到了两种方法：

1. 拉格朗日乘数。非常适合最小化具有线性约束的二次成本函数。该链接提供了几个有关如何设置和解决问题的示例。

   

   

   产生

   

   应用约束并定义

   

   给

   

   代回给出最终解决方案

   

   换句话说，我们计算总期望输出和总约束之间的差异，并将其平均分配。

2. 公平划分。如果您愿意放宽最小二乘标准，您的问题可能可以使用公平除法技术解决。特别是，调整后的赢家是一种在玩家之间公平分配商品的方式。你不会像你建议的那样得到否定的答案，但更像是一个蛋糕切割解决方案。

Answer 4

基本上对于数据的向量 v（长度为 k）和总预算 b，您有以下优化问题：

min_{x1, x2, ..., xk} (x1-v1)^2 + (x2-v2)^2 + ... + (xk-vk)^2
s.t. x1 + x2 + ... + xk = b

这是一个线性约束二次规划，可以使用二次规划软件包求解。例如，这里有一个quadprogR 语言包的解决方案：

# Setup data
v <- c(2, -3, 4)
b <- 5

# Solve quadratic program
library(quadprog)
solve.QP(diag(length(v)), v, matrix(rep(1, length(v))), b, 1)$solution
# [1]  2.666667 -2.333333  4.666667

在此示例中，我们得到目标值 4/3，小于原始帖子中提供的分配的目标值 4。