Constraints like "max(column a + column b) == 2" are not DCP

Question

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?

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}