CODEWITHSUNDEEP
matlabmathematical-optimizationleast-squares
T.TM
T.TM

Reputation: 31

Boolean least squares

For a spectrum estimation algorithm I need to find the best fitting linear combination of vectors to fit a target spectral distribution. So far, this works relatively well using the lsqlin optimizer in MATLAB. However, for the final application I would like to approximate/solve this problem for exclusively zeros and ones, meaning Ax=b solved for Boolean x.

Is there any way to parametrize lsqlin or another optimizer function for this purpose?

Upvotes: 1

Views: 461

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16762

If the problem is just:

Solve Ax=b for x in {0,1}

then you can use a MIP solver (e.g. Matlab intlinprog). If the problem is over-constrained and you want a least squares solution:

Min w'w
S.t. Ax - b = w
x in {0,1} (binary variable)
w free variable

then you have a MIQP (Mixed Integer Quadratic Programming) problem. There are good solvers for this such as Cplex and Gurobi (callable from Matlab). Also Matlab has a discussion about an approximation scheme using intlinprog. Another idea is to replace the quadratic objective by a sum of absolute values. This can be formulated as linear MIP model.

Upvotes: 2

Related Questions