使用仅限Numpy和Python的受限最小二乘法

huangapple go评论76阅读模式
英文:

Constrained Least Squares with Numpy and Python only

问题

如何只使用 numpy 执行受限最小二乘法?是否有办法将约束集成到 numpy.linalg.lstsq() 中,或者是否有 numpy 和 Python 的解决方法来执行受限最小二乘法?我知道可以使用 cvxpyscipy.optimize 轻松实现这一点,但这个优化将成为 numba JITed 函数的一部分,而这两者都不受 numba 支持。

编辑:
以下是我想解决的问题的示例:

arr_true = np.vstack([np.random.normal(0.3, 2, size=20),
                      np.random.normal(1.4, 2, size=20),
                      np.random.normal(4.2, 2, size=20)]).transpose()
x_true = np.array([0.3, 0.35, 0.35])
y = arr_true @ x_true

def problem():
    noisy_arr = np.vstack([np.random.normal(0.3, 2, size=20),
                        np.random.normal(1.4, 2, size=20),
                        np.random.normal(4.2, 2, size=20)]).transpose()

    x = cvxpy.Variable(3)
    objective = cvxpy.Minimize(cvxpy.sum_squares(noisy_arr @ x - y))
    constraints = [0 <= x, x <= 1, cvxpy.sum(x) == 1]
    prob = cvxpy.Problem(objective, constraints)
    result = prob.solve()
    output = prob.value
    args = x.value

    return output, args

基本上,我的问题是在满足 $x_1+x_2+x_3 = 1$ 和 $\forall x_i, 0 \leq x_i \leq 1$ 的条件下最小化 $Ax-y$。

英文:

How to do constrained Least Squares only using numpy. Is there any way to incorporate constraints into numpy.linalg.lstsq() or is there any numpy+Python workaround to do constrained Least Squares? I know that I can do this easily with cvxpy and scipy.optimize, but this optimization will be a part of numba JITed function, and those two are not supported by numba.

EDIT:
Here is a dummy example of a problem I want to solve

arr_true = np.vstack([np.random.normal(0.3, 2, size=20),
                      np.random.normal(1.4, 2, size=20),
                      np.random.normal(4.2, 2, size=20)]).transpose()
x_true = np.array([0.3, 0.35, 0.35])
y = arr_true @ x_true

def problem():
    noisy_arr = np.vstack([np.random.normal(0.3, 2, size=20),
                        np.random.normal(1.4, 2, size=20),
                        np.random.normal(4.2, 2, size=20)]).transpose()

    x = cvxpy.Variable(3)
    objective = cvxpy.Minimize(cvxpy.sum_squares(noisy_arr @ x - y))
    constraints = [0 &lt;= x, x &lt;= 1, cvxpy.sum(x) == 1]
    prob = cvxpy.Problem(objective, constraints)
    result = prob.solve()
    output = prob.value
    args = x.value

    return output, args

Essentially, my problem is to minimize $Ax-y$ subject to $x_1+x_2+x_3 = 1$ and $\forall x_i, 0 \leq x_i \leq 1$.

答案1

得分: 3

这似乎合理,而且我的约束 x1 - x2 = 0.1 也得以满足。

英文:

Is it linear? Based on your numpy.linalg.lstsq suggestion I'll assume that for now. Also, I assume (to solve the simple case first) that you talk about equality constraints. Then you can easily solve it yourself by using Lagrange multipliers, and the solution can be found by solving a linear equation system.

If the problem is to minimize A * x - y over the constraints B * x = b, then solve

<img src="https://latex.codecogs.com/png.image?\large&space;\dpi{110}\bg{white}\begin{pmatrix}A^T\cdot&space;A&B^T\B&\end{pmatrix}\cdot\begin{pmatrix}x\\lambda\end{pmatrix}=\begin{pmatrix}A^T\cdot&space;y\b\end{pmatrix}" title="\begin{pmatrix}A^T\cdot A&B^T\B&\end{pmatrix}\cdot\begin{pmatrix}x\\lambda\end{pmatrix}=\begin{pmatrix}A^T\cdot y\b\end{pmatrix}" />

As an example:

from numpy import array, zeros
from numpy.linalg import solve

A = array([[1, 2], [3, 4], [5, 6], [7, 8]])
y = array([3.2, 6.8, 11.1, 15.2])

B = array([[1, -1]])
b = array([0.1])

S = zeros((3, 3))
r = zeros(3)

S[:2, :2] = A.T @ A
S[2:, :2] = B
S[:2, 2:] = B.T
r[:2] = A.T @ y
r[2] = b

x = solve(S, r)[:2]
print(x)

Disclamer: Bugs might be included, but brief testing gave me for x

[1.06262376 0.96262376]

This seems reasonable, and my constraint x1 - x2 = 0.1 is also fulfilled.

huangapple
  • 本文由 发表于 2023年7月28日 00:06:50
  • 转载请务必保留本文链接:https://go.coder-hub.com/76781586.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定