I am trying to solve Ax=b for an underdetermined system with an objective function based on weighted basis vectors.
I can’t seem to get a simple implementation to work, however. I have a very basic setup of my issues below.
First, the simple 3x3 square system works correctly:
# Objective is to satisfy Ax=b
# while minimizing weights * coefficients.
A = numpy.array([[0,0,1],[0,1,0],[1,0,0]])
x = cvx.Variable(len(A))
b = [1,2,3]
# weights
c = numpy.array([1, 1, 1])
obj = cvx.Minimize(c@x)
constraints = [A.T@x == b]
prob = cvx.Problem(obj, constraints)
result = prob.solve(solver="SCS")
print(x.value.round(), result.round())
[3. 2. 1.] 6.0
When I add another basis vector, however, the solver does not find a solution (even though there is one - [2,1,0,1], 3.1
)
A = numpy.array([[0,0,1],[0,1,0],[1,0,0],[1,1,1]])
x = cvx.Variable(len(A))
b = [1,2,3]
c = numpy.array([1, 1, 1, 0.1])
obj = cvx.Minimize(c@x)
constraints = [A.T@x == b]
prob = cvx.Problem(obj, constraints)
result = prob.solve(solver="SCS")
print(x.value, result)
None -inf
So I wonder if I have defined my system wrong. Thanks so much for the help!!