Make Optimization term fit into DCP rules

Question

I want to make a term in an objective function I am working with fit into DCP for CVXPY.

I am working on replicating this research paper for an active learning problem. Specifically equations 5 is what I am trying to implement in CVXPY.

A bit of an explanation. I have a set of $n$ vectors $x_i$, each representing one piece of unlabeled data, that I want to get labeled into one of $C$ classes. But the difficulty is that I know that for a few of the classes that they are infrequent, so instead of taking random samples to be labeled, we want to make smart selections as to what should get labeled.

If I have a matrix $P_{ij}$, where for each row $i$ for each unlabeled data point, I have a confidence score in each column $j$ for each class. A high confidence score means that we are more certain that that data point belongs to that class, a lower one means we are less confident.

I also have a redundancy matrix $R_{ij}$, which calculated by $R_{ij}=\max(0,\cos(x_i,x_j))$. This is used to identify pairs of data points that are likely very similar, and not select them to both be labeled.

What the optimization problem is trying to solve for is a matrix $M_{ij}$ , where each row $i$ represents a data point, and each columns $j$ represents a class. For each for we either want to assign a 1 to one of the columns and all the other values remain 0 to designate a data poi t to label, or all the values remain zero to designate select no data points.

I have followed equation 5 because it looks fairly straight forward to calculate, but the difficulty I am encountering it that CVXPY does not like the $(Me)^TR(Me)$(e is a vector of ones with as many elements as there are classes) term due to it not fitting in to the rules of DCP, but the authors of the paper proved that its a linear program. When I write it in terms of the equivalent 7 in equation I run into the same issue.

What resources or hints are there for translating the redundancy term in the objective function in equation 5 and 7 in the paper into something that CVXPY will accept as compliant with DCP? I am not very familiar with how to classify the exact type of optimization that this might be, so please excuse me if I missed something that would have answered my own question.

Answer 1

Formulation (7) on p. 6 of the linked paper is very explicitly linear in the matrix variable M and the newly introduced matrix variable V. MIDCP systems, such as CVXPY (CVX and others) allow programs which are DCP compliant but for binary or integer constraints. Formulation (7) falls into that category, and is just a "plain Jane" MILP; therefore is easily entered into any such system.

Perhaps you are trying to explicitly include the first half of equation (6) $$V_{ijab} = M_{ia}M_{jb}$$ as a constraint or expression assignment in CVXPY. Do NOT do that. Declare both M and V as matrix variables, and include only the objective function and constraints in (7). The last constraint in (7) is the last half of equation (6), and is how the first half of equation (6) gets enforced in the optimization problem formulation (7). That is because as equation (6) shows, the last constraint in (7) is equivalent to the first half of equation (6).

Your apparent mistake is very similar to one I addressed in my answer at https://scicomp.stackexchange.com/questions/27206/imposing-special-structure-on-positive-semi-definite-matrix/27207#27207 . In that question, the O.P. violated DCP rules when entering a semdefinite relaxation of a non-convex quadratic constraint, by making the mistake of entering the original non-convex quadratic constraint in addition to the semidefinite constraint, which was its convex relaxation.

To address @Richard 's comment: The paper incorrectly refers to (7) as being a Linear Programming problem (LP). It is not; it is a Mixed-Integer Linear Programming problem (MILP); actually, it is a pure Binary (Integer) LP, because there are no continuous variables. MILP 's fall within the MIDCP rules, which CVXPY supports.