I am struggling with the following constraint on a minimization problem

cvx.max(z[:, i] + z[:, j]) == 2

where z is a Boolean matrix decision variable. I need to ensure that at least one row in z has a $1$ in two given columns (i and j). CVXPY informs me that this is not DCP-compliant.

Can you think of a DCP formulation that would enable a constraint such as z[k, i] == 1 and z[k, j] == 1 for at least one k?


1 Answer 1


Not sure if it is DCP, but you can write it as a quadratic constraint: $$\sum_k z_{k,i} z_{k,j} \ge 1$$ You can also linearize as follows: \begin{align} \sum_k x_{k,i,j} &\ge 1 \\ x_{k,i,j} &\le z_{k,i} \\ x_{k,i,j} &\le z_{k,j} \end{align}

  • $\begingroup$ The linearization is DCP-compliant (the quadratic constraint is not). $\endgroup$ Commented Mar 3, 2022 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.