带不等式的最小二乘线性规划

Question

我正在使用 Numpy np.linalg.lstsq(A, b, rcond=-1) 通过最小二乘法求解具有近似解的方程组。

但是我意识到近似解包含某些维度系数的负值。所以我想添加边界以使所有维度都为正。我认为这意味着在方程组中增加不等式。似乎 SciPy 与 from scipy.optimize import linprog 有这个 - 但是这要求我自己指定一个函数来最小化它在我的例子中是“最小二乘”规范，但我不知道如何定义它。 AFAIU 没有默认功能。我如何使用 SciPy linprog 和某种默认的最小二乘范数作为最小化函数？

这是使用 NumPy 的代码：

import numpy as np

# This is a matrix representing fertilisers, 
# i.e. products with various chemical elements in them
A = np.array([[1.04e+01, 0.00e+00, 0.00e+00, 1.00e+00, 0.00e+00, 0.00e+00,
        3.00e+00, 1.20e+01, 9.00e+00],
       [7.00e+00, 0.00e+00, 0.00e+00, 5.00e+01, 0.00e+00, 0.00e+00,
        3.00e+01, 6.00e+00, 5.00e+00],
       [2.70e+01, 0.00e+00, 0.00e+00, 9.00e+00, 0.00e+00, 0.00e+00,
        3.00e+01, 2.90e+01, 3.90e+01],
       [0.00e+00, 0.00e+00, 1.50e+01, 2.00e+00, 1.60e+01, 0.00e+00,
        0.00e+00, 0.00e+00, 2.00e+00],
       [7.00e+00, 1.50e+01, 0.00e+00, 0.00e+00, 0.00e+00, 0.00e+00,
        0.00e+00, 7.00e+00, 0.00e+00],
       [0.00e+00, 0.00e+00, 3.00e+01, 0.00e+00, 3.00e+01, 0.00e+00,
        0.00e+00, 0.00e+00, 1.12e+01],
       [0.00e+00, 0.00e+00, 5.00e-01, 1.00e-02, 0.00e+00, 6.00e-01,
        1.00e-01, 1.00e-02, 1.00e-02],
       [0.00e+00, 0.00e+00, 0.00e+00, 2.00e-02, 0.00e+00, 5.00e-01,
        0.00e+00, 1.60e-01, 4.00e-02],
       [0.00e+00, 5.00e-01, 5.00e-01, 2.00e-03, 1.00e+00, 1.50e+00,
        1.00e-01, 4.00e-02, 2.00e-03],
       [0.00e+00, 0.00e+00, 0.00e+00, 2.00e-03, 5.00e-01, 2.00e-01,
        0.00e+00, 1.00e-02, 2.00e-03],
       [0.00e+00, 0.00e+00, 0.00e+00, 1.00e-03, 0.00e+00, 2.00e-01,
        1.60e+00, 6.00e-03, 2.00e-03],
       [0.00e+00, 5.00e-01, 5.00e-01, 1.00e-02, 1.50e+00, 2.10e+00,
        1.00e-01, 8.00e-02, 1.00e-02],
       [4.10e+00, 0.00e+00, 0.00e+00, 8.00e+00, 0.00e+00, 0.00e+00,
        3.00e+00, 0.00e+00, 1.00e+00]])

# this is a vector representing a given "recipe" 
# for desired quantities of each chemical element
b = np.array([[8.0e+01],
       [4.5e+01],
       [1.0e+02],
       [5.0e+01],
       [2.0e+02],
       [1.8e+02],
       [5.0e-01],
       [3.0e+00],
       [5.0e-01],
       [5.0e-02],
       [5.0e-02],
       [5.0e-01],
       [0.0e+00]])

# the optimisation solution
x_solution = np.linalg.lstsq(A, b, rcond=-1)
x_approx_sol = x_solution[0]
x_residuals = x_solution[1]

# the "new b" according to the optimised "x solution"
b_approx = A.dot(x_approx_sol)

如您所见，x_approx_sol 包含负数，这意味着每种肥料的数量为负数，但我希望只有 0 个或正数：

array([[ -7.06529347],
       [ 12.62140023],
       [ 16.79436939],
       [  6.67404177],
       [-13.95259075],
       [  2.26982817],
       [-11.05480032],
       [  8.58752025],
       [  8.08066117]])

所以我想我应该在 SciPy linprog 中添加一个包含 9 个元素的“边界”数组作为 (0, float("inf"))。如何定义要最小化的距离范数？它应该是欧几里德 2-范数 || b - x ||

Answer 1

您正在寻找 https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.nnls.html which is an implementation of https://en.wikipedia.org/wiki/Non-negative_least_squares。

在这种情况下用nnls替换lstsq（b也需要只有一个维度）：

# the optimisation solution
x_approx_sol, x_residuals = nnls(A, b.squeeze())

# the "new b" according to the optimised "x solution"
b_approx = A.dot(x_approx_sol)

assert (x_approx_sol >= 0).all()

print(x_approx_sol.reshape(-1, 1))

给予

[[ 0.        ]
 [11.50294958]
 [ 5.44866408]
 [ 0.36370257]
 [ 0.        ]
 [ 0.        ]
 [ 0.        ]
 [ 3.84407344]
 [ 0.        ]]

Answer 2

线性编程不会帮助您 non-linear objective。关于 general-purpose constrained-optimization，您可能希望针对凸 quadratic-programming 或 second-order 圆锥编程。但是不需要使用那些非常通用的工具（更通用 = 不太健壮）。

要么去：

David 的方法非常适合 small/medium-sized 密集问题
- 可能是最简单的方法
或使用scipy.optimize.least_squares
- 由于它支持 non-linear 函数
- 稀疏算法可用
或基于L-BFGS-B构建您自己的最小化器
- 更多工作
- 当实例变大时，与 NNLS 相比，对我来说效率要高得多！

So I would like to add boundaries to make all the dimensions only positive. I think this means adding inequalities to the system of equations.

请记住，您想介绍 variable-bounds，可以由 linear-equalities 介绍，但通常这些类型的约束是明确强制执行的（例如 simplex-method 的修改；投影到边界等）。第 2n 和第 3 种方法都支持 variable-bounds，但不支持一般（甚至线性）约束：某种程度上表明，使用这些约束并不同样困难。

Answer 3

Scipy.optimize 提供 nnls、non-negative 最小二乘法。对于一般框约束，使用 least_squares 进行 non-linear 优化或 lsq_linear 用于框约束的线性问题。

带不等式的最小二乘线性规划

Least Squares Linear Programming with inequalities

numpy

scipy

mathematical-optimization

linear-programming

euclidean-distance