Constrained Optimization : Minimize sum of dot products

Question

I am working on minimizing the sum of dot products. The problem can be stated as follows.

Given a matrix $A$ where each entry is either $0$ or $1$, $A_{ij} \in \{0,1\}$, with the constraint that the sum of each column is greater or equal to $k$, $$\sum_{i=1}^{m} A_{ij} \geq k, \qquad j \in \{1,\dots,n\}$$ and the objective is to minimize the sum of pairwise dot product of each column. (i.e. in each column at-least $k$ elements are $1$)

$$\min\sum_{i=1}^{n}\sum_{j=i}^{n} A_i^{'} A_j$$

Could someone please help me with this problem? Please let me know if there is a standard closed form solution for this problem.

Answer 1

For small instaces you can solve this using mixed-integer linear programming. You use the fact that $A_{ij}^2 = A_{ij}$ and bilinear products $A_{ij}A_{kl}$ are taken care of by replacing them with a new variables $B_{ijkl}$ with the constraints

$B_{ijkl} \leq A_{ij}, B_{ijkl} \leq A_{kl}, B_{ijkl}\geq A_{ij}+A_{kl}-1$

The following snippet implements this in the free MATLAB Toolbox YALMIP (I'm the developer). The instance below is solved in a second or so using the MILP solver Gurobi. The command binmodel does the magic of linearizing the model according to the strategy above.

n = 6;
m = 7;
A = binvar(n,m,'full');
obj = sum(sum(A'*A));
[obj,cut] = binmodel(obj);
solvesdp([cut,sum(A,1)>=3],obj)
double(A)

Of course, this approach is only relevant for small problems, as the number of new variables and constraints introduced will be quartic in the dimension of $A$. Might be useful for seeing the pattern on a closed form solution though.

BTW, you have a misplaced transpose in your objective.