Overdetermined Linear System with Binary-Solution
8 views (last 30 days)
Show older comments
Hi dear matlab folks.
Following Problem:
I got a sparse rectangular matrix A with n x m elements. n>m,
A coloumnvector b with n elements.
I want to solve the problem min || Ax-b|| under the constraints of x being binary via the lsqr solver.
2 questions:
- How to give the lsqr solver the constraints of x being binary?
- The use of binary constraints is described in the help of intlinprog(). Here i have the problem to define the functionhandle with a set of equations, and not only one equation... What is the Coefficient Vector for the intlinprog()function looking when solving a overdetermined set of equations
Thanks a lot for any help.
yours, Tobi
0 Comments
Answers (1)
John D'Errico
on 8 Feb 2021
Edited: John D'Errico
on 8 Feb 2021
You CANNOT use lsqr on integer (binary) problems. Period. I don't know why you think you could do that.
You cannot use intlinprog to solve a 2-norm regression, though you can formulate a linear programming problem that solves a 1-norm objective, thus minimum absolute deviation. So you could use intlinprog, as long as you are willing to assume a 1-norm'ed objective.
2 Comments
John D'Errico
on 8 Feb 2021
That being a relatively huge problem, it is not surprising that a solver did not terminate in a reasonable time. Big problems take big time.
Unfortunately, the standard way to implement l1 norm solving using an LP solver requires the problem be expanded using a concept called slack variables. So instead of having a problem with 8128 unknowns, this becomes a problem with many more unknowns. In your case, I recall the internal problem becomes one of size 422500+8128 unknowns. This is getting seriously large. Again, big problems take big time. Huge problems take longer.
You ask how to "configure x0", based on the solution from lsqr. I have no clue what you mean by that. Since lsqr does not allow even bound constraints, the solution you will find from lsqr can be arbitrarily far from a [0,1] binary variable. Some of those unknowns may be arbitrarily large in either direction. So even just rounding the result from lsqr has no reason to be remotely close to the l1 norm solution in your binary solution space.
Finally, merely rounding a noninteger solution will not get you to a much better starting point to speed up the solve time for a huge problem.
See Also
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!