LSQLIN For sparse matrices?

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?

Answer 1

[Harish Guruprasad]

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.

Answer 2

[Andrew S]

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

Answer 3

[Harish Guruprasad]

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.