Binary matrix optimization problem

Question

Let $\mathbf{u} \in \mathbb{R}^{M}$ and $\mathbf{v} \in \mathbb{R}^{N}$ be two given vectors. I want to solve the following optimisation problem

$$\min \limits_{\mathbf{X}} \hspace{3mm} \mathbf{u}^{T}\mathbf{X}^{T}\mathbf{X}\mathbf{u} + \mathbf{v}^{T}\mathbf{X}\mathbf{u}$$ $$ s.t. \hspace{3mm}X_{nm} \in \{0,1\}, $$

$~\text{for}~ 1\leq m \leq M ~\text{and}~ 1\leq n \leq N.$

Is there any method to tackle this problem? I just need some hints and/or references.

Takes in advance!

Answer 1

Just for fun, I decided to test three different ways to solve the problem. The first is the obvious approach to simply solve the mixed-integer QP as it is written. The second approach implements the model as a second-order cone program as in the answer by @linalg, and in the third approach we use a mixed-integer LP formulation (a binary product $xy$ can be linearized by replacing it with a new variable z which constraints $z\geq x + y-1, z\leq x, z\leq y$.

For the problem sizes I tested, the LP or QP form turned out to be fastest typically (which is reasonable as these are much more mature areas than MISOCP). Implemented using the MATLAB Toolbox YALMIP, and problems solved with integer solvers CPLEX and Gurobi.

n = 8;
m = 10;
X = binvar(n,m);
v = randn(n,1);
u = randn(m,1);

% Solve as mixed-integer QP
optimize([],u'*X'*X*u + v'*X*u)

% Solve as mixed-integer SOCP
sdpvar t
optimize(norm(X*u) <= t, t^2 + v'*X*u)

% Solve as mixed-integer LP
[p,cuts] = binmodel(u'*X'*X*u);
optimize(cuts, p + v'*X*u)

Answer 2

Rewrite the problem to $\min_{X,t} \{ t^2 + v^TXu \; : \; ||Xu|| \leq t, X \in \{0,1\}^{n\times m} \}$ The objective is quadratic while the constraint is second order conic. This is therefore called a mixed integer second order conic optimization problem. MOSEK is arguably the best solver to solve this problem.