given two constant matrices $D$ and $T$,$D \in \{0,1\}^{m,n},\ T \in \{0,1\}^{m,l}$, $R$ is a binary variable matrix ,$R \in \{0,1\}^{n,l}$, i want to minimize the following objective function:
$min(\ \sum_{i=1}^nmax({R_i})+\sum_{i=1}^n\sum_{j=1}^lR_{i,j}+||DR-T||_{F}^2\ )$
$max({R_i})$ refers to the maximum of the $i$th row of matrix $R$
n is a big number so i can not just use the optimization toolbox directly,
The objective function is convex, I have tried get the fractional solution firstly and round it to get the binary solution, but the result is not good.(I used randomized rounding but the expectation of cost is very high)
Is there any method to tackle this problem? I just need some hints and/or references.
Takes in advance!
You can linearize the $\max(R_i)$ part of the objective by replacing it with a new (binary or nonnegative) variable $S_i$ and linear constraints $S_i \ge R_{ij}$ for all $i$ and $j$. You can also linearize the quadratic part of the objective. See https://or.stackexchange.com/questions/37/how-to-linearize-the-product-of-two-binary-variables