How to solve AX = B equation with Python (NumPy, SciPy etc.), where A, X, B are matrices and all elements of X must be non-negative

Question

I need to solve an equation AX = B using Python where A, X, B are matrices and all values of X must be non-negative.

The best solution I've found is

X = np.linalg.lstsq(A, B, rcond=None)

but as a result X contains negative values. Is it possible to get a solution without negative values? Thanks in advance!

@user2699 B has to be one-dimensional with scipy.optimize.lsq_linear and scipy.optimize.nnls unfortunately. — user2653663
– user2653663, Commented May 20, 2019 at 20:54
@user2653663 Why is that an issue? A wrapper can easily solve for each column in B, which reference solution in the question using np.linalg.lstsq already does. — user2699
– user2699, Commented May 21, 2019 at 12:14

Prune · Accepted Answer · 2019-05-20 20:59:05Z

6

In general, this is not mathematically possible. Given the basic requirements of A and B being invertible, X is a unique matrix. If you don't like the elements that X has, you can't simply ask for another solution: there isn't one. You'll have to change A or B to get a different result.

answered May 20, 2019 at 20:59

Prune

78k14 gold badges63 silver badges83 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user2699 Over a year ago

A and B do not have to be invertible - that is not a constraint given in the question or even implied. The least squares solver given in the question finds the solution that gives the minimum mean squared error - but there are other definitions of error (or constraints on B) that result in unique solutions for non-invertible A.

user2653663 · Accepted Answer · 2019-05-20 21:06:41Z

2

You could solve it with cvxpy:

import cvxpy

def solve(A, B):
    """
    Minimizes |AX - B|**2, assuming A and B are 
    square matrices for simplicity. If this optimized 
    error is zero, this corresponds to solving AX = B.
    """
    n = A.shape[0]
    X = cvxpy.Variable((n,n))
    # Set objective
    obj_fun = cvxpy.sum_squares(A*X - B)
    objective = cvxpy.Minimize(obj_fun)
    # Set constraints
    constraints = [X >= 0]
    prob = cvxpy.Problem(objective, constraints)
    result = prob.solve(solver = "ECOS")
    return X.value

EDIT: The answer by Prune is correct I believe. You can check if the error in the numerical solver is non-zero by inspecting results.

edited May 20, 2019 at 21:06

answered May 20, 2019 at 20:45

user2653663

2,9481 gold badge20 silver badges23 bronze badges

1 Comment

Андрій Немченко Over a year ago

Thank you for the answer, but I got "'shape' elements cannot be negative" error with A.shape=(128,1025) and B.shape=(128,146). When I tried the solution on arrays with less dimensios, it works fine.

Collectives™ on Stack Overflow

How to solve AX = B equation with Python (NumPy, SciPy etc.), where A, X, B are matrices and all elements of X must be non-negative

2 Answers 2

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related