Quadratic optimisation with $\ell_1$ constraints with CVXPY

Question

_{Crossposted on Mathematics SE}

---

I seek to minimize a convex quadratic objective subject to linear and $\ell_1$-based equality constraints. When I turn to CVXPY, an error is raised indicating that it does not follow DCP rules. In what ways would it violate DCP? Naively, I thought this would be a common problem so would be handled by CVXPY out of the box.

import cvxpy as cp
import numpy as np

n = 5
A = np.random.randn(n, n)
E = np.eye(n)
w = cp.Variable(n)
problem = np.Problem(
   cp.Minimize(cp.quad_form(w, E)),
   [
      A.T @ w == 0,
      cp.norm(w, 1) == 1
   ]
prob.solve()

Answer 1

cp.norm(w, 1) == 1 is a nonlinear equality constraint, hence violates DCP rules. It is a non-convex constraint.

Unless there is some special CVXPY mode or add-on to handle this, i believe you would need to introduce binary variables to handle this constraint, as shown in section 9.1.7 "Exact 1-norm" of the "Mosek Modeling Cookbook".

Note that cp.norm(w, 1) <= 1 is a DCP-compliant convex constraint. But cp.norm(w, 1) >= 1 is non-convex, and is non-DCP-compliant.

The formulation in the Mosek Modeling Cookbook gets around this by shifting the non-convexity into the binary variables. I.e., the declaration of a variable as binary or integer is in and of itself a non-convex constraint, but one which CVXPY and similar convex optimization modeling tools allow, presuming the continuous relaxation is DCP-compliant.

P.S. In the future, please follow the advice in @Henrik Alsing Friberg 's comment to show all the modeling tool and solver log output.