title: L1 convex optimization with equality constraints in python
body: <p>I need to minimize L_1(x) subject to Mx = y. </p>
  
  <p>x is a vector with dimension b, y is a vector with dimension a, and M is a matrix with dimensions (a,b).</p>
  
  <p>After some reading I determined to use scipy.optimize.minimize: </p>
  
  <pre><code>import numpy as np
  from scipy.optimize import minimize
  
  def objective(x):     #L_1 norm objective function
      return np.linalg.norm(x,ord=1)
  
  constraints = [] #list of all constraint functions
  for i in range(a):
      def con(x,y=y,i=i):
          return np.matmul(M[i],x)-y[i]
      constraints.append(con)
  
  #make constraints into tuple of dicts as required by scipy 
  cons = tuple({'type':'eq','fun':c} for c in constraints)
  
  #perform the minimization with sequential least squares programming
  opt = minimize(objective,x0 = x0,
                          constraints=cons,method='SLSQP',options={'disp': True})
  </code></pre>
  
  <p>First, 
  what can I use for x0? x is unknown, and I need an x0 which satisfies the constraint M*x0 = y: How can I find an initial guess which satisfies the constraint? M is a matrix of independent Gaussian variables (~N(0,1)) if that helps. </p>
  
  <p>Second, 
  Is there a problem with the way I've set this up? When I use the true x (which I happen to know in the development phase) for x0, I expect it to return x = x0 quickly. Instead, it returns a zero vector x = [0,0,0...,0]. This behavior is unexpected. </p>
  
  <p>Edit: </p>
  
  <p>Here is a solution using cvxpy** solving min(L_1(x)) subject to Mx=y:</p>
  
  <pre><code>import cvxpy as cvx
  
  x = cvx.Variable(b) #b is dim x  
  objective = cvx.Minimize(cvx.norm(x,1)) #L_1 norm objective function
  constraints = [M*x == y] #y is dim a and M is dim a by b
  prob = cvx.Problem(objective,constraints)
  result = prob.solve(verbose=False)
  
  #then clean up and chop the 1e-12 vals out of the solution
  x = np.array(x.value) #extract array from variable 
  x = np.array([a for b in x for a in b]) #unpack the extra brackets
  x[np.abs(x)&lt;1e-9]=0 #chop small numbers to 0 
  </code></pre>