Constrained Optimization : Minimize sum of dot products I am working on a problem to minimize sum of dot product. The problem can be stated as following.
Given a matrix where each element is either 0 or 1.
$$
\ A_{ij} = \{0,1\};
$$
with the constraint that sum of each column is greater or equal to k
$$
\ \sum_{i=1}^{m} A_{ij} >= k ; j=1...n
$$
And the objective is to minimize 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.
Thanks
 A: 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.
