Integer programing for minimization

- How to solve the following integer optimization problem :

Find B and D such that B,D = Min |Y- XDB|||

where the matrices X,Y are given.

The matrix D must be a diagonal matrix where its diagonal elements are 0 or 1.

[Torsten]

Which norm do you use ?

Is it correct that the same B appears on both sides of the equation

B = Min |Y- XDB|

?

Best wishes

Torsten.

[Corto Rasp]

No indeed, thank you to underline this mistake. The purpose to this problem is to find both matrices D and B with the matrix D sparse as possible.

Answer 1

[Nihar Deodhar]

Your problem could be solved using fmincon. See Matlab documentation on fmincon for more info.

Set up the objective function as

J = abs(Y- X*D*B);

where I guess X is a known matrix/vector.

Set up B using b1,b2,b3.... etc. the number of variables needed would depend on size of B. choose n number of elements d1,d2,....dn for the square matrix D based on its size.

for instance if B is 3x3, set up b1, b2, ......b9 and if D is 3x3 as well (which would have to be given the size of B) choose d1, d2 and d3 as optimization variables ad set the off diagonal elements in D = 0. So the problem will involve (9+3 = 12) optimization variables in this case. Now you said that diagonal of D should be populated by 1 or 0. Set this range for the parameter bounds in fmincon. It is possible that you might get fractions between 0 and 1 as the optimum, just round it up to either 0 or 1 in the end.