linear-programming - 使用纸浆在混合整数线性规划中公式化函数的平方

Question

我有一个线性方程 Ax = b。我正在尝试使用 Python 中的纸浆来最小化 (Ax-b)^2。A 的尺寸为 (1000, 500)，b 的尺寸为 (1000,)。

到目前为止，我已经尝试过：

import pulp
mse = pulp.LpProblem("Example_Problem", LpMinimize)
vars = pulp.LpVariable.dicts('x', range(len(A[0])), lowBound=0,upBound =1, 
                             cat='Integer')
for row, rhs in zip(A, b):
    mse += sum([row[i]*vars[i] for i in range(len(row))]) - rhs

我如何将正方形用于函数 mse。如果我尝试：

mse += (sum([row[i]*vars[i] for i in range(len(row))]) - rhs)**2

我收到此错误：

* ** 或 pow() 不支持的操作数类型：'LpAffineExpression' 和 'int'*

Answer 1

Pulp 仅适用于线性模型。您创建了一个非线性模型。

从理论上讲，您可以通过形成正规方程来解决这个问题（请参阅统计书籍）：您得到一个线性方程组。这可以用 LP 求解器来解决，但不幸的是，这种方法不是很可靠。

使用 LP 模型的更好方法是用偏差的绝对值代替偏差的平方。这会给你一个 LP（见链接）。此方法有时用于获得受异常值影响较小的更稳健的估计。

加上 x 必须采用整数值的约束，您最终得到了一个 MIP 模型。