最小化具有 Python 范围内的多变量、约束线性函数？

Question

我必须最小化以下函数：

def foo(x):
        sigma1 = sum([sum([KS * x[U + e * K + k] for k in range(K)]) for e in range(E)])
        sigma2 = sum([W * c for c in x[U + Y: U + Y + X]])
        sigma3 = sum([T * z for r in x[U + Y + X:]])
        return sigma1 + sigma2 + sigma3

其中 KS、U、K、E、W、Y、X、T 是常量，x 是 [0;1] 范围内数字的向量。

此外，必须匹配几个约束条件：

cons = [
        {
           'type': 'ineq', 'fun': lambda x, k=k, e=e:  x[U + K * e + k + 1] - x[U + K * e + k]
        }
        for k in range(K - 1) for e in range(E)
    ]

cons += [
        {
            'type': 'ineq', 'fun': lambda x, r=r, c=c: x[U + Y + X + r - 1] - x[U + Y + c]
        }
        for r in range(R)
    for c in range(C)
    ]
cons += [
        {
            'type': 'ineq', 'fun': lambda x, e=e: sum([M * x[U + e * K + k] for k in range(K)]) - sum(V * x[E * d + e] for d in range(D)])
        }
        for e in range(E)
    ]
cons += [
        {
            'type': 'ineq', 'fun': lambda x, k=k, c=c, e=e: x[U + Y + c] - x[U + e * K + k]
        }
                for r in range(R)
            for c in range(C)
        for e in range(E)
    for k in range(K)
    ]
cons += [
        {
            'type': 'eq', 'fun': lambda x, d=d, i=i: sum(x[E * i + e] for e in some_dict[d["ENTRY"]].values()) - 1
        }
        for i, d in enumerate(dicts)
    ]

，其中 M、V、D、C 是常量，dicts 是字典列表，在 "ENTRY" 键下还包含字典。初始猜测向量：

init_guess = [1] * (U + C + Y + Z)

最小化：

result = scipy.optimize.minimize(fun=foo, x0=init_guess, method='SLSQP', constraints=cons, options={"maxiter": 5000}, bounds=[(0, 1) for _ in range(len(init_guess))])

但是，输出如下所示：

nfev: 159
fun: 17480.0
status: 6
njev: 1
   x: array([ 1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,
    1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,
    1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,
    1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,
    1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,
    1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,
    1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,
    1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,
    1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,
    1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,
    1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,
    1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.])
 message: 'Singular matrix C in LSQ subproblem'
 jac: array([    0.,     0.,     0.,     0.,     0.,     0.,     0.,     0.,
       0.,     0.,     0.,     0.,     0.,     0.,     0.,     0.,
       0.,     0.,     0.,     0.,     0.,     0.,     0.,     0.,
       0.,     0.,     0.,     0.,     0.,     0.,     0.,     0.,
       0.,     0.,     0.,     0.,     0.,     0.,     0.,     0.,
       0.,     0.,     0.,     0.,     0.,     0.,     0.,     0.,
       0.,     0.,     0.,     0.,     0.,     0.,     0.,     0.,
       0.,     0.,     0.,     0.,     0.,     0.,     0.,     0.,
      15.,    15.,    15.,    15.,    15.,    15.,    15.,    15.,
      15.,    15.,    15.,    15.,    15.,    15.,    15.,    15.,
      15.,    15.,    15.,    15.,    15.,    15.,    15.,    15.,
      15.,    15.,    15.,    15.,    15.,    15.,    15.,    15.,
      15.,    15.,    15.,    15.,    15.,    15.,    15.,    15.,
      15.,    15.,    15.,    15.,    15.,    15.,    15.,    15.,
      15.,    15.,    15.,    15.,    15.,    15.,    15.,    15.,
      15.,    15.,    15.,    15.,    15.,    15.,    15.,    15.,
      80.,    80.,    80.,    80.,    80.,    80.,    80.,    80.,
      80.,    80.,    80.,    80.,    80.,    80.,    80.,    80.,
      80.,    80.,    80.,  1500.,  1500.,  1500.,  1500.,  1500.,
    1500.,  1500.,  1500.,  1500.,  1500.,     0.])
 nit: 1
 success: False

我不仅不明白为什么它会失败，而且也不明白为什么雅可比矩阵虽然计算正确，但在末尾有一个额外的'0'（所以它比初始猜测向量长1个元素）。我试过明确发送雅可比行列式，但结果还是一样。我不能使用其他最小化方法，因为只有 SLSQP 可以处理 'eq' 和 'ineq' 约束以及边界。如果 scipy.optimize.minimize 不是解决此问题的好工具，谁能推荐另一个能够解决此问题的 Python 库？我不熟悉线性优化，但我必须在 Python.

中执行此操作

Answer 1

我建议使用 GLPK/Python：https://en.wikibooks.org/wiki/GLPK/Python。它是免费的、开源的，它可以解决 LP 和 MIP 问题，您可以在许多 linux 存储库中找到它。

最小化具有 Python 范围内的多变量、约束线性函数？

Minimizing multivariable, constrained linear function with bounds in Python?

python

optimization

scipy

linear-programming