Overdetermined Linear System with Binary-Solution

6 visualizaciones (últimos 30 días)
Manuel Starlinger
Manuel Starlinger el 7 de Feb. de 2021
Comentada: John D'Errico el 8 de Feb. de 2021
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

Respuestas (1)

John D'Errico
John D'Errico el 8 de Feb. de 2021
Editada: John D'Errico el 8 de Feb. de 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 comentarios
Manuel Starlinger
Manuel Starlinger el 8 de Feb. de 2021
Editada: Manuel Starlinger el 8 de Feb. de 2021
Hello John
Thanks a lot for the Answer.
I found the function
, which is i think the method you described out in your second point.
The problem i have is, that after quite a long time (~25min) the solver didnt converge to a feasable solution. My A-Matrix has size 422500x8128.
So, i wanted to use the unconstrainted solution of the lsqr-method to be the starting point of the minL1int() function. But how do i have to configure my x0 (starting solution) for the minL1int()-function?
Do you recommend other functions, which use the intlinprog() function combined with the L1-norm?
Tobi
John D'Errico
John D'Errico el 8 de Feb. de 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.

Iniciar sesión para comentar.

Categorías

Más información sobre Mathematics en Help Center y File Exchange.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by