Optimization over a binary (or discrete) variable

Question

I have the equation $y=Kx$ where, for example, $x=\begin{pmatrix} x_1 \\ \vdots \\ x_{50} \end{pmatrix}$, where $x_i=0$ or $1$

$K \in M _{1000,50}(\mathbb R)$ a given constant matrix and $$y=\begin{pmatrix} y_1 \\ \vdots \\ y_{1000} \end{pmatrix}$$

My question is, if I was given a value for $y$ how can I find an approximation for the value of $x$?

Answer 1

Choose a measure of closeness, then minimize that measure of closeness subject to x being a zer0 one binary variable.

Common measures of closeness are:

2-norm of y-K*x, which is (equivalent to) least squares

1-norm of y-K*x, which is the sum of the n absolute differences of the $y_i$ and $(K*x)_i$

Infinity norm of y-K*xwhich is the maximum of then absolute differences of the $y_i$ and $(K*x)_i$

For instance, using YALMIP under MATLAB, assuming y is an n by 1 vector of data. Assume p equals one of 2,1, 'inf'

x = binvar(n,1);
optimize([],norm(y-K*x,p)) % minimizes norm(y-K*x,p)) subject only to the constraint that x is a binary variable
disp(value(x')) % displays the optimal value of x transpose

Here is an example with one randomly generated set of data solved with each of p = 2, 1, 'inf'.

n = 20;
K = 2*randn(n);
y = K*rand(n,1) + 2*randn(n,1);

Using these instances of K and y, and solving for optimal x gives optimal x transpose for p = 2, i, 'inf' respectively as

0     1     1     0     0     0     1     0     0     0     1     1     0     1     0     0     0     0     0     0

0     1     1     0     0     0     1     0     0     0     1     1     0     1     0     0     0     0     0     0

0     0     1     0     0     1     1     1     0     1     1     1     0     1     0     0     0     0     0     1

In this example, the 2 and 1 norm solutions came out the same, but the inf norm solution is different. Using the optimal 2 and 1 norm solution, the inf norm is 3.9828, but using the optimal inf norm solution, the inf norm is 3.4243, which is better. Using the optimal inf norm solution, the 2 norm is 9.9829, but using the optimal 2 or 1 norm solution, the 2 norm is 7.9897, which is better. Using the optimal inf norm solution, the 1 norm is 41.8925, but using the optimal 2 or 1 norm solution, the 1 norm is 28.5188, which is better. So as you can see, the choice of norm can affect the optimal solution.