How can I solve a binary quadratic program in MATLAB?

Question

I'm not an expert in MATLAB. Can I use MATLAB function fminimax to solve the problem below?

---

Let's say I have matrix $\mathbf P$ and let's say $\bf Px = b$. My problem consists of

$$\begin{array}{ll} \text{minimize} & \| {\bf P} {\bf x} \|_2^2& \\ \text{subject to} & {\bf P} {\bf x} \geq {\bf y} \\ & \ell \leq {\bf 1}^\top {\bf x} \leq u \\ & x_i \in \{0,1\}\end{array}$$

where $\mathbf P$, $\mathbf y$, $\ell$, and $u$ are given. The purpose of $\mathbf x$ is to get specific parts of $\mathbf P$ into $\mathbf b$.

Answer 1

You need a mixed-integer quadratic programming solver for this, such as Mosek or Gurobi, available also for MATLAB, free for academia

With a modelling Toolbox such as YALMIP (developed by me) with some installed MIQP solver, you would conveniently solve it then as

x = binvar(n,1);
optimize([l<=sum(x)<=u,P*x >= 0],x'*P'*P*x);

However, with the trivial size you speak about, nothing will beat brute-force enumeration.