LSQLIN For sparse matrices?

조회 수: 5 (최근 30일)
Andrew S
Andrew S 2011년 5월 10일
Hello,
I've run into the problem that I need to solve an optimization problem for very large matrices. The equality constraint matrix is around 75000 by 75000, but only represents around 190 equalities (to this extent, I might be doing things inefficiently). There are no other constraints. The only way I can make such a large matrix is using sparse, but lsqlin's constraints do not cooperate with sparse matrices. Is there some other way I can formulate the problem so I can specify these 190 constraints?
Any and all replies are really appreciated!
~Andy
Afterthought: Reading the error message more carefully, I see it's saying that I could use bound constraints for sparse matrices. Is this accurate? If so, would it make sense to form bound constraints in two directions? Would MATLAB be able to solve this?

답변 (3개)

Harish Guruprasad
Harish Guruprasad 2011년 5월 10일
Hi Andy,
If you really have only 190 equality constraints but 75000 variables , it must mean that your equality constraint matrix consists of linearly dependent rows the best way would obviously be to remove the dependent rows and work with the rest. But if you are somehow just given the huge matrix, (and if you know the exact number of independent equality constraints) you can start with an empty matrix and keep on adding rows from the constraint matrix till you reach the required rank.
And no, even if you have just equality constraints for separate variables(not linear combinations of variables), you can't enforce them using the lower and upper bound constraints. But in that case you can easily reduce the problem yourself analytically.
Harish.

Andrew S
Andrew S 2011년 5월 11일
Hi Harish,
I decreased it down to a 190 by 75000 matrix, but this doesn't solve the problem. MATLAB has to convert the main C matrix to the full representation, it seems, so that is where the out of memory difficulties are coming about. Is there any way to get around this? Is there a different solver I can use?
~Andy

Harish Guruprasad
Harish Guruprasad 2011년 5월 11일
An 190 by 75000 double matrix takes about 100 MB memory, which Matlab can handle (with some difficulty) on a decent machine.
If not, your best bet would be 'quadprog', you can always rewrite a least squares problem as a quadratic optimization , and I think quadprog accepts sparse equality constraints. But there might be trouble if the matrix H of quadprog(equivalent to C'*C of the lsqlin formulation) is singular.
Also you might save a significant amount of time as your formulation can be solved using the large scale formulation of quadprog, whereas lsqlin would automatically use the medium scale algorithm in the presence of equality constraints.
Harish.

카테고리

Help CenterFile Exchange에서 Linear Least Squares에 대해 자세히 알아보기

제품

Community Treasure Hunt

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

Start Hunting!

Translated by