algorithm - 最小化数字加权和的绝对值

Question

我的部分问题是最小化某些数字的加权和的绝对值。我必须找到重量。

假设我有一组数字 A、a1、a2、a3 和 a4，这样 (a1, a2 > 0), (a3, a4 < 0)

例如，最小重量为 0.1 (10%)，最大重量为 0.4 (40%)。我正在寻找权重w以使加权和为零；如果不可能为零，则最接近于零。可以使用一个简单的线性模型来实现这一点：

Minimise E

E >= SUM w * a
E >= -(SUM w * a)
SUM w = 1
w >= 0.1 for all w
w <= 0.4 for all w

一个简单的线性程序足以快速找到解决方案。但是，我非常想为这个问题找到一个多项式算法或公式。有任何想法吗？这个问题众所周知吗？

谢谢！

score 1 · Accepted Answer

最小化（或最大化）SUM w * a很容易；将所有权重设置为最小值，然后从最小到最大（分别从最大到最小）增加关于局部最大值的权重，直到达到全局最大值。

如果 [min, max] 区间包含 0，则最优解可以实现为这两个解的凸组合。否则，使解更接近于 0。

score 1 · Accepted Answer

椭球算法是线性规划的第一个最坏情况多项式时间算法。

但是，我怀疑您想快速解决问题，这就是您对多项式时间算法感兴趣的原因。

在这种情况下，使用单纯形法会更好。尽管单纯形在最坏的情况下是指数的，但它似乎是大多数实际应用的最佳选择。毫不奇怪，它在我所知道的所有高质量求解器中都实现了。

2 回答 2