least square with equality constraint and singular matrix

I have the following problem to solve:

Ax = b where A is singular.

To resolve this I introduce a condition Cx = d

Even after this, I am not able to solve it using scipy.optimize.minimize as it keeps complaining that the matrix is singular. I am trying to solve it using the following:

optimum_func = lambda x: np.sum((Ax -b)**2) constraint = ({'type': 'eq', 'func': lambda x: C@x-d})

What is the right way to solve this problem? And what theory did I miss that it does not work? Please ask for any other information needed and I will edit this post with information.

• Does $Ax = b$ even have a solution? Mar 29 '19 at 19:30
• in the least square sense, I am pretty sure it does. Mar 30 '19 at 12:00
• What if $A x = b$ has infinitely many solutions? Then you're solving the wrong problem. Mar 30 '19 at 12:09

You can use the Moore–Penrose inverse (the pseudoinverse) to get a solution. In this example, the system is over-determined (has infinitely many solutions) and the pseudo-inverse leads to the least-squares solution.

import numpy as np
A = np.array([[3, 4], [6, 8]])
b = np.array([, ])
# Compute the pseudo inverse and solve
Apinv = np.linalg.pinv(A)
x = Apinv @ x
x
#> array([[1.8],
#>       [2.4]])
# Check that A*x = b
A @ x
#> array([[15.],
#>       [30.]])

# Or find the least squares solution
soln = np.linalg.lstsq(A, b)
x = soln
x
#> array([[1.8],
#>       [2.4]])
A @ x
#> array([[15.],
#>       [30.]])
$$`$$